《Hello 算法》图论章节小结精讲图的表示、遍历与时空权衡【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo图是《Hello 算法》数据结构知识体系中自由度最高的一类非线性结构。本篇基于仓库中俄文版 图章节小结 的核心脉络结合 图的基础概念、图的基础操作、图的遍历 与仓库中多语言源码实现系统梳理图的定义与分类、邻接矩阵与邻接表两种表示、BFS/DFS 遍历及其复杂度分析。读完本篇你将掌握图的选型权衡思路并能在实际工程中快速判断该用矩阵还是邻接表该用广度还是深度遍历。图的核心概念与分类顶点、边与集合化定义图graph是一种由**顶点vertex和边edge**组成的非线性数据结构。抽象地看图 $G$ 可以表示为顶点集合 $V$ 与边集合 $E$ 的二元组$$ \begin{aligned} V { 1, 2, 3, 4, 5 } \ E { (1,2), (1,3), (1,5), (2,3), (2,4), (2,5), (4,5) } \ G { V, E } \end{aligned} $$如果将顶点看作节点、边看作连接节点的引用那么图可以视为链表的延伸结构。与线性关系链表和分治关系树相比网络关系图具有更高的自由度因此也更为复杂。三类划分维度根据划分维度不同图有以下常见类型划分维度类型含义典型例子边是否有方向无向图边表示两个顶点之间的双向关系社交网络中的好友关系有向图边具有方向$A \rightarrow B$ 与 $A \leftarrow B$ 相互独立关注/被关注关系顶点是否全部连通连通图任意两个顶点之间都存在可达路径单一连通的地铁网络非连通图至少存在一个顶点从当前顶点不可达多岛屿的航线网络边是否带权重有权图每条边包含权重变量游戏中按共同游戏时长计算的亲密度网络相关基础术语邻接adjacency两个顶点之间存在边则称二者相邻。例如顶点 1 的邻接顶点是 2、3、5。路径path从顶点 A 到顶点 B 经过的边序列。边序列 1-5-2-4 是从顶点 1 到顶点 4 的一条路径。度degree与顶点关联的边数。对于有向图还细分为入度in-degree与出度out-degree。图的两种表示邻接矩阵与邻接表设图中顶点数为 $n$边数为 $m$最常见的两种表示方式如下。邻接矩阵adjacency matrix邻接矩阵用一个 $n \times n$ 的矩阵表示图每一行列对应一个顶点矩阵元素 $M[i, j] 1$ 表示顶点 $V[i]$ 与 $V[j]$ 之间存在边$M[i, j] 0$ 表示无边。邻接矩阵的三个特性简单图中顶点不能与自身相连主对角线元素无意义无向图的边双向等价矩阵关于主对角线对称把 $1/0$ 替换为权重值即可表示有权图。优点直接访问矩阵元素即可获取边信息增删查改操作效率高均为 $O(1)$缺点空间复杂度为 $O(n^2)$内存占用大。仓库中基于邻接矩阵的完整实现见 Python 版 graph_adjacency_matrix.pyC/C/Java/Go 等 16 种语言均有对应实现如 Java 版。从源码可以看到add_vertex需要先加一行、再逐行追加一列graph_adjacency_matrix.py#L35-L45而remove_vertex需要同时删除行列这正是其增删顶点复杂度偏高的原因。邻接表adjacency list邻接表使用 $n$ 个链表表示图第 $i$ 个链表对应顶点 $i$存储该顶点的所有邻接顶点即与该顶点相连的所有顶点。优点只存储实际存在的边通常 $m \ll n^2$因此更节省内存缺点查找边需要遍历链表时间效率低于邻接矩阵。仓库中的实际实现graph_adjacency_list.py相比教科书图示做了两点工程化调整使用**动态数组列表**代替链表简化增删顶点逻辑使用哈希表存储邻接表key为顶点实例value为该顶点的邻接顶点列表顶点使用独立的Vertex类modules/vertex.py而非列表索引这样删除某个顶点时无需更新其余顶点的索引。操作复杂度对比操作邻接矩阵邻接表链表邻接表哈希表判断是否邻接$O(1)$$O(n)$$O(1)$添加边$O(1)$$O(1)$$O(1)$删除边$O(1)$$O(n)$$O(1)$添加顶点$O(n)$$O(1)$$O(1)$删除顶点$O(n^2)$$O(n m)$$O(n)$内存占用$O(n^2)$$O(n m)$$O(n m)$上表来自 图的基础操作 中的效率对比章节。仅看表格似乎邻接表哈希表在时间、空间上都最优但实际工程中邻接矩阵的边操作往往更快——它只需一次数组访问或一次赋值。因此本质上是两种设计哲学的取舍邻接矩阵体现以空间换时间用 $O(n^2)$ 的冗余空间换来了 $O(1)$ 的任意边查询邻接表体现以时间换空间用遍历开销换取只存储真实边的紧凑内存。邻接表的进一步优化邻接表的结构与哈希表的链式地址法非常相似因此可以采用类似的优化手段当某个顶点的邻接链表过长时将其转换为 AVL 树或红黑树将查找边的时间从 $O(n)$ 降到 $O(\log n)$或者转换为哈希表进一步将时间复杂度优化到 $O(1)$。这也是工程中稀疏图用邻接表、稠密图用邻接矩阵经验的底层依据。图的应用场景许多现实系统都可以建模为图并把实际问题归约为图上的计算问题现实系统顶点边图上的计算问题社交网络用户好友关系潜在好友推荐地铁线路站点站点间连通关系最短路线推荐太阳系天体天体间引力作用行星轨道计算树的遍历是图遍历的特例树表示一对多关系图则能表达任意的多对多关系因此树是图的特例树的遍历操作也是图的遍历操作的特例。图的遍历同样分为广度优先遍历BFS与深度优先遍历DFS两种。广度优先遍历BFS由近及远层层扩张BFS 是一种由近及远、层层向外扩张的搜索方式借助队列先进先出的特性实现。算法流程将起始顶点startVet入队并开始循环每轮循环弹出队首顶点并记录访问将其所有邻接顶点加入队尾重复步骤 2直至所有顶点均被访问。为防止重复访问需要借助哈希集合visited记录已访问顶点哈希集合可看作只存key不存value的哈希表增删查均为 $O(1)$。仓库中 Python 实现见 graph_bfs.py核心代码如下def graph_bfs(graph: GraphAdjList, start_vet: Vertex) - list[Vertex]: 广度优先遍历 res [] visited setVertex # 记录已被访问的顶点 que dequeVertex # 队列用于实现 BFS while len(que) 0: vet que.popleft() # 队首顶点出队 res.append(vet) # 记录访问顶点 for adj_vet in graph.adj_list[vet]: if adj_vet in visited: continue # 跳过已被访问的顶点 que.append(adj_vet) # 只入队未访问的顶点 visited.add(adj_vet) # 标记该顶点已被访问 return res时间复杂度所有顶点入队、出队各一次$O(|V|)$无向图中每条边被访问 2 次$O(2|E|)$总计 $O(|V| |E|)$。空间复杂度res、visited、que最坏各容纳 $|V|$ 个顶点$O(|V|)$。深度优先遍历DFS走到底再回溯DFS 是一种优先走到底、无路可走时再回溯的搜索方式走到底再回头的模式通常用递归实现同样借助visited哈希集合避免重复访问。完整实现见 graph_dfs.pydef dfs(graph: GraphAdjList, visited: set[Vertex], res: list[Vertex], vet: Vertex): 深度优先遍历辅助函数 res.append(vet) # 记录访问顶点 visited.add(vet) # 标记该顶点已被访问 for adjVet in graph.adj_list[vet]: if adjVet in visited: continue # 跳过已被访问的顶点 dfs(graph, visited, res, adjVet) # 递归访问邻接顶点 def graph_dfs(graph: GraphAdjList, start_vet: Vertex) - list[Vertex]: 深度优先遍历 res [] visited set[Vertex]() dfs(graph, visited, res, start_vet) return res时间复杂度同样为 $O(|V| |E|)$所有顶点访问 1 次、所有边访问 2 次空间复杂度为 $O(|V|)$res与visited最坏容纳 $|V|$ 个顶点递归最大深度也为 $|V|$。遍历序列是否唯一BFS 序列不唯一BFS 只要求由近及远同一距离层内的多个顶点访问顺序可以任意互换。DFS 序列也不唯一对给定顶点可以向任意方向优先深入邻接顶点的顺序可以任意。以树的遍历类比根→左→右左→根→右左→右→根分别对应先序、中序、后序遍历三者优先级不同但都属于深度优先。章节 Q A 精讲Q1路径的定义是顶点序列还是边序列维基百科不同语言版本定义不一致英文版定义路径为边序列中文/俄文版定义为顶点序列。本书将路径视为边序列而非顶点序列原因在于两个顶点之间可能存在多条边此时每条边都对应一条不同的路径若按顶点序列定义则多条边会被合并为同一条路径无法区分。Q2非连通图中是否有无法遍历到的顶点有。在非连通图中从某个顶点出发至少存在一个顶点不可达。要遍历完整的非连通图需要设置多个起点依次遍历图中的所有连通分量。例如在 章节习题 中顶点集{A, B, C}、{D, E}与{F}各自构成一个连通分量需分别以A、D、F为起点发起三次 BFS 才能遍历全图。这也说明判断两个顶点是否连通必须基于同一个连通分量。Q3邻接表中顶点的存储顺序是否有要求没有强制要求可以是任意顺序。但在实际应用中可能需要按特定规则排序例如按顶点添加的次序或按顶点值的升序排列。这样做的意义在于可以快速查找带有某种极值的顶点。若想临时改变访问顺序也可以借助哈希表或红黑树等结构存储邻接顶点代价是增加部分内存开销。实战自测把理论转化为判断力章节习题 提供了三道典型练习建议按先手算、后编程的方式完成同一张图的两种表示给定无向图顶点A, B, C, D边A-B, A-C, B-C, C-D分别写出邻接表与只含 0/1 的邻接矩阵。结论是判断A与D是否直接相连邻接矩阵只需查看交叉单元格而顶点多、边少时邻接表更省内存。BFS/DFS 遍历顺序给定顶点A, B, C, D, E与边A-B, A-C, B-D, C-D, D-E从A出发按字母序选择邻接顶点BFS 结果为A, B, C, D, EDFS 结果为A, B, D, C, E。由于图中存在环如A-B-D-C-A不标记已访问顶点会导致遍历在环上反复绕行无法终止——这正是visited存在的意义。单次 BFS 能否访问全图若图中还有孤立的边D-E和孤立顶点F从A出发单次 BFS 只能访问{A, B, C}无法触达其他连通分量由此可统计出全图共有 3 个连通分量。配套的编程练习是判断无向图中两顶点间是否存在路径先用edges构建邻接表注意无向边要双向添加再从source出发做 BFS/DFS遇到destination返回true遍历结束未遇到则返回false。该题与 graph_bfs.py 的visited去重思路完全一致可在仓库任一语言目录如 Java 版、Go 版中对照运行验证。小结本章的核心脉络可浓缩为三条主线表示选型邻接矩阵以 $O(n^2)$ 空间换 $O(1)$ 边操作适合稠密图邻接表以遍历开销换紧凑内存适合稀疏图长链表可升级为红黑树或哈希表遍历方法BFS 用队列实现由近及远DFS 用递归实现走到底再回溯两者均需visited去重复杂度同为 $O(|V| |E|)$抽象层级树是图的特例图的建模能力覆盖社交网络、地铁线路等真实系统是后续最短路径、拓扑排序等图算法的基础。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/9/10 21:06:45 · 阅读 1.2k 《Hello 算法》图论章节小结精讲：图的表示、遍历与时空权衡
《Hello 算法》图论章节小结精讲图的表示、遍历与时空权衡【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo图是《Hello 算法》数据结构知识体系中自由度最高的一类非线性结构。本篇基于仓库中俄文版 图章节小结 的核心脉络结合 图的基础概念、图的基础操作、图的遍历 与仓库中多语言源码实现系统梳理图的定义与分类、邻接矩阵与邻接表两种表示、BFS/DFS 遍历及其复杂度分析。读完本篇你将掌握图的选型权衡思路并能在实际工程中快速判断该用矩阵还是邻接表该用广度还是深度遍历。图的核心概念与分类顶点、边与集合化定义图graph是一种由**顶点vertex和边edge**组成的非线性数据结构。抽象地看图 $G$ 可以表示为顶点集合 $V$ 与边集合 $E$ 的二元组$$ \begin{aligned} V { 1, 2, 3, 4, 5 } \ E { (1,2), (1,3), (1,5), (2,3), (2,4), (2,5), (4,5) } \ G { V, E } \end{aligned} $$如果将顶点看作节点、边看作连接节点的引用那么图可以视为链表的延伸结构。与线性关系链表和分治关系树相比网络关系图具有更高的自由度因此也更为复杂。三类划分维度根据划分维度不同图有以下常见类型划分维度类型含义典型例子边是否有方向无向图边表示两个顶点之间的双向关系社交网络中的好友关系有向图边具有方向$A \rightarrow B$ 与 $A \leftarrow B$ 相互独立关注/被关注关系顶点是否全部连通连通图任意两个顶点之间都存在可达路径单一连通的地铁网络非连通图至少存在一个顶点从当前顶点不可达多岛屿的航线网络边是否带权重有权图每条边包含权重变量游戏中按共同游戏时长计算的亲密度网络相关基础术语邻接adjacency两个顶点之间存在边则称二者相邻。例如顶点 1 的邻接顶点是 2、3、5。路径path从顶点 A 到顶点 B 经过的边序列。边序列 1-5-2-4 是从顶点 1 到顶点 4 的一条路径。度degree与顶点关联的边数。对于有向图还细分为入度in-degree与出度out-degree。图的两种表示邻接矩阵与邻接表设图中顶点数为 $n$边数为 $m$最常见的两种表示方式如下。邻接矩阵adjacency matrix邻接矩阵用一个 $n \times n$ 的矩阵表示图每一行列对应一个顶点矩阵元素 $M[i, j] 1$ 表示顶点 $V[i]$ 与 $V[j]$ 之间存在边$M[i, j] 0$ 表示无边。邻接矩阵的三个特性简单图中顶点不能与自身相连主对角线元素无意义无向图的边双向等价矩阵关于主对角线对称把 $1/0$ 替换为权重值即可表示有权图。优点直接访问矩阵元素即可获取边信息增删查改操作效率高均为 $O(1)$缺点空间复杂度为 $O(n^2)$内存占用大。仓库中基于邻接矩阵的完整实现见 Python 版 graph_adjacency_matrix.pyC/C/Java/Go 等 16 种语言均有对应实现如 Java 版。从源码可以看到add_vertex需要先加一行、再逐行追加一列graph_adjacency_matrix.py#L35-L45而remove_vertex需要同时删除行列这正是其增删顶点复杂度偏高的原因。邻接表adjacency list邻接表使用 $n$ 个链表表示图第 $i$ 个链表对应顶点 $i$存储该顶点的所有邻接顶点即与该顶点相连的所有顶点。优点只存储实际存在的边通常 $m \ll n^2$因此更节省内存缺点查找边需要遍历链表时间效率低于邻接矩阵。仓库中的实际实现graph_adjacency_list.py相比教科书图示做了两点工程化调整使用**动态数组列表**代替链表简化增删顶点逻辑使用哈希表存储邻接表key为顶点实例value为该顶点的邻接顶点列表顶点使用独立的Vertex类modules/vertex.py而非列表索引这样删除某个顶点时无需更新其余顶点的索引。操作复杂度对比操作邻接矩阵邻接表链表邻接表哈希表判断是否邻接$O(1)$$O(n)$$O(1)$添加边$O(1)$$O(1)$$O(1)$删除边$O(1)$$O(n)$$O(1)$添加顶点$O(n)$$O(1)$$O(1)$删除顶点$O(n^2)$$O(n m)$$O(n)$内存占用$O(n^2)$$O(n m)$$O(n m)$上表来自 图的基础操作 中的效率对比章节。仅看表格似乎邻接表哈希表在时间、空间上都最优但实际工程中邻接矩阵的边操作往往更快——它只需一次数组访问或一次赋值。因此本质上是两种设计哲学的取舍邻接矩阵体现以空间换时间用 $O(n^2)$ 的冗余空间换来了 $O(1)$ 的任意边查询邻接表体现以时间换空间用遍历开销换取只存储真实边的紧凑内存。邻接表的进一步优化邻接表的结构与哈希表的链式地址法非常相似因此可以采用类似的优化手段当某个顶点的邻接链表过长时将其转换为 AVL 树或红黑树将查找边的时间从 $O(n)$ 降到 $O(\log n)$或者转换为哈希表进一步将时间复杂度优化到 $O(1)$。这也是工程中稀疏图用邻接表、稠密图用邻接矩阵经验的底层依据。图的应用场景许多现实系统都可以建模为图并把实际问题归约为图上的计算问题现实系统顶点边图上的计算问题社交网络用户好友关系潜在好友推荐地铁线路站点站点间连通关系最短路线推荐太阳系天体天体间引力作用行星轨道计算树的遍历是图遍历的特例树表示一对多关系图则能表达任意的多对多关系因此树是图的特例树的遍历操作也是图的遍历操作的特例。图的遍历同样分为广度优先遍历BFS与深度优先遍历DFS两种。广度优先遍历BFS由近及远层层扩张BFS 是一种由近及远、层层向外扩张的搜索方式借助队列先进先出的特性实现。算法流程将起始顶点startVet入队并开始循环每轮循环弹出队首顶点并记录访问将其所有邻接顶点加入队尾重复步骤 2直至所有顶点均被访问。为防止重复访问需要借助哈希集合visited记录已访问顶点哈希集合可看作只存key不存value的哈希表增删查均为 $O(1)$。仓库中 Python 实现见 graph_bfs.py核心代码如下def graph_bfs(graph: GraphAdjList, start_vet: Vertex) - list[Vertex]: 广度优先遍历 res [] visited setVertex # 记录已被访问的顶点 que dequeVertex # 队列用于实现 BFS while len(que) 0: vet que.popleft() # 队首顶点出队 res.append(vet) # 记录访问顶点 for adj_vet in graph.adj_list[vet]: if adj_vet in visited: continue # 跳过已被访问的顶点 que.append(adj_vet) # 只入队未访问的顶点 visited.add(adj_vet) # 标记该顶点已被访问 return res时间复杂度所有顶点入队、出队各一次$O(|V|)$无向图中每条边被访问 2 次$O(2|E|)$总计 $O(|V| |E|)$。空间复杂度res、visited、que最坏各容纳 $|V|$ 个顶点$O(|V|)$。深度优先遍历DFS走到底再回溯DFS 是一种优先走到底、无路可走时再回溯的搜索方式走到底再回头的模式通常用递归实现同样借助visited哈希集合避免重复访问。完整实现见 graph_dfs.pydef dfs(graph: GraphAdjList, visited: set[Vertex], res: list[Vertex], vet: Vertex): 深度优先遍历辅助函数 res.append(vet) # 记录访问顶点 visited.add(vet) # 标记该顶点已被访问 for adjVet in graph.adj_list[vet]: if adjVet in visited: continue # 跳过已被访问的顶点 dfs(graph, visited, res, adjVet) # 递归访问邻接顶点 def graph_dfs(graph: GraphAdjList, start_vet: Vertex) - list[Vertex]: 深度优先遍历 res [] visited set[Vertex]() dfs(graph, visited, res, start_vet) return res时间复杂度同样为 $O(|V| |E|)$所有顶点访问 1 次、所有边访问 2 次空间复杂度为 $O(|V|)$res与visited最坏容纳 $|V|$ 个顶点递归最大深度也为 $|V|$。遍历序列是否唯一BFS 序列不唯一BFS 只要求由近及远同一距离层内的多个顶点访问顺序可以任意互换。DFS 序列也不唯一对给定顶点可以向任意方向优先深入邻接顶点的顺序可以任意。以树的遍历类比根→左→右左→根→右左→右→根分别对应先序、中序、后序遍历三者优先级不同但都属于深度优先。章节 Q A 精讲Q1路径的定义是顶点序列还是边序列维基百科不同语言版本定义不一致英文版定义路径为边序列中文/俄文版定义为顶点序列。本书将路径视为边序列而非顶点序列原因在于两个顶点之间可能存在多条边此时每条边都对应一条不同的路径若按顶点序列定义则多条边会被合并为同一条路径无法区分。Q2非连通图中是否有无法遍历到的顶点有。在非连通图中从某个顶点出发至少存在一个顶点不可达。要遍历完整的非连通图需要设置多个起点依次遍历图中的所有连通分量。例如在 章节习题 中顶点集{A, B, C}、{D, E}与{F}各自构成一个连通分量需分别以A、D、F为起点发起三次 BFS 才能遍历全图。这也说明判断两个顶点是否连通必须基于同一个连通分量。Q3邻接表中顶点的存储顺序是否有要求没有强制要求可以是任意顺序。但在实际应用中可能需要按特定规则排序例如按顶点添加的次序或按顶点值的升序排列。这样做的意义在于可以快速查找带有某种极值的顶点。若想临时改变访问顺序也可以借助哈希表或红黑树等结构存储邻接顶点代价是增加部分内存开销。实战自测把理论转化为判断力章节习题 提供了三道典型练习建议按先手算、后编程的方式完成同一张图的两种表示给定无向图顶点A, B, C, D边A-B, A-C, B-C, C-D分别写出邻接表与只含 0/1 的邻接矩阵。结论是判断A与D是否直接相连邻接矩阵只需查看交叉单元格而顶点多、边少时邻接表更省内存。BFS/DFS 遍历顺序给定顶点A, B, C, D, E与边A-B, A-C, B-D, C-D, D-E从A出发按字母序选择邻接顶点BFS 结果为A, B, C, D, EDFS 结果为A, B, D, C, E。由于图中存在环如A-B-D-C-A不标记已访问顶点会导致遍历在环上反复绕行无法终止——这正是visited存在的意义。单次 BFS 能否访问全图若图中还有孤立的边D-E和孤立顶点F从A出发单次 BFS 只能访问{A, B, C}无法触达其他连通分量由此可统计出全图共有 3 个连通分量。配套的编程练习是判断无向图中两顶点间是否存在路径先用edges构建邻接表注意无向边要双向添加再从source出发做 BFS/DFS遇到destination返回true遍历结束未遇到则返回false。该题与 graph_bfs.py 的visited去重思路完全一致可在仓库任一语言目录如 Java 版、Go 版中对照运行验证。小结本章的核心脉络可浓缩为三条主线表示选型邻接矩阵以 $O(n^2)$ 空间换 $O(1)$ 边操作适合稠密图邻接表以遍历开销换紧凑内存适合稀疏图长链表可升级为红黑树或哈希表遍历方法BFS 用队列实现由近及远DFS 用递归实现走到底再回溯两者均需visited去重复杂度同为 $O(|V| |E|)$抽象层级树是图的特例图的建模能力覆盖社交网络、地铁线路等真实系统是后续最短路径、拓扑排序等图算法的基础。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考