图论基础原理与题目说明文章目录图论基础原理与题目说明一、 图论基本概念1.1 图的核心定义1.2 图的存储方式二、 图的遍历核心DFS 与 BFS2.1 DFS深度优先遍历2.2 BFS广度优先遍历三、 高阶概念有向图与 Trie 树3.1 入度与出度拓扑排序前置知识3.2 Trie前缀树 / 字典树四、 图论算法实战演练[200. 岛屿数量](https://leetcode.cn/problems/number-of-islands/)[994. 腐烂的橘子](https://leetcode.cn/problems/rotting-oranges/)[207. 课程表](https://leetcode.cn/problems/course-schedule/)[208. 实现 Trie (前缀树)](https://leetcode.cn/problems/implement-trie-prefix-tree/) 查看完整专栏LeetCode基础算法专栏特别说明本文为个人的 LeetCode 刷题与学习笔记内容仅供学习与交流使用禁止转载或用于商业用途。需要强调的是文中的题目解法不一定是最优解可能存在时间或空间复杂度的进一步优化空间主要目的是分享个人的解题思路与逻辑实现仅供参考。笔记内容为个人理解与总结可能存在疏漏或偏差欢迎读者自行甄别并交流探讨。一、 图论基本概念1.1 图的核心定义图是由顶点节点**和**边组成的结构记为G ( V , E ) G(V,E)G(V,E)。分类维度类型特点刷题关注点边的方向无向图边无方向如社交网络的好友关系有向图边有方向如道路单行道、任务依赖关系边的权重无权图边无值仅表示连通状态有权图边有值如两点间的距离、费用、时间等环的存在无环图无闭环如经典的 DAG有向无环图有环图存在闭环遍历时必须加标记以避免死循环1.2 图的存储方式邻接表用数组或哈希表存储每个节点的相邻节点列表空间复杂度通常更优最常用。邻接矩阵二维数组matrix[i][j]。值为 1 代表相连0 代表不连若为有权图则直接存储权重值。二、 图的遍历核心DFS 与 BFS图的遍历是所有图论算法的基石本质上与二叉树的遍历同源。唯一且最致命的区别在于图可能存在环必须利用visited标记访问状态防止无限死循环。2.1 DFS深度优先遍历核心思路从起点出发沿着一条路径走到黑不撞南墙不回头再回溯走其他路径同二叉树的前序/后序递归逻辑。基础模板邻接表 递归defdfs(node,adj,visited):visited[node]True# 标记当前节点已访问# print(node) # 访问节点执行业务逻辑# 遍历所有相邻节点forneighborinadj[node]:ifnotvisited[neighbor]:dfs(neighbor,adj,visited)2.2 BFS广度优先遍历核心思路从起点出发像水波纹一样先访问所有直接相邻的节点一层再访问相邻节点的相邻节点下一层同二叉树的层序遍历逻辑。基础模板邻接表 队列fromcollectionsimportdequedefbfs(start,adj,visited):qdeque([start])visited[start]Truewhileq:nodeq.popleft()# print(node) # 访问节点forneighborinadj[node]:ifnotvisited[neighbor]:visited[neighbor]Trueq.append(neighbor)三、 高阶概念有向图与 Trie 树3.1 入度与出度拓扑排序前置知识在有向图中入度与出度是描述「节点与边」关系的核心指标。概念通俗定义数学定义入度指向当前节点的边的数量有多少个 “前驱” 指向我i n _ d e g r e e ( u ) in\_degree(u)in_degree(u) 以u uu为终点的边数出度从当前节点出发的边的数量我有多少个 “后继”o u t _ d e g r e e ( u ) out\_degree(u)out_degree(u) 以u uu为起点的边数入度为 0 的节点没有任何前驱依赖可以直接作为起点开始。出度为 0 的节点没有任何后继依赖是终点。拓扑排序把有向无环图DAG的节点排成一个序列满足 “所有边的起点必须排在终点的前面”。若图中有环则无法完成拓扑排序因为永远找不到入度为 0 的起始节点。3.2 Trie前缀树 / 字典树Trie 是专门用于高效存储和检索字符串集合的树形数据结构。核心优势「共享字符串前缀」。例如存储app和apple时前缀app会被共享大幅节省空间。检索时间仅与目标字符串长度相关与集合大小无关。节点设计children字典key字符value子节点存储当前节点的所有分支。is_end布尔值标记该节点是否是某个完整单词的结尾。四、 图论算法实战演练200. 岛屿数量题目描述给你一个由1陆地和0水组成的的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。解题思路选用DFS深度优先搜索嵌套递归法。遍历网格遇到未被访问的陆地1时启动一次 DFS 递归。在 DFS 过程中将该陆地及其所有相连的陆地原地修改为水0。这相当于利用原网格代替了visited数组。每启动一次 DFS 就代表消灭并找到了一个独立岛屿最终统计 DFS 的启动次数即可。核心代码fromtypingimportListclassSolution:defnumIslands(self,grid:List[List[str]])-int:ifnotgridornotgrid[0]:return0rowslen(grid)colslen(grid[0])ans0# 定义 DFS 函数作用是淹没 (x,y) 所在的整个相连岛屿defdfs(x,y):# 递归终止条件越界或者当前单元格已经是水ifnot0xrowsornot0ycolsorgrid[x][y]0:return# 核心操作将当前陆地标记为水替代 visited 数组grid[x][y]0# 递归遍历上下左右淹没相连陆地dfs(x-1,y)dfs(x1,y)dfs(x,y-1)dfs(x,y1)# 遍历网格寻找岛屿起点foriinrange(rows):forjinrange(cols):ifgrid[i][j]1:ans1# 发现新岛屿dfs(i,j)# 启动 DFS 淹没它returnans994. 腐烂的橘子题目描述每分钟腐烂的橘子周围 4 个方向上相邻的新鲜橘子都会腐烂。返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能全腐烂返回 -1。解题思路「同时腐烂」说明过程是分层扩散的「多个初始腐烂点」说明需从多个起点同时开始。这完美契合多源 BFS算法初始化将所有初始腐烂橘子的坐标加入队列并统计新鲜橘子的总数。分层 BFS每一层循环代表“过了一分钟”。逐个取出队列中的腐烂橘子向四周扩散将新鲜橘子腐烂并加入下一层队列同时新鲜橘子总数减一。结果判定若最终新鲜橘子数 0 00返回 -1否则返回统计的分钟数。核心代码importcollectionsfromtypingimportListclassSolution:deforangesRotting(self,grid:List[List[int]])-int:ifnotgridornotgrid[0]:return0rowslen(grid)colslen(grid[0])queuecollections.deque()fresh_num0time0# 1. 收集初始腐烂橘子多源起点并统计新鲜橘子foriinrange(rows):forjinrange(cols):ifgrid[i][j]1:fresh_num1elifgrid[i][j]2:queue.append((i,j))dirs[(-1,0),(1,0),(0,-1),(0,1)]# 2. 分层 BFS 模拟腐烂过程whilequeueandfresh_num0:level_sizelen(queue)for_inrange(level_size):x,yqueue.popleft()fordx,dyindirs:nx,nyxdx,ydy# 发现相邻的新鲜橘子if0nxrowsand0nycolsandgrid[nx][ny]1:grid[nx][ny]2fresh_num-1queue.append((nx,ny))time1returntimeiffresh_num0else-1207. 课程表题目描述判断是否可能完成所有课程的学习课程之间存在先修依赖关系。本质是判断有向图中是否存在环。解题思路使用基于入度的BFS 拓扑排序构建图构建邻接表adj记录每门课的后续课程构建in_degree数组记录每门课的前置条件数量。初始化队列将所有入度为 0无前置依赖的课程加入队列。BFS 模拟修课取出队列中的课算作修完一门。然后将其所有后续课程的入度减 1。若后续课程的入度降为 0说明其前置条件已全部满足加入队列。结果判定最后统计修完的课程数若等于总课数则说明无环可以完成选课。核心代码importcollectionsfromtypingimportListclassSolution:defcanFinish(self,numCourses:int,prerequisites:List[List[int]])-bool:# 1. 初始化邻接表和入度数组adj[[]for_inrange(numCourses)]in_degree[0]*numCoursesfora,binprerequisites:adj[b].append(a)# b - a修 a 需先修 bin_degree[a]1# 2. 收集所有入度为 0 的节点可以直接学的课queuecollections.deque()foriinrange(numCourses):ifin_degree[i]0:queue.append(i)# 3. BFS 模拟选课过程processed0whilequeue:coursequeue.popleft()processed1fornext_courseinadj[course]:in_degree[next_course]-1# 前置条件全部满足可以开始学了ifin_degree[next_course]0:queue.append(next_course)returnprocessednumCourses208. 实现 Trie (前缀树)解题思路根据前述理论构建TrieNode辅助类随后实现树的初始化、插入和查询逻辑。对于startsWith只需路径存在即可返回True无需校验is_end。核心代码classTrieNode:定义 Trie 的节点类def__init__(self):self.children{}# key: 字符, value: 对应的 TrieNodeself.is_endFalse# 标记是否是单词结尾classTrie:def__init__(self):self.rootTrieNode()# 根节点不存储实际字符definsert(self,word:str)-None:current_nodeself.rootforcharinword:# 字符不存在对应分支则创建ifcharnotincurrent_node.children:current_node.children[char]TrieNode()current_nodecurrent_node.children[char]# 单词插入完毕打上结尾标记current_node.is_endTruedefsearch(self,word:str)-bool:current_nodeself.rootforcharinword:ifcharnotincurrent_node.children:returnFalsecurrent_nodecurrent_node.children[char]# 必须是某个完整单词的结尾returncurrent_node.is_enddefstartsWith(self,prefix:str)-bool:current_nodeself.rootforcharinprefix:ifcharnotincurrent_node.children:returnFalsecurrent_nodecurrent_node.children[char]# 只要存在这条路径即可无需判断 is_endreturnTrue