Hello Algo 图论章节核心总结：图的表示、遍历与常见疑问全解-编程实验室

Hello Algo 图论章节核心总结：图的表示、遍历与常见疑问全解

【免费下载链接】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 Algo《图》章节的收官总结页（源文档），它不引入新算法，而是把图的术语、两种存储表示（邻接矩阵与邻接表）以及广度优先/深度优先遍历的核心结论压缩成可快速回查的知识清单，并用一问一答的形式澄清三个最易混淆的细节。读完本文，你将能把全书图相关概念串成一条线，并在面试与刷题时快速调用「该用什么结构存储图、该选 BFS 还是 DFS、遍历序列是否唯一」这类判断依据。

图的本质：从线性、树到网络关系

图由顶点（vertex）与边（edge）构成，可抽象地记为集合V（顶点集）与集合E（边集）的组合G = {V, E}。Hello Algo 用一个包含 5 个顶点、7 条边的示例图给出了形式化定义，例如V = {1,2,3,4,5}、E = {(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(4,5)}，详见 graph.md。

理解图的关键视角是把它当作链表的推广：

链表刻画的是线性（一对一）关系，数据像链条一样顺序相连；
树刻画的是分治（一对多）关系，一个父节点下挂多个子节点；
图刻画的则是网络（多对多）关系，任意顶点之间都可能存在边，自由度最高，因此也最复杂。

把顶点看成节点、把边看成连接节点之间的引用（指针），图就是链表的自然延伸。正因如此，树可以被视为图的一种特例，树的遍历也可以视为图遍历的特例——这两个论断在本章总结中反复出现，是理解图遍历（尤其是 DFS）的钥匙。

基础术语速查

无向图 / 有向图：边是否有方向。无向图的边表示两个顶点之间的「双向」连接（如微信好友关系）；有向图中边A→B与A←B相互独立（如微博的关注关系）。
连通图 / 非连通图：按顶点之间是否全部可达划分。连通图从任一顶点出发都能到达其余全部顶点；非连通图则至少存在一个顶点无法从某个起点到达。
有权图：在边上附加「权重」变量，例如游戏系统根据玩家共同游玩时长计算的「亲密度」网络。
邻接（adjacency）：两个顶点由一条边相连，则称二者相邻。
路径（path）：从顶点 A 到顶点 B 的边序列。例如边序列1-5-2-4就是从顶点 1 到顶点 4 的一条路径。
度（degree）：顶点拥有的边数；对有向图进一步分为入度（指向该顶点的边数）与出度（从该顶点出发的边数）。

图的现实应用

很多现实系统都能建模成图，并把实际问题归约为图计算问题（表见 graph.md）：

现实系统	顶点	边	可归约的图计算问题
社交网络	用户	好友关系	潜在好友推荐
地铁线路	站点	站点之间的连通	最短路线推荐
太阳系	天体	天体间的引力	行星轨道计算

图的两种存储表示：邻接矩阵与邻接表

图的常见表示方法有两种：邻接矩阵与邻接表，二者是本章总结的核心对比点。以下以无向图为例展开（完整讲解与配图见 graph_operations.md）。

邻接矩阵（Adjacency Matrix）

对于含n个顶点的图，邻接矩阵使用n × n的矩阵表示图：每行（列）对应一个顶点，矩阵元素表示边，用1或0指示两顶点之间是否存在边。设邻接矩阵为M、顶点列表为V，则M[i, j] = 1表示顶点V[i]与V[j]之间有边，0表示无边。

其性质包括：

简单图中顶点不能连接自身，因此邻接矩阵主对角线上的元素无意义；
无向图中两个方向的边等价，故邻接矩阵关于主对角线对称；
把矩阵中的0/1替换为权重，邻接矩阵即可表示有权图。

优缺点：可直接通过下标访问矩阵元素，增删查改操作都达到O(1)时间复杂度；但矩阵的空间复杂度为O(n²)，顶点较多时内存消耗显著。C 语言实现可参考 graph_adjacency_matrix.c：该文件用Vertex数组保存顶点、用adjMat[MAX_SIZE][MAX_SIZE]保存矩阵，构造函数在初始化时逐格清零，新增顶点时向size索引处追加行与列——与教科书上的理论步骤一一对应。

邻接表（Adjacency List）

邻接表用多条链表表示图，链表节点代表顶点：第i条链表对应顶点i，存储该顶点的全部邻接顶点。与邻接矩阵相比，邻接表只存储实际存在的边，而总边数通常远小于n²，因此更省空间；缺点是查边需要遍历链表，时间效率不如邻接矩阵的O(1)直达。

从结构上看，邻接表与哈希表的「链式地址」非常相似，因此可以借鉴同样的优化手段：当链表过长时，将其转换为 AVL 树或红黑树，把查询复杂度从O(n)降到O(log n)；也可转换为哈希表，进一步把复杂度降到O(1)。这正是本章总结中强调的「提高查找效率」的可行路径。

Hello Algo 的代码实现在细节上做了两处工程化改造（见 graph_operations.md）：

为便于增删顶点、简化代码，用列表（动态数组）取代链表；
用哈希表存储邻接表：key为顶点实例，value是该顶点的邻接顶点列表（链表）。

此外，代码使用Vertex类来表示顶点而非用列表下标区分顶点。原因是：若用下标区分，删除下标i的顶点时需要遍历整张邻接表并把所有大于i的下标减一，效率很低；而每个顶点是唯一的Vertex实例时，删除一个顶点无需改动其他顶点。C 实现可参考 graph_adjacency_list.c。

效率对比表

设图有n个顶点、m条边，下表（出自 graph_operations.md）对比两种结构以及「邻接表全部换用哈希表」形态的效率：

操作	邻接矩阵	邻接表（链表）	邻接表（哈希表）
判断是否邻接	`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²)`	`O(n + m)`	`O(n)`
内存空间占用	`O(n²)`	`O(n + m)`	`O(n + m)`

单看表格，邻接表（哈希表）似乎时间、空间效率都占优，但实践中对边的操作在邻接矩阵上只涉及一次数组访问或赋值，常数因子更小。因此本章总结给出一个精辟的宏观结论：邻接矩阵体现「以空间换时间」，邻接表体现「以时间换空间」。选择哪种存储方式，本质是在顶点规模、内存预算与操作频率之间做权衡。

图的遍历：广度优先（BFS）与深度优先（DFS）

图遍历必须借助搜索算法完成，与树的遍历一脉相承。Hello Algo 把图遍历分为广度优先与深度优先两类，细节与分步配图见 graph_traversal.md。

广度优先搜索：队列驱动的「由近及远」

广度优先搜索从近处向远处推进：从给定节点出发，总是先访问距离最近的顶点，再逐层向外扩张。它通常借助队列实现：队列「先进先出」的特性恰好契合「由近及远」的遍历思路。

算法步骤为：先把起始顶点startVet入队并开始循环；每轮循环弹出队首顶点并记录为已访问，再将该顶点的所有邻接顶点加入队尾；重复直到所有顶点均被访问。为了防止重复访问，还需要一个哈希集合visited记录已访问顶点——哈希集合可看作只存key不存value的哈希表，能在O(1)时间内完成插入、删除、查找，常用于去重场景。

以 Python 实现为例，其核心循环（见 graph_bfs.py）非常清晰：

def graph_bfs(graph: GraphAdjList, start_vet: Vertex) -> list[Vertex]: # 顶点遍历序列 res = [] # 哈希集合，记录已访问顶点 visited = setVertex # 队列，用于实现 BFS que = dequeVertex 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 # 返回顶点遍历序列

从源码结构看，Python 版用deque充当队列，visited使用内置set，遍历邻接顶点时直接读取graph.adj_list[vet]；C 语言版则手工实现了一个环形队列（见 graph_bfs.c），因 C 没有现成哈希集合，isVisited通过线性扫描visited数组完成，这一实现差异也印证了不同语言在数据结构选型上的取舍。

复杂度分析：所有顶点都会入队、出队一次，耗时O(|V|)；遍历邻接顶点的过程中，无向图的所有边会被访问 2 次，耗时O(2|E|)；总时间复杂度为O(|V| + |E|)。空间上，结果列表res、哈希集合visited与队列que最多容纳|V|个顶点，空间复杂度O(|V|)。

一个易错点：广度优先遍历序列不唯一。BFS 只要求按「由近及远」的顺序遍历，同一距离层内的顶点访问顺序可以任意打乱——例如参考图中顶点 1 与 3 的访问次序可以互换，顶点 2、4、6 同理。

深度优先搜索：递归驱动的「走到底再回溯」

深度优先搜索优先「一条路走到黑」，走不通再回溯：从起点开始访问当前顶点的一个邻接顶点，不断深入直到死胡同，然后返回、继续深入、再返回，如此往复直到遍历完所有顶点。

这种「能进则进，不能进则退」的范式天然适合用递归实现。与 BFS 类似，DFS 也需要visited哈希集合避免走回头路。在递归过程中：竖直虚线表示向下递归（发起新调用访问新顶点），弯曲虚线表示向上回溯（本次递归调用返回到发起点）。Hello Algo 建议将分步图与代码对照，在脑中推演每一次递归的发起与返回时刻。

深度优先的遍历序列同样不唯一：给定一个顶点，先探索哪个方向都可以，即邻接顶点的顺序可以任意重排。以树的遍历为例，「根→左→右」「左→根→右」「左→右→根」分别对应前序、中序、后序遍历——它们是三种不同的遍历优先级，但同属深度优先搜索。

复杂度分析：所有顶点被访问 1 次、所有边被访问 2 次，总时间复杂度O(|V| + |E|)；空间上列表res与集合visited最多容纳|V|个顶点，且最大递归深度为|V|，空间复杂度O(|V|)。

三个高频疑问的权威解答

总结页以 Q&A 形式收录了读者最常提出的三个问题，这里完整转述并补充背景：

Q1：路径（path）究竟是「顶点序列」还是「边序列」？

不同语言版本的 Wikipedia 定义不一致：英文版把路径定义为「边的序列」，中文版则定义为「顶点的序列」（英文原文为"In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices"）。Hello Algo 的正文约定把路径视为边的序列而非顶点的序列，原因是：两个顶点之间可能存在多条边，此时每一条边都对应一条路径；若按顶点序列定义，就无法区分这些不同的路径。

Q2：在非连通图中，一定会存在不可达的顶点吗？

是。在非连通图中，从某个顶点出发，至少存在一个其他顶点无法到达。因此要遍历非连通图，需要多个起点，分别覆盖每一个连通分量。这与 graph.md 中「连通图从任一点出发可达全部顶点」的定义互为补充——也解释了为什么遍历算法通常只保证覆盖起点所在的连通分量，实际工程中遍历整个非连通图时需要在外层套循环枚举所有未访问起点。

Q3：邻接表中某个顶点的邻接顶点列表是否必须有序？

没有强制顺序，它们可以以任意顺序出现。但在工程实践中，可能需要按特定规则排序，例如按顶点的加入顺序或按顶点值的大小排序，这样有助于快速查找具有某个极值的顶点（如最值、最新加入等），属于基于查询需求的自选优化。

小结：快速记忆框架

图 = 顶点集 + 边集，是链表（线性）与树（分治）之上的**网络（多对多）**关系，树是图的特例；
有向/无向看边的方向，连通/非连通看可达性，加权图给边附加权重；
邻接矩阵：O(1)改查、O(n²)空间，无向图对称、主对角线无意义，本质「以空间换时间」；
邻接表：省空间、查边慢，链表过长可升级为红黑树（O(log n)）或哈希表（O(1)），本质「以时间换空间」；
BFS用队列、由近及远逐层展开；DFS用递归、走到底再回溯；二者都用visited防重，复杂度同为O(|V| + |E|)，且遍历序列都不唯一；
非连通图需要多个起点才能遍历全部连通分量；路径定义为边序列可区分两顶点间的多条边。