Hello Algo 图数据结构全解邻接矩阵、邻接表与 BFS/DFS 遍历的源码级梳理【免费下载链接】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_adjacency_matrix.py、graph_adjacency_list.py、graph_bfs.py、graph_dfs.py 等 Python 实现代码逐点印证。读完本篇你能完整掌握图的核心概念、两种表示的复杂度差异以及可直接运行的图遍历代码。图的基本构成从链表到网络关系图graph是一种非线性数据结构由顶点vertex和边edge组成可以抽象地表示为一组顶点 $V$ 与一组边 $E$ 构成的集合 $G {V, E}$。例如一个包含 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 中有专门的图示说明也是本章全部内容的出发点。常见图的类型与核心术语按照 graph.md 的划分图有以下几种常见类型有向图与无向图无向图中边表示“双向”连接如微信好友关系有向图中边具有方向性$A \rightarrow B$ 与 $A \leftarrow B$ 是相互独立的如微博“关注”与“被关注”关系。连通图与非连通图连通图中从某个顶点出发可到达其余任意顶点非连通图中从某个顶点出发至少有一个顶点无法到达。有权图与无权图为边添加“权重”变量即得到有权图。例如手游系统根据共同游戏时间计算玩家“亲密度”这种亲密度网络就可以用有权图建模。三个必须记住的术语邻接adjacency两顶点之间若存在边相连称两顶点“邻接”。在上例图中顶点 1 的邻接顶点为 2、3、5。路径path从顶点 A 到顶点 B 经过的边构成的序列。上例中边序列 1-5-2-4 是顶点 1 到顶点 4 的一条路径。度degree一个顶点拥有的边数。对无向图而言顶点 1 的度为 3。有向图中还需区分入度in-degree指向该顶点的边数与出度out-degree从该顶点指出的边数。表示方式一邻接矩阵以空间换时间设图有 $n$ 个顶点邻接矩阵adjacency matrix使用一个 $n \times n$ 的矩阵表示图每一行列代表一个顶点矩阵元素代表边用 $1$ 或 $0$ 表示两顶点之间有边或无边。若邻接矩阵为 $M$、顶点列表为 $V$则 $M[i, j] 1$ 表示顶点 $V[i]$ 到 $V[j]$ 之间存在边$M[i, j] 0$ 表示无边。邻接矩阵有三条重要性质在简单图中顶点不能与自身相连此时主对角线元素没有意义对无向图两个方向的边等价邻接矩阵关于主对角线对称将矩阵元素从 $1$ 和 $0$ 替换为权重即可表示有权图。在 graph_adjacency_matrix.py 中GraphAdjMat类用vertices列表存放顶点值索引即顶点索引、用二维数组adj_mat存放邻接矩阵各操作的实现恰好印证了上述理论查/改边add_edge与remove_edge直接读写矩阵元素并因无向图的对称性同时更新(i, j)与(j, i)两个位置时间复杂度 $O(1)$见 graph_adjacency_matrix.py#L59-L76添加顶点向adj_mat追加一行同时给已有每一行补一列 $0$见 graph_adjacency_matrix.py#L35-L45$O(n)$删除顶点删除一行一列删除首行首列时需将 $(n-1)^2$ 个元素整体移动最差 $O(n^2)$见 graph_adjacency_matrix.py#L47-L57。可以概括为邻接矩阵在增删查改边上效率极高查边恒为 $O(1)$但空间复杂度为 $O(n^2)$内存占用较多。表示方式二邻接表以时间换空间邻接表adjacency list使用 $n$ 个链表表示图第 $i$ 个链表对应顶点 $i$其中存储该顶点的所有邻接顶点。由于它仅存储实际存在的边而边数 $m$ 通常远小于 $n^2$邻接表更节省空间代价是通过遍历链表查找边时间效率不如邻接矩阵。graph_adjacency_list.py 中的GraphAdjList类对理论描述做了两处务实的工程化改造graph_operations.md 对此有专门说明用列表代替链表为了方便增删顶点并简化代码每个顶点的邻接顶点用动态数组Python list存储用哈希表存储邻接表adj_list的key为顶点实例、value为该顶点的邻接顶点列表从而将“定位某个顶点的链表”这一步优化到 $O(1)$以Vertex对象而非索引标识顶点若像邻接矩阵那样用列表索引区分顶点删除索引为 $i$ 的顶点后须遍历全表把更大的索引全部减 1效率很低而每个顶点是唯一的Vertex实例删除时只需清理指向它的边即可见 graph_adjacency_list.py#L54-L63。各操作对应的效率为添加边 $O(1)$链表尾部追加无向图需写两个方向、删除边 $O(m)$需查找链表、添加顶点 $O(1)$、删除顶点 $O(n m)$、初始化 $O(n m)$。两种表示的效率对比与优化思路结合 graph_operations.md 的效率对比表设 $n$ 个顶点、$m$ 条边邻接矩阵邻接表链表邻接表哈希表判断是否邻接$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)$从算法思想角度分析邻接矩阵体现“以空间换时间”邻接表体现“以时间换空间”。表中的“邻接表哈希表”一列看似全面占优但实际工程中对“边”的增删改邻接矩阵只需一次数组赋值常数更小因此两种表示各有适用场景选型取决于图的稠密程度$m$ 相对 $n^2$ 的占比与操作模式。进一步地由于邻接表的链式结构与哈希表中的“链地址法”非常相似当某条链表过长时可以按同样的思路优化将链表转换为 AVL 树或红黑树把查询从 $O(n)$ 提升至 $O(\log n)$或直接换成哈希表降至 $O(1)$。本仓库 graph_adjacency_list.py 采用的正是“哈希表外层 列表内层”的折中方案属于该优化思路的一个落地点。广度优先遍历 BFS由近及远、层层扩张树是图的一种特例因此树的遍历也是图遍历的一种特例。图遍历分 BFS 与 DFS 两种。BFS 是一种由近及远的搜索方式从某顶点出发优先访问距离最近的顶点一层层向外扩张。实现上借助队列——“先入先出”的性质与“由近及远”的思想异曲同工。算法流程为将起始顶点入队每轮迭代弹出队首顶点并记录访问再把该顶点所有未访问的邻接顶点加入队尾重复直到队列为空。为防止重复访问需借助哈希集合visited记录已访问顶点。graph_bfs.py 给出了完整实现deque作为队列、visited在顶点入队时就提前标记避免同一顶点被多个邻居重复入队返回遍历序列resdef graph_bfs(graph: GraphAdjList, start_vet: Vertex) - list[Vertex]: res [] visited setVertex 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复杂度所有顶点入队、出队各一次共 $O(|V|)$无向图中每条边被两侧各访问一次共 $O(2|E|)$故时间复杂度 $O(|V| |E|)$res、visited、que中顶点数最多 $|V|$空间复杂度 $O(|V|)$。需要说明的是BFS 序列并非唯一只要保持“由近及远”的层次顺序同一层内各顶点的先后可以任意交换。深度优先遍历 DFS优先走到底、无路再回头DFS 是一种优先走到底、无路可走时再回溯的搜索方式通常基于递归来实现访问当前顶点的某个邻接顶点走到尽头后返回再继续探索直至所有顶点访问完毕。同样需要visited集合避免重复访问。graph_dfs.py 的实现非常简洁——外层graph_dfs负责初始化res与visited并启动递归内层dfs每进入一个顶点就“记录 标记 向未访问邻居递推”def 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复杂度与 BFS 相同每个顶点访问 1 次共 $O(|V|)$无向图中每条边被访问 2 次共 $O(2|E|)$时间复杂度 $O(|V| |E|)$res与visited各至多 $|V|$递归调用栈深度最大 $|V|$空间复杂度 $O(|V|)$。与 BFS 一样DFS 序列也不唯一——给定某顶点先往哪个方向探索都可以邻接顶点的顺序可以任意打乱树的“根左右/左右根/左根右”三种序本质上都是深度优先遍历。图的常见应用图可用于建模各类现实系统相应问题可约化为图计算问题引自 graph.md 的应用表顶点边图计算问题社交网络用户好友关系潜在好友推荐地铁线路站点站点间的连通性最短路线推荐太阳系星体星体间的万有引力作用行星轨道计算重点回顾三个高频 Q AQ1路径的定义是顶点序列还是边序列维基百科不同语言版本定义不一致英文版是“路径是一个边序列”中文版是“路径是一个顶点序列”。英文版原文为In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices.在《Hello 算法》中路径被视为边序列而非顶点序列原因是两个顶点之间可能存在多条边连接此时每条边都对应一条独立的路径——若以顶点序列定义将无法区分这些不同的边。Q2非连通图中是否会有无法遍历到的点会。在非连通图中从某个顶点出发至少有一个顶点无法到达。遍历非连通图需要设置多个起点以遍历到图的所有连通分量。对照上面的 BFS/DFS 代码可以看出两者均只从单个start_vet出发while len(que) 0或递归结束时队列/栈为空对非连通图需要对每个尚未访问的顶点各启动一次遍历直到visited覆盖全部顶点。Q3邻接表中“与该顶点相连的所有顶点”的顺序是否有要求可以是任意顺序。但在实际应用中可能需要按指定规则排序比如按顶点添加的次序、或按顶点值大小排序这样有助于快速查找“带有某种极值”的顶点例如最短路算法中反复取“最小距离”顶点时的加速。从源码结构看GraphAdjList.add_edge以追加方式维护列表graph_adjacency_list.py#L31-L37因此默认顺序即边的添加顺序这本身就是一种可用的“极值友好”排序。小结本章内容可以压缩为一张“心智地图”图 顶点集合 边集合是链表与树的自由度扩展有向/连通/有权是三个正交的修饰维度邻接矩阵 $O(1)$ 查边、$O(n^2)$ 空间以空间换时间邻接表 $O(n m)$ 空间、查边需遍历以时间换空间且可沿“链地址法”思路升级为红黑树或哈希表BFS 用队列实现由近及远、DFS 用递归实现走到底再回头二者复杂度均为 $O(|V| |E|)$ 时间、$O(|V|)$ 空间且都依赖visited集合去重树是图的特例树的遍历是图遍历的特例——掌握图遍历即同时掌握了树的遍历。全部讲解与可运行代码Python 版另含 C/C/Java/Go/JS/TS 等十余种语言的平行实现可在 codes/chapter_graph/ 与 docs/chapter_graph/ 中查看直接执行对应脚本即可复现文中的遍历序列输出。【免费下载链接】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），仅供参考
Hello Algo 图数据结构全解：邻接矩阵、邻接表与 BFS/DFS 遍历的源码级梳理
Hello Algo 图数据结构全解邻接矩阵、邻接表与 BFS/DFS 遍历的源码级梳理【免费下载链接】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_adjacency_matrix.py、graph_adjacency_list.py、graph_bfs.py、graph_dfs.py 等 Python 实现代码逐点印证。读完本篇你能完整掌握图的核心概念、两种表示的复杂度差异以及可直接运行的图遍历代码。图的基本构成从链表到网络关系图graph是一种非线性数据结构由顶点vertex和边edge组成可以抽象地表示为一组顶点 $V$ 与一组边 $E$ 构成的集合 $G {V, E}$。例如一个包含 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 中有专门的图示说明也是本章全部内容的出发点。常见图的类型与核心术语按照 graph.md 的划分图有以下几种常见类型有向图与无向图无向图中边表示“双向”连接如微信好友关系有向图中边具有方向性$A \rightarrow B$ 与 $A \leftarrow B$ 是相互独立的如微博“关注”与“被关注”关系。连通图与非连通图连通图中从某个顶点出发可到达其余任意顶点非连通图中从某个顶点出发至少有一个顶点无法到达。有权图与无权图为边添加“权重”变量即得到有权图。例如手游系统根据共同游戏时间计算玩家“亲密度”这种亲密度网络就可以用有权图建模。三个必须记住的术语邻接adjacency两顶点之间若存在边相连称两顶点“邻接”。在上例图中顶点 1 的邻接顶点为 2、3、5。路径path从顶点 A 到顶点 B 经过的边构成的序列。上例中边序列 1-5-2-4 是顶点 1 到顶点 4 的一条路径。度degree一个顶点拥有的边数。对无向图而言顶点 1 的度为 3。有向图中还需区分入度in-degree指向该顶点的边数与出度out-degree从该顶点指出的边数。表示方式一邻接矩阵以空间换时间设图有 $n$ 个顶点邻接矩阵adjacency matrix使用一个 $n \times n$ 的矩阵表示图每一行列代表一个顶点矩阵元素代表边用 $1$ 或 $0$ 表示两顶点之间有边或无边。若邻接矩阵为 $M$、顶点列表为 $V$则 $M[i, j] 1$ 表示顶点 $V[i]$ 到 $V[j]$ 之间存在边$M[i, j] 0$ 表示无边。邻接矩阵有三条重要性质在简单图中顶点不能与自身相连此时主对角线元素没有意义对无向图两个方向的边等价邻接矩阵关于主对角线对称将矩阵元素从 $1$ 和 $0$ 替换为权重即可表示有权图。在 graph_adjacency_matrix.py 中GraphAdjMat类用vertices列表存放顶点值索引即顶点索引、用二维数组adj_mat存放邻接矩阵各操作的实现恰好印证了上述理论查/改边add_edge与remove_edge直接读写矩阵元素并因无向图的对称性同时更新(i, j)与(j, i)两个位置时间复杂度 $O(1)$见 graph_adjacency_matrix.py#L59-L76添加顶点向adj_mat追加一行同时给已有每一行补一列 $0$见 graph_adjacency_matrix.py#L35-L45$O(n)$删除顶点删除一行一列删除首行首列时需将 $(n-1)^2$ 个元素整体移动最差 $O(n^2)$见 graph_adjacency_matrix.py#L47-L57。可以概括为邻接矩阵在增删查改边上效率极高查边恒为 $O(1)$但空间复杂度为 $O(n^2)$内存占用较多。表示方式二邻接表以时间换空间邻接表adjacency list使用 $n$ 个链表表示图第 $i$ 个链表对应顶点 $i$其中存储该顶点的所有邻接顶点。由于它仅存储实际存在的边而边数 $m$ 通常远小于 $n^2$邻接表更节省空间代价是通过遍历链表查找边时间效率不如邻接矩阵。graph_adjacency_list.py 中的GraphAdjList类对理论描述做了两处务实的工程化改造graph_operations.md 对此有专门说明用列表代替链表为了方便增删顶点并简化代码每个顶点的邻接顶点用动态数组Python list存储用哈希表存储邻接表adj_list的key为顶点实例、value为该顶点的邻接顶点列表从而将“定位某个顶点的链表”这一步优化到 $O(1)$以Vertex对象而非索引标识顶点若像邻接矩阵那样用列表索引区分顶点删除索引为 $i$ 的顶点后须遍历全表把更大的索引全部减 1效率很低而每个顶点是唯一的Vertex实例删除时只需清理指向它的边即可见 graph_adjacency_list.py#L54-L63。各操作对应的效率为添加边 $O(1)$链表尾部追加无向图需写两个方向、删除边 $O(m)$需查找链表、添加顶点 $O(1)$、删除顶点 $O(n m)$、初始化 $O(n m)$。两种表示的效率对比与优化思路结合 graph_operations.md 的效率对比表设 $n$ 个顶点、$m$ 条边邻接矩阵邻接表链表邻接表哈希表判断是否邻接$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)$从算法思想角度分析邻接矩阵体现“以空间换时间”邻接表体现“以时间换空间”。表中的“邻接表哈希表”一列看似全面占优但实际工程中对“边”的增删改邻接矩阵只需一次数组赋值常数更小因此两种表示各有适用场景选型取决于图的稠密程度$m$ 相对 $n^2$ 的占比与操作模式。进一步地由于邻接表的链式结构与哈希表中的“链地址法”非常相似当某条链表过长时可以按同样的思路优化将链表转换为 AVL 树或红黑树把查询从 $O(n)$ 提升至 $O(\log n)$或直接换成哈希表降至 $O(1)$。本仓库 graph_adjacency_list.py 采用的正是“哈希表外层 列表内层”的折中方案属于该优化思路的一个落地点。广度优先遍历 BFS由近及远、层层扩张树是图的一种特例因此树的遍历也是图遍历的一种特例。图遍历分 BFS 与 DFS 两种。BFS 是一种由近及远的搜索方式从某顶点出发优先访问距离最近的顶点一层层向外扩张。实现上借助队列——“先入先出”的性质与“由近及远”的思想异曲同工。算法流程为将起始顶点入队每轮迭代弹出队首顶点并记录访问再把该顶点所有未访问的邻接顶点加入队尾重复直到队列为空。为防止重复访问需借助哈希集合visited记录已访问顶点。graph_bfs.py 给出了完整实现deque作为队列、visited在顶点入队时就提前标记避免同一顶点被多个邻居重复入队返回遍历序列resdef graph_bfs(graph: GraphAdjList, start_vet: Vertex) - list[Vertex]: res [] visited setVertex 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复杂度所有顶点入队、出队各一次共 $O(|V|)$无向图中每条边被两侧各访问一次共 $O(2|E|)$故时间复杂度 $O(|V| |E|)$res、visited、que中顶点数最多 $|V|$空间复杂度 $O(|V|)$。需要说明的是BFS 序列并非唯一只要保持“由近及远”的层次顺序同一层内各顶点的先后可以任意交换。深度优先遍历 DFS优先走到底、无路再回头DFS 是一种优先走到底、无路可走时再回溯的搜索方式通常基于递归来实现访问当前顶点的某个邻接顶点走到尽头后返回再继续探索直至所有顶点访问完毕。同样需要visited集合避免重复访问。graph_dfs.py 的实现非常简洁——外层graph_dfs负责初始化res与visited并启动递归内层dfs每进入一个顶点就“记录 标记 向未访问邻居递推”def 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复杂度与 BFS 相同每个顶点访问 1 次共 $O(|V|)$无向图中每条边被访问 2 次共 $O(2|E|)$时间复杂度 $O(|V| |E|)$res与visited各至多 $|V|$递归调用栈深度最大 $|V|$空间复杂度 $O(|V|)$。与 BFS 一样DFS 序列也不唯一——给定某顶点先往哪个方向探索都可以邻接顶点的顺序可以任意打乱树的“根左右/左右根/左根右”三种序本质上都是深度优先遍历。图的常见应用图可用于建模各类现实系统相应问题可约化为图计算问题引自 graph.md 的应用表顶点边图计算问题社交网络用户好友关系潜在好友推荐地铁线路站点站点间的连通性最短路线推荐太阳系星体星体间的万有引力作用行星轨道计算重点回顾三个高频 Q AQ1路径的定义是顶点序列还是边序列维基百科不同语言版本定义不一致英文版是“路径是一个边序列”中文版是“路径是一个顶点序列”。英文版原文为In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices.在《Hello 算法》中路径被视为边序列而非顶点序列原因是两个顶点之间可能存在多条边连接此时每条边都对应一条独立的路径——若以顶点序列定义将无法区分这些不同的边。Q2非连通图中是否会有无法遍历到的点会。在非连通图中从某个顶点出发至少有一个顶点无法到达。遍历非连通图需要设置多个起点以遍历到图的所有连通分量。对照上面的 BFS/DFS 代码可以看出两者均只从单个start_vet出发while len(que) 0或递归结束时队列/栈为空对非连通图需要对每个尚未访问的顶点各启动一次遍历直到visited覆盖全部顶点。Q3邻接表中“与该顶点相连的所有顶点”的顺序是否有要求可以是任意顺序。但在实际应用中可能需要按指定规则排序比如按顶点添加的次序、或按顶点值大小排序这样有助于快速查找“带有某种极值”的顶点例如最短路算法中反复取“最小距离”顶点时的加速。从源码结构看GraphAdjList.add_edge以追加方式维护列表graph_adjacency_list.py#L31-L37因此默认顺序即边的添加顺序这本身就是一种可用的“极值友好”排序。小结本章内容可以压缩为一张“心智地图”图 顶点集合 边集合是链表与树的自由度扩展有向/连通/有权是三个正交的修饰维度邻接矩阵 $O(1)$ 查边、$O(n^2)$ 空间以空间换时间邻接表 $O(n m)$ 空间、查边需遍历以时间换空间且可沿“链地址法”思路升级为红黑树或哈希表BFS 用队列实现由近及远、DFS 用递归实现走到底再回头二者复杂度均为 $O(|V| |E|)$ 时间、$O(|V|)$ 空间且都依赖visited集合去重树是图的特例树的遍历是图遍历的特例——掌握图遍历即同时掌握了树的遍历。全部讲解与可运行代码Python 版另含 C/C/Java/Go/JS/TS 等十余种语言的平行实现可在 codes/chapter_graph/ 与 docs/chapter_graph/ 中查看直接执行对应脚本即可复现文中的遍历序列输出。【免费下载链接】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），仅供参考
