Python图遍历全解析：邻接矩阵与邻接表的DFS/BFS递归与非递归实现

1. 为什么图的遍历值得反复琢磨图的遍历是数据结构里少数几个看起来简单、写起来全是坑的知识点。我见过太多人背下了邻接矩阵和邻接表的定义也能默写出DFS的递归模板但一旦要求用非递归方式实现、或者要求同时输出遍历序列和路径信息代码就开始出问题。更常见的情况是面试时被问到为什么BFS能求最短路径而DFS不行脑子里只有模糊的印象说不出所以然。这篇文章围绕一个核心目标展开用Python把图的两种存储结构邻接矩阵、邻接表和两种遍历方式DFS、BFS的递归与非递归实现全部打通。不管你是正在准备考试的学生还是工作中需要处理图结构数据的开发者又或者只是想把这块基础知识彻底夯实的人下面的内容都能直接拿来参考和复现。我自己的经验是图的遍历真正难的不是写出一段能跑的代码而是理解每种实现方式背后的取舍——什么时候用矩阵、什么时候用表、递归和非递归各自适合什么场景、BFS和DFS分别能解决什么类型的问题。这些判断力不是靠背模板能获得的必须自己动手把每种组合都跑一遍观察输出结果对比差异才能形成直觉。接下来的内容会按照存储结构→遍历算法→递归与非递归对比→常见问题排查的顺序展开每个环节都附带可直接运行的Python代码和详细的注释说明。代码不会追求炫技式的简洁而是优先保证可读性和可调试性方便你在此基础上修改和扩展。2. 图的两种存储结构邻接矩阵与邻接表2.1 邻接矩阵的构建逻辑与适用场景邻接矩阵的本质是一个二维数组。假设图中有n个顶点就用一个n×n的矩阵来表示顶点之间的连接关系。矩阵中第i行第j列的值表示顶点i到顶点j是否有边对于无权图用0和1表示对于带权图用具体的权值或者一个特殊标记比如无穷大表示不连通。这种表示方式最大的优点是直观。你想知道两个顶点之间有没有边直接查矩阵对应位置就行时间复杂度是O(1)。在Python里用嵌套列表就能实现class GraphMatrix: def __init__(self, num_vertices, directedFalse): self.num_vertices num_vertices self.directed directed # 初始化全零矩阵 self.matrix [[0] * num_vertices for _ in range(num_vertices)] def add_edge(self, u, v, weight1): self.matrix[u][v] weight if not self.directed: self.matrix[v][u] weight def has_edge(self, u, v): return self.matrix[u][v] ! 0 def get_neighbors(self, u): 返回顶点u的所有邻接顶点 neighbors [] for v in range(self.num_vertices): if self.matrix[u][v] ! 0: neighbors.append(v) return neighbors这段代码里有个细节值得注意初始化矩阵时用了[[0] * n for _ in range(n)]而不是[[0] * n] * n。后者看起来更简洁但它创建的是n个指向同一个列表的引用修改任意一行都会影响所有行。这个坑我在早期写代码时踩过不止一次排查了半天才发现问题出在初始化上。邻接矩阵的缺点也很明显。如果图是稀疏的边数远小于n²矩阵里大量的0就是浪费。假设一个图有1000个顶点但只有2000条边用邻接矩阵需要存储100万个元素而实际有效的不到0.4%。另外获取某个顶点的所有邻接顶点时即使该顶点只有少数几个邻居也必须扫描整行时间复杂度是O(n)。所以邻接矩阵适合的场景是顶点数量不大、图比较稠密、或者需要频繁判断任意两个顶点之间是否有边。比如在Floyd-Warshall最短路径算法中邻接矩阵就是天然的存储结构。2.2 邻接表的构建逻辑与适用场景邻接表换了一个思路不为不存在的边浪费空间。它用一个列表或字典来存储每个顶点的邻居集合。在Python里最自然的实现方式是用字典套列表class GraphList: def __init__(self, directedFalse): self.directed directed self.adj {} # 字典顶点 - 邻居列表 def add_vertex(self, v): if v not in self.adj: self.adj[v] [] def add_edge(self, u, v, weight1): self.add_vertex(u) self.add_vertex(v) self.adj[u].append((v, weight)) if not self.directed: self.adj[v].append((u, weight)) def get_neighbors(self, u): return self.adj.get(u, [])邻接表的空间复杂度是O(VE)V是顶点数E是边数。对于稀疏图来说这比邻接矩阵的O(V²)要高效得多。获取某个顶点的邻居时只需要遍历该顶点对应的列表时间复杂度是O(degree(u))degree是顶点的度数。但邻接表也有代价。判断两个顶点之间是否有边需要遍历其中一个顶点的邻居列表最坏情况下是O(V)。如果这个操作很频繁邻接表就不如矩阵方便。另外邻接表的实现方式更灵活可以用列表、字典、甚至集合来存储邻居不同选择会影响操作的效率。比如用集合存储邻居判断边是否存在就变成了O(1)但会丢失边的顺序信息。我在实际项目中的选择习惯是这样的如果图的规模在几百个顶点以内两种结构差别不大优先用邻接矩阵因为代码更简单、不容易出错如果顶点数上千或者图明显稀疏果断用邻接表。如果需要在遍历过程中频繁判断边是否存在可以考虑邻接表加一个辅助的集合来加速查询。2.3 两种结构的转换与选择建议有时候我们需要在两种结构之间转换。比如输入数据给的是邻接矩阵但算法内部用邻接表更方便。转换的逻辑很直接def matrix_to_list(matrix): n len(matrix) graph GraphList() for i in range(n): graph.add_vertex(i) for i in range(n): for j in range(n): if matrix[i][j] ! 0: graph.add_edge(i, j, matrix[i][j]) return graph def list_to_matrix(graph, num_vertices): matrix [[0] * num_vertices for _ in range(num_vertices)] for u in graph.adj: for v, w in graph.adj[u]: matrix[u][v] w return matrix选择哪种结构我的判断标准是看三个因素图的规模、图的稠密程度、以及主要操作类型。下面这个表格可以帮你快速决策考量因素邻接矩阵邻接表空间复杂度O(V²)O(VE)判断边是否存在O(1)O(degree)获取所有邻居O(V)O(degree)添加边O(1)O(1)适合的图类型稠密图稀疏图实现难度低中等注意如果你的图顶点数超过1000且边数远小于V²不要犹豫直接用邻接表。我见过有人用邻接矩阵处理上万个顶点的稀疏图程序跑起来内存直接爆掉。3. 深度优先搜索DFS的递归与非递归实现3.1 递归版DFS最直观但最容易栈溢出DFS的核心思想是一条路走到黑走不通再回头。递归实现几乎是对这个思想的直接翻译def dfs_recursive(graph, start, visitedNone): if visited is None: visited set() visited.add(start) result [start] for neighbor in graph.get_neighbors(start): # 邻接表返回的是(v, weight)元组需要取第一个元素 v neighbor[0] if isinstance(neighbor, tuple) else neighbor if v not in visited: result.extend(dfs_recursive(graph, v, visited)) return result这段代码的逻辑很清晰访问当前顶点标记为已访问然后递归访问所有未访问的邻居。visited集合用来防止重复访问这是DFS能正确终止的关键。递归版DFS的优点是代码简洁、容易理解。但它的缺点也很致命递归深度受限于Python的调用栈大小。Python默认的递归深度限制是1000层左右虽然可以用sys.setrecursionlimit()调大但调得太大可能导致栈溢出崩溃。如果一个图有上万个顶点且形成一条长链递归版DFS几乎必然出问题。我实测过在默认设置下递归深度超过900左右就会抛出RecursionError。所以如果你的图规模不确定或者可能包含长路径非递归版本是更稳妥的选择。3.2 非递归版DFS用栈模拟递归过程把递归改成非递归核心是用一个显式的栈来模拟函数调用栈。这里有一个容易出错的细节入栈的顺序。def dfs_iterative(graph, start): visited set() stack [start] result [] while stack: vertex stack.pop() if vertex not in visited: visited.add(vertex) result.append(vertex) # 将邻居逆序入栈保证出栈顺序与递归版一致 neighbors graph.get_neighbors(vertex) for neighbor in reversed(neighbors): v neighbor[0] if isinstance(neighbor, tuple) else neighbor if v not in visited: stack.append(v) return result为什么要把邻居逆序入栈因为栈是后进先出LIFO的结构。如果按顺序把邻居压入栈出栈时顺序就反了。逆序入栈可以保证出栈顺序和递归版的遍历顺序一致。这个细节很多人不注意导致非递归版和递归版的输出结果不一样调试时一头雾水。还有一个常见的写法是在入栈时就标记visited而不是出栈时标记。这两种写法都能工作但行为略有不同。出栈时标记更接近递归版的语义入栈时标记则可以避免同一个顶点被多次压入栈。我倾向于出栈时标记因为逻辑更清晰而且栈中最多存在重复顶点不会影响正确性。非递归DFS的时间复杂度是O(VE)空间复杂度最坏情况下是O(V)栈的大小。相比递归版它不受调用栈深度限制处理大规模图更安全。3.3 递归与非递归的对比与选择两种实现方式各有适用场景。递归版代码短、可读性强适合教学演示和小规模图。非递归版更稳健适合生产环境和不确定规模的图。对比维度递归版DFS非递归版DFS代码长度短中等可读性高中等栈深度限制受Python限制不受限大规模图可能崩溃安全调试难度低中等遍历顺序控制自然需注意入栈顺序我个人的习惯是先用递归版快速验证算法逻辑确认无误后再改成非递归版用于实际运行。这样既能利用递归版的直观性来调试又能保证最终代码的健壮性。实操心得如果你在面试中需要手写DFS先写递归版然后主动提一句如果图规模很大我会改成用栈的非递归实现来避免栈溢出。这个补充能体现你对实际问题的考虑比单纯写出代码更加分。4. 广度优先搜索BFS的实现与层级控制4.1 BFS的核心机制队列与层级遍历BFS的思想是先访问所有邻居再访问邻居的邻居像水波一样一层层扩散。它用队列FIFO来实现from collections import deque def bfs(graph, start): visited set() queue deque([start]) visited.add(start) result [] while queue: vertex queue.popleft() result.append(vertex) for neighbor in graph.get_neighbors(vertex): v neighbor[0] if isinstance(neighbor, tuple) else neighbor if v not in visited: visited.add(v) queue.append(v) return result注意这里和DFS非递归版的一个关键区别BFS在入队时就标记visited而不是出队时。这是因为如果出队时才标记同一个顶点可能被多次加入队列导致重复处理和性能下降。DFS用栈时这个问题不那么明显因为栈的LIFO特性使得重复顶点很快被处理掉但BFS用队列时重复顶点会堆积必须提前标记。4.2 记录层级信息与最短路径BFS最强大的特性是它能自然计算出从起点到每个顶点的最短路径无权图。只需要在遍历时记录每个顶点的层级def bfs_with_level(graph, start): visited {start} queue deque([(start, 0)]) levels {start: 0} parent {start: None} # 记录路径 while queue: vertex, level queue.popleft() for neighbor in graph.get_neighbors(vertex): v neighbor[0] if isinstance(neighbor, tuple) else neighbor if v not in visited: visited.add(v) levels[v] level 1 parent[v] vertex queue.append((v, level 1)) return levels, parent def get_shortest_path(parent, target): path [] while target is not None: path.append(target) target parent[target] return path[::-1]parent字典记录了每个顶点是从哪个顶点扩展来的沿着parent指针回溯就能得到最短路径。这个技巧在实际问题中非常有用比如迷宫最短路径、社交网络中的最短关系链等。为什么BFS能求最短路径而DFS不能因为BFS是按层级扩展的第一次访问到某个顶点时经过的边数一定是最少的。DFS则可能沿着一条很长的路径先到达目标即使存在更短的路径也不会优先发现。4.3 BFS的常见变体与应用场景BFS不只能做简单的遍历稍加改造就能解决很多实际问题。比如多源BFS把多个起点同时加入队列可以计算每个顶点到最近起点的距离。再比如双向BFS从起点和终点同时扩展相遇时即找到最短路径能把搜索空间从O(b^d)降到O(b^(d/2))。def multi_source_bfs(graph, sources): visited set(sources) queue deque([(s, 0) for s in sources]) distances {s: 0 for s in sources} while queue: vertex, dist queue.popleft() for neighbor in graph.get_neighbors(vertex): v neighbor[0] if isinstance(neighbor, tuple) else neighbor if v not in visited: visited.add(v) distances[v] dist 1 queue.append((v, dist 1)) return distances多源BFS的典型应用是腐烂的橘子这类问题多个腐烂源同时扩散求所有橘子腐烂的最短时间。把初始腐烂的橘子全部入队然后正常BFS即可。注意BFS的空间复杂度在最坏情况下是O(V)因为队列可能同时包含大量顶点。如果图的宽度很大比如每个顶点都有很多邻居BFS的内存消耗会比DFS更明显。5. 完整实操从零构建图并运行四种遍历5.1 构建测试用例与预期结果光看代码不够得实际跑一遍才能发现问题。下面构建一个包含8个顶点的无向图分别用四种方式遍历对比输出结果。# 构建测试图 # 顶点: 0-7 # 边: 0-1, 0-2, 1-3, 1-4, 2-5, 2-6, 3-7, 4-7 def build_test_graph_list(): g GraphList(directedFalse) edges [(0,1), (0,2), (1,3), (1,4), (2,5), (2,6), (3,7), (4,7)] for u, v in edges: g.add_edge(u, v) return g def build_test_graph_matrix(): g GraphMatrix(8, directedFalse) edges [(0,1), (0,2), (1,3), (1,4), (2,5), (2,6), (3,7), (4,7)] for u, v in edges: g.add_edge(u, v) return g这个图的结构是0连接1和21连接3和42连接5和63和4都连接7。从0出发DFS应该沿着一条路径走到7再回溯BFS应该按层级依次访问。5.2 四种遍历方式的运行与结果对比if __name__ __main__: g_list build_test_graph_list() g_matrix build_test_graph_matrix() print( 邻接表 ) print(DFS递归:, dfs_recursive(g_list, 0)) print(DFS非递归:, dfs_iterative(g_list, 0)) print(BFS:, bfs(g_list, 0)) print(\n 邻接矩阵 ) print(DFS递归:, dfs_recursive(g_matrix, 0)) print(DFS非递归:, dfs_iterative(g_matrix, 0)) print(BFS:, bfs(g_matrix, 0)) # 层级与最短路径 levels, parent bfs_with_level(g_list, 0) print(\n层级:, levels) print(0到7的最短路径:, get_shortest_path(parent, 7))运行结果中DFS递归和非递归的输出应该完全一致前提是入栈顺序处理正确BFS的输出则呈现明显的层级特征。如果DFS两种实现的输出不一致大概率是入栈顺序的问题检查是否对邻居做了逆序处理。邻接矩阵和邻接表的遍历结果应该相同因为图的结构是一样的。如果不同说明某一种存储结构的构建有问题比如邻接矩阵忘记处理无向图的双向边。5.3 性能实测与数据结构选择验证我用一个随机生成的图做了简单的性能对比。对于1000个顶点、约5000条边的稀疏图邻接表的构建和遍历速度明显优于邻接矩阵。邻接矩阵在构建时就要分配100万个元素的二维数组而邻接表只需要存储实际存在的边。操作邻接矩阵(1000顶点)邻接表(1000顶点,5000边)构建时间约0.15秒约0.02秒DFS遍历约0.08秒约0.01秒BFS遍历约0.09秒约0.01秒内存占用约8MB约0.5MB这个差距在顶点数增加时会进一步拉大。所以再次强调稀疏图用邻接表不要跟内存过不去。6. 常见问题与排查技巧实录6.1 遍历结果不完整或死循环这是最常见的问题几乎都是visited集合的使用出了问题。典型症状是程序陷入死循环或者输出的顶点数量少于实际数量。排查思路首先检查visited是在什么时候标记的。DFS非递归版如果在入栈时标记可能导致某些顶点被跳过BFS如果在出队时标记可能导致重复入队和性能问题。其次检查无向图的边是否双向添加了如果只加了一个方向遍历会漏掉大量顶点。还有一个隐蔽的坑如果顶点编号不是从0开始的连续整数用列表做visited会出问题。这种情况下必须用集合或字典。我一般无脑用集合省心。6.2 递归深度超限的解决方案Python默认递归限制是1000超过就报RecursionError。临时方案是sys.setrecursionlimit(100000)但这只是把限制调高并没有消除栈溢出的风险。真正的解决方案是改用非递归实现。如果你必须用递归比如某些算法天然适合递归表达可以考虑用生成器或者手动维护栈来模拟。但在图的遍历这个场景下非递归版本并不复杂直接改掉是最省事的。6.3 邻接矩阵与邻接表结果不一致这种情况通常发生在图的有向性设置上。比如构建邻接矩阵时设置了directedTrue但构建邻接表时忘了设置导致一个有向一个无向遍历结果自然不同。另一个可能的原因是权重的处理。邻接矩阵中用0表示无边但如果边的权重恰好是0就会产生歧义。这种情况下需要用特殊值比如None或无穷大来表示无边。邻接表则没有这个问题因为不存在的边根本不会出现在邻居列表里。6.4 常见问题速查表问题现象可能原因解决方法死循环visited未标记或标记时机错误检查标记位置BFS入队标记DFS出栈标记遍历不全无向图只加了一个方向的边确保add_edge中双向添加递归报错递归深度超过限制改用非递归实现结果不一致两种存储结构的有向性设置不同统一directed参数性能差稀疏图用了邻接矩阵改用邻接表顶点编号非连续用列表做visited越界改用集合或字典实操心得调试图的遍历时先用一个只有3-4个顶点的小图手动推演一遍确认逻辑正确后再换成大图测试。小图上能一眼看出问题大图上输出一大堆数字反而难以定位。7. 一些延伸思考与个人体会图的遍历看起来是基础中的基础但真正把它吃透之后很多高级算法都会变得顺理成章。拓扑排序本质上就是DFS的后序遍历变体连通分量可以用DFS或BFS轻松求出二分图判定靠BFS的层级染色就能完成。这些算法我后面会陆续整理但前提是先把遍历这块基石打牢。我在实际写代码时有一个习惯不管题目要求用哪种方式我都会先把邻接表建好因为它的通用性最强。需要矩阵的时候再转换转换代码就几行不费事。这样避免了在一开始就纠结用哪种结构把精力集中在算法逻辑上。另外Python的deque比用列表模拟队列要快得多。列表的pop(0)是O(n)操作而deque.popleft()是O(1)。在BFS中这个差距会随着数据量增大而变得非常明显。这个细节看似微小但在处理大规模图时能省下大量时间。最后分享一个调试技巧在遍历过程中把每一步的栈/队列状态和visited集合打印出来对比递归版和非递归版的中间状态。如果两者在某个步骤出现分歧问题就定位到了那一步。这个方法比盯着最终输出结果猜问题要高效得多。