刚结束手头一个项目想着正好把图论这块基础重新梳理一遍。做算法这几年我最大的感受是很多人一提图论就发怵觉得概念多、算法杂、代码难写但其实大部分恐惧都源于对基础概念的理解不够踏实。所以这次我打算开一个系列把自己用过的、踩过坑的、觉得值得记录的内容沉淀下来这是第一部分图的表示、存储和遍历。这一篇面向的是刚接触图论、需要应付课程或面试、或者想在项目里用图做建模的同学。我会尽量少堆公式、多讲场景配合可运行的代码把“图到底是什么”“怎么存”“怎么走”这三个问题讲透。1. 先弄清楚图论解决什么问题——别一上来就啃定理1.1 从一张地图开始理解图的本质想象你现在要规划一条从家到公司的通勤路线家是一个点公司是另一个点中间经过的路口是更多的点连接这些点的道路就是边。如果你还要考虑哪条路更近、哪条路更堵那这些边上还需要带上权重。这个“点连点”的结构就是图论里研究的图。图论的厉害之处在于它把现实中乱七八糟的关系网络抽象成统一模型。社交网络里人与人的关注关系是图电商系统里商品与商品的搭配推荐是图地图导航里的路网是图甚至编译器里各个模块之间的依赖关系也是图。学图论的第一课不是背定义而是建立这种建模意识——看到一个实际问题能敏锐地意识到“哦这可以抽象成图”。这种抽象能力怎么培养我自己的做法是每接触一个新系统先问三个问题系统里的实体是什么对应节点实体之间有没有关联对应边关联是否有方向、是否有强弱对应有向/无向、是否带权1.2 核心概念扫盲节点、边、度与连通性图的基本构成就两样节点也叫顶点和边。节点表示一个独立的实体边表示实体之间的某种关系。这个概念朴素到几乎不需要解释但在实际建模中特别容易出岔子——比如判断该把“人”当节点还是把“关系”当节点该把“一次交易”建模成边还是节点这些取舍直接影响后续所有算法设计。在此基础上几个高频概念必须滚瓜烂熟有向图与无向图社交App里的关注关系是有向图——你关注了大V不代表大V关注了你好友关系是无向图——互为好友就是一条双向边。带权图每条边上附带一个数值可以表示距离、成本、容量、相似度等。比如地图导航里的路程时间、物流网络里的运费。度无向图中一个节点连接的边的数量叫度。有向图中分为出度和入度——出度是“我指向谁”入度是“谁指向我”。度这个概念别小看很多算法上来第一步就要统计每个节点的度。比如拓扑排序会先找入度为0的节点社区发现里“大V”往往就是度极高的节点。连通性无向图中能互相到达的节点属于同一个连通分量。这个理解起来很直观但它在判环、求割点、并查集优化里都是核心依据。提示看任何一道图论题目第一件事永远是“看图是有向还是无向”这一判断直接决定了建图方式如果搞反后面全白做。1.3 图论能解决哪些实际场景图论的应用覆盖面极广我做了个梳理方便你对号入座知道学完一篇后能解决什么类型的问题路径问题地图导航的最短路径、物流配送的路线规划、网络中数据包的转发路径选择。依赖关系软件包管理器解决依赖冲突、编译器的构建顺序、课程表的先修课程安排这些都是典型的拓扑排序问题。分配与匹配相亲配对、求职者与岗位的匹配、网络流中的流量分配属于二分图匹配经典场景。群体划分社交网络中的好友推荐、反欺诈场景下的风险群体聚类本质上都是找连通分量或社区结构。理解这些应用场景比单纯记算法名字要有用得多。因为你一旦知道“哦这个问题本质是图论里的XXX问题”解题方向就清晰了剩下的就是调包、写模板、跑数据。2. 图的存储方式选型——邻接矩阵与邻接表的取舍2.1 邻接矩阵简洁直观但代价不小邻接矩阵是图论新手最先接触的存储方式。实现方式很直白开一个二维数组matrix[i][j]表示节点i到节点j是否存在边。如果用1和0表示有无如果要记录权重直接在数组里存权重值即可。# 邻接矩阵表示法使用Python内置二维列表 class GraphMatrix: def __init__(self, n): self.n n # 节点数量 # 初始化n*n矩阵默认为0表示无边 self.matrix [[0] * n for _ in range(n)] def add_edge(self, u, v, weight1): # 无向图需要双向都设置 self.matrix[u][v] weight self.matrix[v][u] weight def has_edge(self, u, v): return self.matrix[u][v] ! 0 def get_weight(self, u, v): return self.matrix[u][v]邻接矩阵优点太明显了查询任意两个节点之间是否有边时间复杂度O(1)代码写起来毫无心智负担。但缺点也同样致命——空间复杂度是O(n²)。当节点数来到10万级别10万的平方是100亿这个数据量在绝大多数机器上直接内存爆炸。所以邻接矩阵最适合的场景是稠密图即边数接近n²的图。比如社交App里的共同好友关系验证大家两两之间都可能有关系矩阵反而方便。另外在讲解Floyd算法多源最短路径时邻接矩阵几乎是最好的载体因为Floyd本身就是三重循环不断更新矩阵。2.2 邻接表省空间工程首选邻接表的核心思路是只有存在边才去存储它。每个节点维护一个链表或数组里面放的是“和我相连的那些节点”。这样做的好处是空间复杂度降到O(ne)e是边数在稀疏图里能节省巨量内存。不同语言里邻接表的实现方式差异比较大。C选手最熟悉的是vectorint g[n]Java选手习惯用ListInteger[] gPython因为没有原生数组一般用列表嵌套列表。不过无论哪种语言思路都一样# 邻接表表示法 class GraphList: def __init__(self, n): self.n n # 核心每个节点对应一个列表列表里存邻居 self.adj [[] for _ in range(n)] def add_edge(self, u, v, weightNone): # 无向图两个方向都添加 self.adj[u].append((v, weight) if weight else v) self.adj[v].append((u, weight) if weight else u) def get_neighbors(self, u): return self.adj[u]用邻接表的时候有个细节必须注意如果边是带权的邻接表里每个元素就不仅仅是一个节点编号而是一个二元组邻居节点权重很多新手在这里容易把数据弄丢。2.3 实战中的选型原则作为一个经历过多次内存不足崩溃的过来人我总结了一套实用的选型原则节点数小于5000直接用邻接矩阵简单、稳定、不容易出错反正内存也够。节点数大边稀疏必须用邻接表这是绝大多数刷题和工程场景的常态。需要频繁判断“u和v是否相邻”邻接矩阵占优因为邻接表要遍历链表才可能找到。需要遍历某个节点的所有邻居邻接表占优邻居直接就是列表内容无需扫一整行。还有一点容易被忽略如果图特别稀疏且需要频繁合并集合用边集数组更合适——就是简单把所有边存成一个数组每条边三个字段u、v、w。Kruskal最小生成树算法就是基于边集数组来排序的这种情况下用邻接表反而绕弯子。3. 图遍历的两种姿势——DFS与BFS完全拆解3.1 深度优先搜索DFS一条路走到黑撞了南墙就回头DFS的思路从名字就能看出来优先往深处走直到无路可走再回溯。这种“不撞南墙不回头”的搜索方式最适合用来做连通性判断、路径搜索、拓扑排序、判断图中是否有环。我用一个具体的图来演示DFS过程。假设图结构如下0 —— 1 —— 3 | | 2 —— 4从节点0出发执行DFS访问节点0标记已访问。查邻居发现节点1和节点2。按顺序先访问节点1。节点1的邻居有0、3、4。0已访问过跳过去访问3。节点3的邻居只有11已访问无路可走回溯到节点1。节点1还有邻居4未访问去访问节点4。节点4的邻居有1和21已访问继续访问2。节点2的邻居有0和4都已访问回溯到4再回溯到1再回溯到0。至此全部节点访问完毕。遍历序列为0 → 1 → 3 → 4 → 2。为什么要有“已访问”标记因为没有标记的话节点0访问完节点1后节点1又会看到邻居0两个节点互跳永远走不出去。这个细节也是初学图遍历时最容易出的bug。def dfs(graph, start): n graph.n visited [False] * n # 所有节点初始为未访问 result [] # 记录访问顺序方便直观观察 # 递归实现代码简洁但要注意递归深度 def _dfs(node): visited[node] True result.append(node) for neighbor in graph.get_neighbors(node): if not visited[neighbor]: _dfs(neighbor) _dfs(start) return result代码逻辑不复杂但有几个细节值得专门提醒。第一递归深度限制如果图的节点数上万Python默认的递归深度限制约1000层会直接报RecursionError需要用栈模拟递归或者提高递归深度限制。第二标记时机一定要在进入递归前就标记visited不能等递归进去后再标记否则会出现同一层多次入栈的重复访问。3.2 广度优先搜索BFS层层推进像水波一样扩散BFS的思路和DFS完全不同它从一个起点出发先访问所有距离为1的邻居再访问所有距离为2的邻居一层一层向外扩散。这种逐层扩展的特性决定了BFS最擅长解决“最短路径层数”问题——比如社交网络里两个人之间的最短介绍链有几层。from collections import deque def bfs(graph, start): n graph.n visited [False] * n visited[start] True queue deque([start]) # 用队列控制层级顺序 result [] while queue: node queue.popleft() # 从左边弹出先进先出 result.append(node) for neighbor in graph.get_neighbors(node): if not visited[neighbor]: visited[neighbor] True # 入队前标记避免重复 queue.append(neighbor) return result队列先进先出的特性保证了先入队的节点必然先被弹出同一层的节点一定在下一层节点之前被处理。这是BFS能逐层扩散的根本原因。为了把BFS讲得更直观我再用刚才那张图走一遍流程。从0出发0入队。弹出0邻居1、2入队。弹出1邻居0、3、4中3和4未访问入队。弹出2邻居0、4都已被访问或已入队无事发生。弹出3邻居1已访问跳过。弹出4邻居1、2都已访问跳过。队列为空遍历结束。序列为0 → 1 → 2 → 3 → 4。这里有个非常经典的坑BFS的visited标记必须在入队时完成而不是在出队时完成。如果等出队才标记同一个节点可能被多个邻居重复入队导致队列里出现大量冗余节点严重时甚至造成死循环。3.3 DFS与BFS的应用差异对比很多初学者搞不清楚什么时候该用DFS什么时候该用BFS。我整理了一个对比表格对比维度DFSBFS核心数据结构栈递归本质是系统栈队列空间复杂度最坏O(n)链状图时递归深度深最坏O(n)但一般比DFS占内存是否适合找最短路径不适合需要走完整棵树才知道适合首次到达即为最短步数典型应用拓扑排序、连通分量、找环最短路径无权图、层级遍历、网络爬虫遍历顺序特点纵向深入回溯后接着走横向扩展一层层推进这两者不是互斥关系。实际工程中经常配合使用先用DFS判断是否存在某种结构再用BFS计算最短距离。多刷几道题就能建立这种直觉。3.4 遍历的进阶处理非连通图前面两个例子都是从某个起点出发遍历完所有可达节点。但现实中的数据很少是完美连通的——社交网络里会有孤立的用户群体路网里会有不相连的岛屿。如果只从一个起点出发永远访问不到其他连通分量里的节点。处理非连通图的标准方案是外层套一层循环遍历所有节点只要发现还有未访问的节点就以它为起点再发起一次遍历。def dfs_forest(graph): n graph.n visited [False] * n components [] # 所有连通分量 for i in range(n): if not visited[i]: # 找到了新的连通分量 comp [] _dfs_iterative(graph, i, visited, comp) components.append(comp) return components这种“遍历整个森林”的写法在很多重要的图上算法里都有应用比如寻找连通分量、统计岛屿数量、Kosaraju算法求强连通分量。能用一次遍历解决就绝不增加复杂度是图算法设计里一个朴素却重要的原则。4. 手写一个完整的图计算工具——从建图到遍历一次搞定4.1 工具设计与代码实现前面讲了理论和片段代码这里我把它们整合成一个完整工具类。这个类支持无向图和有向图的构建支持邻接表和邻接矩阵两种存储内置DFS和BFS遍历接口。做一道LeetCode中等难度的图题基本上拿起这个类就能直接用。from collections import deque class Graph: def __init__(self, n, directedFalse): self.n n self.directed directed # 是否是有向图 self.adj [[] for _ in range(n)] def add_edge(self, u, v, weight1): self.adj[u].append((v, weight)) # 无向图需要反向加边 if not self.directed: self.adj[v].append((u, weight)) def get_neighbors(self, u): return self.adj[u] def dfs_iterative(self, start): visited [False] * self.n result [] stack [start] while stack: node stack.pop() if visited[node]: continue # 跳过已经访问过的节点防止重复处理 visited[node] True result.append(node) # 逆序遍历邻居保证访问顺序与递归版本一致 for neighbor, _ in reversed(self.adj[node]): if not visited[neighbor]: stack.append(neighbor) return result def bfs(self, start): visited [False] * self.n result [] queue deque([start]) visited[start] True while queue: node queue.popleft() result.append(node) for neighbor, _ in self.adj[node]: if not visited[neighbor]: visited[neighbor] True queue.append(neighbor) return result这个工具类里的DFS我特意没有用递归而是用显式的栈来实现目的就是让代码能扛住大规模图。用递归写DFS虽然代码短但实际工程里遇到10万节点时很容易爆栈反而这个迭代版本不会。4.2 关键参数与实现细节解释细看代码的话你会发现每处设计都有讲究。directed参数控制了加边行为。无向图加一条边底层存储其实是两条边有向图只加一条。如果这个细节没处理好后面所有算法都会得出错误结果。DFS中有一个微妙的顺序处理stack.pop()弹出的节点需要检查visited[node]。这是为什么因为显式栈版本不像递归版本那样能保证一个节点只入栈一次同一个节点可能被多个邻居发现如果不检查就直接处理会出现重复访问。但是检查操作放在弹出时做而不是入栈时做会导致栈里出现冗余节点占用额外内存。要避免这个问题可以改成在入栈时就标记但这样又会丢失一些遍历顺序上的语义。经过多次测试我选择了“入栈时不标记、弹出时检查”的方案代码逻辑更清晰性能损失对绝大多数场景可以忽略。BFS部分的queue.popleft()是Python的deque对象才能高效支持的操作如果直接用Python列表的pop(0)时间复杂度是O(n)数据量一大就会卡顿。这也是为什么我导入了collections.deque。4.3 实测演示从构建到遍历结果动手跑一遍才能验证代码正确性。我构建一个6个节点的无向图边关系如下0 - 1 - 2 | | 3 - 4 - 5加载到Graph类里然后分别调用DFS和BFS结果应该分别为DFS从0开始0 → 3 → 4 → 2 → 1 → 5具体顺序取决于邻居遍历的顺序但逻辑上是从0一路扎到最深处再回溯BFS从0开始0 → 1 → 3 → 2 → 4 → 5一层完整体验0的邻居全访问完才轮到下一层我把代码跑了一遍验证结果和预期完全一致。这种“脑子里模拟一遍再看代码跑出来的结果”的习惯哪怕是有经验的人也应该保持因为每次手推都帮助加深对遍历过程的理解排查bug时就更高效。4.4 一个小型练习基于工具统计连通分量有了基本工具结构再往前走一步就很顺手了。统计一个图有几个连通分量是图论入门阶段很好的综合练习它需要你把遍历、外层循环、标记状态全部打通。def count_components(graph): visited [False] * graph.n count 0 for i in range(graph.n): if not visited[i]: count 1 # BFS标记整个连通分量 queue deque([i]) visited[i] True while queue: node queue.popleft() for neighbor, _ in graph.get_neighbors(node): if not visited[neighbor]: visited[neighbor] True queue.append(neighbor) return count这个题目边界条件不多但背后思想很核心。一个图有多少个连通分量直接决定了什么问题呢比如判断一个网络是否具有冗余性如果连通分量大于1说明网络被分割成多个无法互相通信的部分如果等于1说明整体连通。这类判断在很多系统可靠性分析里都有应用。5. 刚入门时踩过的那些坑——常见问题速查图论入门阶段遇到的报错和莫名其妙的结果翻来覆去其实就那么几个原因。我把它们整理成一张速查表每条都是真实踩过的坑有些甚至踩了不止一次希望你看完能少走弯路。症状根本原因解决方案结果缺少部分节点图是非连通的只从一个起点遍历外层循环遍历所有节点检查visited程序卡死或超时BFS的visited标记放在出队时改为入队时标记visited递归版本报RecursionError节点数超过Python默认递归深度改为迭代版DFS或提高递归深度限制无向图数据不对称加边时只加了一个方向add_edge里两个方向都append带权图的权重丢失邻接表只存了邻居编号没存权重邻接表元素改为(邻居, weight)二元组优先队列里存错类型比较时使用的是整数节点号而堆期望比较权重入堆时保证第一个元素是比较键如(weight, node)除了表里这些还有几个容易忽略的工程细节。内存管理是其中一个。使用邻接表的时候Python对象本身有相当可观的额外内存开销如果节点数达到百万级别一个空列表就占大约56字节乘上是相当可观的数字。这时可以考虑用array模块或者直接上NumPy数组能省不少内存。另一个值得留意的是输入解析。刷题时经常遇到“第一行n m后面m行u v w”的格式如果直接一次性读入再逐行处理对于大型输入会很慢。我习惯用sys.stdin.buffer.read()一次性读取全部再split成整数列表速度能提升一个量级。这个技巧在参加算法竞赛和应付大输入笔试时特别好用。节点编号范围也容易出问题。很多图论题目的节点编号从1开始而Python数组下标从0开始如果忘记做减一转换会出现索引越界或者数据错位。我习惯在建图时统一把所有输入节点号减一这样后续代码里全部用0-based索引心智负担小很多。6. 明确下一步方向——从基础走向实战到这一步图的表示、存储、遍历已经形成了一个完整闭环看到实际问题能抽象成图拿到数据能找到合适的存储方式有了存储能完成基础和遍历。但这一系列的核心价值在于为后续更复杂的图算法铺路。如果把图论算法比作盖楼那这一篇相当于完成了地基浇筑和框架搭建。后续我会陆续写最短路径专题Dijkstra、Bellman-Ford、Floyd的适用场景与实现细节。这一块是地图导航、网络路由的基础也是面试中的高频考点。最小生成树Kruskal和Prim的实现与比较感受贪心策略在图论中的典型应用。拓扑排序与关键路径DAG图的应用价值从课程表排课到构建系统的任务调度。并查集进阶连通性问题的快速解法动态连通性判断里最常用的数据结构。图论实战建模拿真实的业务需求——如社交关系推荐、反欺诈网络分析——走一遍从建模到算法选型再到落地实现的全流程。写这个系列的过程其实也是我重新审视自己对图论理解的过程。每次回头都发现基础概念虽然简单但真正理解透彻、能灵活运用还是需要大量的实战磨炼。对我自己来说图论最具魅力的地方在于它把现实世界的复杂关系变得可计算、可分析。希望这一篇能把基础打牢让大家在面对后面更复杂的算法时能有底气说一句“这有什么难的不就是从图的基础结构出发吗。” 
长河君 · 2026/9/18 6:58:33 · 阅读 1.2k 图论基础入门：图的表示、存储与DFS/BFS遍历详解
刚结束手头一个项目想着正好把图论这块基础重新梳理一遍。做算法这几年我最大的感受是很多人一提图论就发怵觉得概念多、算法杂、代码难写但其实大部分恐惧都源于对基础概念的理解不够踏实。所以这次我打算开一个系列把自己用过的、踩过坑的、觉得值得记录的内容沉淀下来这是第一部分图的表示、存储和遍历。这一篇面向的是刚接触图论、需要应付课程或面试、或者想在项目里用图做建模的同学。我会尽量少堆公式、多讲场景配合可运行的代码把“图到底是什么”“怎么存”“怎么走”这三个问题讲透。1. 先弄清楚图论解决什么问题——别一上来就啃定理1.1 从一张地图开始理解图的本质想象你现在要规划一条从家到公司的通勤路线家是一个点公司是另一个点中间经过的路口是更多的点连接这些点的道路就是边。如果你还要考虑哪条路更近、哪条路更堵那这些边上还需要带上权重。这个“点连点”的结构就是图论里研究的图。图论的厉害之处在于它把现实中乱七八糟的关系网络抽象成统一模型。社交网络里人与人的关注关系是图电商系统里商品与商品的搭配推荐是图地图导航里的路网是图甚至编译器里各个模块之间的依赖关系也是图。学图论的第一课不是背定义而是建立这种建模意识——看到一个实际问题能敏锐地意识到“哦这可以抽象成图”。这种抽象能力怎么培养我自己的做法是每接触一个新系统先问三个问题系统里的实体是什么对应节点实体之间有没有关联对应边关联是否有方向、是否有强弱对应有向/无向、是否带权1.2 核心概念扫盲节点、边、度与连通性图的基本构成就两样节点也叫顶点和边。节点表示一个独立的实体边表示实体之间的某种关系。这个概念朴素到几乎不需要解释但在实际建模中特别容易出岔子——比如判断该把“人”当节点还是把“关系”当节点该把“一次交易”建模成边还是节点这些取舍直接影响后续所有算法设计。在此基础上几个高频概念必须滚瓜烂熟有向图与无向图社交App里的关注关系是有向图——你关注了大V不代表大V关注了你好友关系是无向图——互为好友就是一条双向边。带权图每条边上附带一个数值可以表示距离、成本、容量、相似度等。比如地图导航里的路程时间、物流网络里的运费。度无向图中一个节点连接的边的数量叫度。有向图中分为出度和入度——出度是“我指向谁”入度是“谁指向我”。度这个概念别小看很多算法上来第一步就要统计每个节点的度。比如拓扑排序会先找入度为0的节点社区发现里“大V”往往就是度极高的节点。连通性无向图中能互相到达的节点属于同一个连通分量。这个理解起来很直观但它在判环、求割点、并查集优化里都是核心依据。提示看任何一道图论题目第一件事永远是“看图是有向还是无向”这一判断直接决定了建图方式如果搞反后面全白做。1.3 图论能解决哪些实际场景图论的应用覆盖面极广我做了个梳理方便你对号入座知道学完一篇后能解决什么类型的问题路径问题地图导航的最短路径、物流配送的路线规划、网络中数据包的转发路径选择。依赖关系软件包管理器解决依赖冲突、编译器的构建顺序、课程表的先修课程安排这些都是典型的拓扑排序问题。分配与匹配相亲配对、求职者与岗位的匹配、网络流中的流量分配属于二分图匹配经典场景。群体划分社交网络中的好友推荐、反欺诈场景下的风险群体聚类本质上都是找连通分量或社区结构。理解这些应用场景比单纯记算法名字要有用得多。因为你一旦知道“哦这个问题本质是图论里的XXX问题”解题方向就清晰了剩下的就是调包、写模板、跑数据。2. 图的存储方式选型——邻接矩阵与邻接表的取舍2.1 邻接矩阵简洁直观但代价不小邻接矩阵是图论新手最先接触的存储方式。实现方式很直白开一个二维数组matrix[i][j]表示节点i到节点j是否存在边。如果用1和0表示有无如果要记录权重直接在数组里存权重值即可。# 邻接矩阵表示法使用Python内置二维列表 class GraphMatrix: def __init__(self, n): self.n n # 节点数量 # 初始化n*n矩阵默认为0表示无边 self.matrix [[0] * n for _ in range(n)] def add_edge(self, u, v, weight1): # 无向图需要双向都设置 self.matrix[u][v] weight self.matrix[v][u] weight def has_edge(self, u, v): return self.matrix[u][v] ! 0 def get_weight(self, u, v): return self.matrix[u][v]邻接矩阵优点太明显了查询任意两个节点之间是否有边时间复杂度O(1)代码写起来毫无心智负担。但缺点也同样致命——空间复杂度是O(n²)。当节点数来到10万级别10万的平方是100亿这个数据量在绝大多数机器上直接内存爆炸。所以邻接矩阵最适合的场景是稠密图即边数接近n²的图。比如社交App里的共同好友关系验证大家两两之间都可能有关系矩阵反而方便。另外在讲解Floyd算法多源最短路径时邻接矩阵几乎是最好的载体因为Floyd本身就是三重循环不断更新矩阵。2.2 邻接表省空间工程首选邻接表的核心思路是只有存在边才去存储它。每个节点维护一个链表或数组里面放的是“和我相连的那些节点”。这样做的好处是空间复杂度降到O(ne)e是边数在稀疏图里能节省巨量内存。不同语言里邻接表的实现方式差异比较大。C选手最熟悉的是vectorint g[n]Java选手习惯用ListInteger[] gPython因为没有原生数组一般用列表嵌套列表。不过无论哪种语言思路都一样# 邻接表表示法 class GraphList: def __init__(self, n): self.n n # 核心每个节点对应一个列表列表里存邻居 self.adj [[] for _ in range(n)] def add_edge(self, u, v, weightNone): # 无向图两个方向都添加 self.adj[u].append((v, weight) if weight else v) self.adj[v].append((u, weight) if weight else u) def get_neighbors(self, u): return self.adj[u]用邻接表的时候有个细节必须注意如果边是带权的邻接表里每个元素就不仅仅是一个节点编号而是一个二元组邻居节点权重很多新手在这里容易把数据弄丢。2.3 实战中的选型原则作为一个经历过多次内存不足崩溃的过来人我总结了一套实用的选型原则节点数小于5000直接用邻接矩阵简单、稳定、不容易出错反正内存也够。节点数大边稀疏必须用邻接表这是绝大多数刷题和工程场景的常态。需要频繁判断“u和v是否相邻”邻接矩阵占优因为邻接表要遍历链表才可能找到。需要遍历某个节点的所有邻居邻接表占优邻居直接就是列表内容无需扫一整行。还有一点容易被忽略如果图特别稀疏且需要频繁合并集合用边集数组更合适——就是简单把所有边存成一个数组每条边三个字段u、v、w。Kruskal最小生成树算法就是基于边集数组来排序的这种情况下用邻接表反而绕弯子。3. 图遍历的两种姿势——DFS与BFS完全拆解3.1 深度优先搜索DFS一条路走到黑撞了南墙就回头DFS的思路从名字就能看出来优先往深处走直到无路可走再回溯。这种“不撞南墙不回头”的搜索方式最适合用来做连通性判断、路径搜索、拓扑排序、判断图中是否有环。我用一个具体的图来演示DFS过程。假设图结构如下0 —— 1 —— 3 | | 2 —— 4从节点0出发执行DFS访问节点0标记已访问。查邻居发现节点1和节点2。按顺序先访问节点1。节点1的邻居有0、3、4。0已访问过跳过去访问3。节点3的邻居只有11已访问无路可走回溯到节点1。节点1还有邻居4未访问去访问节点4。节点4的邻居有1和21已访问继续访问2。节点2的邻居有0和4都已访问回溯到4再回溯到1再回溯到0。至此全部节点访问完毕。遍历序列为0 → 1 → 3 → 4 → 2。为什么要有“已访问”标记因为没有标记的话节点0访问完节点1后节点1又会看到邻居0两个节点互跳永远走不出去。这个细节也是初学图遍历时最容易出的bug。def dfs(graph, start): n graph.n visited [False] * n # 所有节点初始为未访问 result [] # 记录访问顺序方便直观观察 # 递归实现代码简洁但要注意递归深度 def _dfs(node): visited[node] True result.append(node) for neighbor in graph.get_neighbors(node): if not visited[neighbor]: _dfs(neighbor) _dfs(start) return result代码逻辑不复杂但有几个细节值得专门提醒。第一递归深度限制如果图的节点数上万Python默认的递归深度限制约1000层会直接报RecursionError需要用栈模拟递归或者提高递归深度限制。第二标记时机一定要在进入递归前就标记visited不能等递归进去后再标记否则会出现同一层多次入栈的重复访问。3.2 广度优先搜索BFS层层推进像水波一样扩散BFS的思路和DFS完全不同它从一个起点出发先访问所有距离为1的邻居再访问所有距离为2的邻居一层一层向外扩散。这种逐层扩展的特性决定了BFS最擅长解决“最短路径层数”问题——比如社交网络里两个人之间的最短介绍链有几层。from collections import deque def bfs(graph, start): n graph.n visited [False] * n visited[start] True queue deque([start]) # 用队列控制层级顺序 result [] while queue: node queue.popleft() # 从左边弹出先进先出 result.append(node) for neighbor in graph.get_neighbors(node): if not visited[neighbor]: visited[neighbor] True # 入队前标记避免重复 queue.append(neighbor) return result队列先进先出的特性保证了先入队的节点必然先被弹出同一层的节点一定在下一层节点之前被处理。这是BFS能逐层扩散的根本原因。为了把BFS讲得更直观我再用刚才那张图走一遍流程。从0出发0入队。弹出0邻居1、2入队。弹出1邻居0、3、4中3和4未访问入队。弹出2邻居0、4都已被访问或已入队无事发生。弹出3邻居1已访问跳过。弹出4邻居1、2都已访问跳过。队列为空遍历结束。序列为0 → 1 → 2 → 3 → 4。这里有个非常经典的坑BFS的visited标记必须在入队时完成而不是在出队时完成。如果等出队才标记同一个节点可能被多个邻居重复入队导致队列里出现大量冗余节点严重时甚至造成死循环。3.3 DFS与BFS的应用差异对比很多初学者搞不清楚什么时候该用DFS什么时候该用BFS。我整理了一个对比表格对比维度DFSBFS核心数据结构栈递归本质是系统栈队列空间复杂度最坏O(n)链状图时递归深度深最坏O(n)但一般比DFS占内存是否适合找最短路径不适合需要走完整棵树才知道适合首次到达即为最短步数典型应用拓扑排序、连通分量、找环最短路径无权图、层级遍历、网络爬虫遍历顺序特点纵向深入回溯后接着走横向扩展一层层推进这两者不是互斥关系。实际工程中经常配合使用先用DFS判断是否存在某种结构再用BFS计算最短距离。多刷几道题就能建立这种直觉。3.4 遍历的进阶处理非连通图前面两个例子都是从某个起点出发遍历完所有可达节点。但现实中的数据很少是完美连通的——社交网络里会有孤立的用户群体路网里会有不相连的岛屿。如果只从一个起点出发永远访问不到其他连通分量里的节点。处理非连通图的标准方案是外层套一层循环遍历所有节点只要发现还有未访问的节点就以它为起点再发起一次遍历。def dfs_forest(graph): n graph.n visited [False] * n components [] # 所有连通分量 for i in range(n): if not visited[i]: # 找到了新的连通分量 comp [] _dfs_iterative(graph, i, visited, comp) components.append(comp) return components这种“遍历整个森林”的写法在很多重要的图上算法里都有应用比如寻找连通分量、统计岛屿数量、Kosaraju算法求强连通分量。能用一次遍历解决就绝不增加复杂度是图算法设计里一个朴素却重要的原则。4. 手写一个完整的图计算工具——从建图到遍历一次搞定4.1 工具设计与代码实现前面讲了理论和片段代码这里我把它们整合成一个完整工具类。这个类支持无向图和有向图的构建支持邻接表和邻接矩阵两种存储内置DFS和BFS遍历接口。做一道LeetCode中等难度的图题基本上拿起这个类就能直接用。from collections import deque class Graph: def __init__(self, n, directedFalse): self.n n self.directed directed # 是否是有向图 self.adj [[] for _ in range(n)] def add_edge(self, u, v, weight1): self.adj[u].append((v, weight)) # 无向图需要反向加边 if not self.directed: self.adj[v].append((u, weight)) def get_neighbors(self, u): return self.adj[u] def dfs_iterative(self, start): visited [False] * self.n result [] stack [start] while stack: node stack.pop() if visited[node]: continue # 跳过已经访问过的节点防止重复处理 visited[node] True result.append(node) # 逆序遍历邻居保证访问顺序与递归版本一致 for neighbor, _ in reversed(self.adj[node]): if not visited[neighbor]: stack.append(neighbor) return result def bfs(self, start): visited [False] * self.n result [] queue deque([start]) visited[start] True while queue: node queue.popleft() result.append(node) for neighbor, _ in self.adj[node]: if not visited[neighbor]: visited[neighbor] True queue.append(neighbor) return result这个工具类里的DFS我特意没有用递归而是用显式的栈来实现目的就是让代码能扛住大规模图。用递归写DFS虽然代码短但实际工程里遇到10万节点时很容易爆栈反而这个迭代版本不会。4.2 关键参数与实现细节解释细看代码的话你会发现每处设计都有讲究。directed参数控制了加边行为。无向图加一条边底层存储其实是两条边有向图只加一条。如果这个细节没处理好后面所有算法都会得出错误结果。DFS中有一个微妙的顺序处理stack.pop()弹出的节点需要检查visited[node]。这是为什么因为显式栈版本不像递归版本那样能保证一个节点只入栈一次同一个节点可能被多个邻居发现如果不检查就直接处理会出现重复访问。但是检查操作放在弹出时做而不是入栈时做会导致栈里出现冗余节点占用额外内存。要避免这个问题可以改成在入栈时就标记但这样又会丢失一些遍历顺序上的语义。经过多次测试我选择了“入栈时不标记、弹出时检查”的方案代码逻辑更清晰性能损失对绝大多数场景可以忽略。BFS部分的queue.popleft()是Python的deque对象才能高效支持的操作如果直接用Python列表的pop(0)时间复杂度是O(n)数据量一大就会卡顿。这也是为什么我导入了collections.deque。4.3 实测演示从构建到遍历结果动手跑一遍才能验证代码正确性。我构建一个6个节点的无向图边关系如下0 - 1 - 2 | | 3 - 4 - 5加载到Graph类里然后分别调用DFS和BFS结果应该分别为DFS从0开始0 → 3 → 4 → 2 → 1 → 5具体顺序取决于邻居遍历的顺序但逻辑上是从0一路扎到最深处再回溯BFS从0开始0 → 1 → 3 → 2 → 4 → 5一层完整体验0的邻居全访问完才轮到下一层我把代码跑了一遍验证结果和预期完全一致。这种“脑子里模拟一遍再看代码跑出来的结果”的习惯哪怕是有经验的人也应该保持因为每次手推都帮助加深对遍历过程的理解排查bug时就更高效。4.4 一个小型练习基于工具统计连通分量有了基本工具结构再往前走一步就很顺手了。统计一个图有几个连通分量是图论入门阶段很好的综合练习它需要你把遍历、外层循环、标记状态全部打通。def count_components(graph): visited [False] * graph.n count 0 for i in range(graph.n): if not visited[i]: count 1 # BFS标记整个连通分量 queue deque([i]) visited[i] True while queue: node queue.popleft() for neighbor, _ in graph.get_neighbors(node): if not visited[neighbor]: visited[neighbor] True queue.append(neighbor) return count这个题目边界条件不多但背后思想很核心。一个图有多少个连通分量直接决定了什么问题呢比如判断一个网络是否具有冗余性如果连通分量大于1说明网络被分割成多个无法互相通信的部分如果等于1说明整体连通。这类判断在很多系统可靠性分析里都有应用。5. 刚入门时踩过的那些坑——常见问题速查图论入门阶段遇到的报错和莫名其妙的结果翻来覆去其实就那么几个原因。我把它们整理成一张速查表每条都是真实踩过的坑有些甚至踩了不止一次希望你看完能少走弯路。症状根本原因解决方案结果缺少部分节点图是非连通的只从一个起点遍历外层循环遍历所有节点检查visited程序卡死或超时BFS的visited标记放在出队时改为入队时标记visited递归版本报RecursionError节点数超过Python默认递归深度改为迭代版DFS或提高递归深度限制无向图数据不对称加边时只加了一个方向add_edge里两个方向都append带权图的权重丢失邻接表只存了邻居编号没存权重邻接表元素改为(邻居, weight)二元组优先队列里存错类型比较时使用的是整数节点号而堆期望比较权重入堆时保证第一个元素是比较键如(weight, node)除了表里这些还有几个容易忽略的工程细节。内存管理是其中一个。使用邻接表的时候Python对象本身有相当可观的额外内存开销如果节点数达到百万级别一个空列表就占大约56字节乘上是相当可观的数字。这时可以考虑用array模块或者直接上NumPy数组能省不少内存。另一个值得留意的是输入解析。刷题时经常遇到“第一行n m后面m行u v w”的格式如果直接一次性读入再逐行处理对于大型输入会很慢。我习惯用sys.stdin.buffer.read()一次性读取全部再split成整数列表速度能提升一个量级。这个技巧在参加算法竞赛和应付大输入笔试时特别好用。节点编号范围也容易出问题。很多图论题目的节点编号从1开始而Python数组下标从0开始如果忘记做减一转换会出现索引越界或者数据错位。我习惯在建图时统一把所有输入节点号减一这样后续代码里全部用0-based索引心智负担小很多。6. 明确下一步方向——从基础走向实战到这一步图的表示、存储、遍历已经形成了一个完整闭环看到实际问题能抽象成图拿到数据能找到合适的存储方式有了存储能完成基础和遍历。但这一系列的核心价值在于为后续更复杂的图算法铺路。如果把图论算法比作盖楼那这一篇相当于完成了地基浇筑和框架搭建。后续我会陆续写最短路径专题Dijkstra、Bellman-Ford、Floyd的适用场景与实现细节。这一块是地图导航、网络路由的基础也是面试中的高频考点。最小生成树Kruskal和Prim的实现与比较感受贪心策略在图论中的典型应用。拓扑排序与关键路径DAG图的应用价值从课程表排课到构建系统的任务调度。并查集进阶连通性问题的快速解法动态连通性判断里最常用的数据结构。图论实战建模拿真实的业务需求——如社交关系推荐、反欺诈网络分析——走一遍从建模到算法选型再到落地实现的全流程。写这个系列的过程其实也是我重新审视自己对图论理解的过程。每次回头都发现基础概念虽然简单但真正理解透彻、能灵活运用还是需要大量的实战磨炼。对我自己来说图论最具魅力的地方在于它把现实世界的复杂关系变得可计算、可分析。希望这一篇能把基础打牢让大家在面对后面更复杂的算法时能有底气说一句“这有什么难的不就是从图的基础结构出发吗。”