做图论或者日常写路径规划、网络拓扑、推荐关系链的朋友一定绕不开一个基础又灵活的数据结构——加权无向图。它解决的是一个很朴素的问题一堆节点之间有相连的边每条边有一个代价值你怎么在图上求出从A到B的最低代价、或者把整张图里的关键成本压到最低。我最早接触它是在做一个物流配送Demo的时候当时地图API在离线环境没法直接用只能靠后台预置的拓扑数据自己算最短路径读了三天图论教材最后把加权无向图的存储、遍历、最短路径和最小生成树全部手写了一遍。这篇文章就把这些完整梳理出来包含可以直接复用的Python代码、边界条件处理和几个我真实踩过的坑适合正在做路径规划、网络建设或者听课到一半卡住的同学参考。1. 加权无向图到底解决什么问题从两个真实场景说起很多人第一次见加权无向图这个名字就被劝退了其实它拆分下来没有任何一个新概念。无向意味着边没有方向1号节点到2号节点和2号节点到1号节点的代价一样类似一条双向都通畅的道路加权意味着边上有数字这个数字可以代表距离、花费、时间、信号衰减等任意可量化的成本。1.1 地图导航里的最短路径问题假设你要在A点和B点之间找一条总路程最短的路线。把路口抽象成图的节点把路口间的路段抽象成边路段的长度就是边的权重整个问题就变成了在加权无向图上求出两个指定节点之间的最小权重路径。这是最经典的应用场景后续动辄出现几十个节点的地图手工人眼已经不可能枚举所有路径必须交给算法。但要注意一个认知误区最短路径不等于经过最少的边。两条路线一条经过3条边但每条都很长另一条经过5条边但每条都很短后者总权重反而更小。把权重从边的数量提升到边的真实代价后处理问题的精度立刻上升了一个层次。地图导航、物流配送、电路布线本质上都在复用这个模型。1.2 通信网络里的线路规划问题再看另一个场景某公司有6个机房要互联任意两个机房之间直接拉光纤的造价不一样有些线路便宜但路径远有些线路贵但延迟低。现在要求让6个机房全部连通、整体造价最低这跟最短路径是不同的模型——它不关心从某个点到另一个点怎么走最省而是关心整张网络怎么连成一个整体时总成本最少。这个问题的数学名称叫最小生成树是加权无向图的第二个核心应用。我当年在某个模拟项目里就遇到类似的网络规划需求节点从10个涨到50个之后贪心手选方案会因为局部最便宜导致全局绕路的问题彻底失效。直到把问题抽象成最小生成树才算真正找到稳定解法。理解加权无向图的这两个核心问题——单源最短路径和最小生成树就抓住了它的主要战场。2. 图的存储方式搞清楚内存结构再动手写算法算法写不好八成是数据结构没选对。加权无向图在计算机里最常见的两种存储结构是邻接矩阵和邻接表两者的取舍直接决定了代码的复杂度和运行表现。2.1 邻接矩阵写起来爽省心但费内存邻接矩阵用一个二维数组adj[i][j]表示节点i到节点j的边的权重。因为图是没有方向的所以矩阵一定是对称的adj[i][j] adj[j][i]。如果两点之间没有边就放一个无穷大值表示无法直接到达。class WeightedGraphMatrix: def __init__(self, n): self.n n INF float(inf) self.adj [[INF] * n for _ in range(n)] for i in range(n): self.adj[i][i] 0 def add_edge(self, u, v, weight): self.adj[u][v] weight self.adj[v][u] weight def get_weight(self, u, v): return self.adj[u][v]这段代码很容易懂add_edge在矩阵里对称写入权重查询两点间的权重时直接按下标取。它的优点是查询是否连通复杂度为O(1)写起来直观。缺点是内存开销太大1000个节点就要开1000×1000个数字100000个节点根本存不下。它在稠密图边数接近节点数平方或者节点数在几千以内的场景下才划算。2.2 邻接表真实项目中几乎都是它邻接表为每个节点保存一张邻居和边权重的列表只存储真实存在的边。无向图里加一条边u-v时需要在u的邻接表里加(v, weight)在v的邻接表里加(u, weight)。from collections import defaultdict class WeightedGraphAdj: def __init__(self, n): self.n n self.adj [[] for _ in range(n)] def add_edge(self, u, v, weight): # 无向边两侧都要记录 self.adj[u].append((v, weight)) self.adj[v].append((u, weight)) def neighbors(self, u): return self.adj[u]邻接表最大的好处是内存跟边数成正比稀疏图边数远小于节点数平方下极为省空间遍历某个节点的所有邻居时只需要扫一遍对应链表复杂度O(degree(u))。Dijkstra、Prim等基于松弛邻居的算法天然匹配邻接表。实际工程里除非节点数小于几百否则我基本都是无脑选邻接表。2.3 从文件到内存真实图的加载方式实际拿到的图数据往往是文本文件比如每行三个数字表示端点1 端点2 权重。加载时要处理的下标偏移、重复边这两个问题很常见。def load_graph_from_file(file_path, n): g WeightedGraphAdj(n) with open(file_path, r, encodingutf-8) as f: for line in f: line line.strip() if not line or line.startswith(#): continue parts line.split() if len(parts) ! 3: continue u, v, w int(parts[0]), int(parts[1]), float(parts[2]) # 有的文件节点编号从1开始需要转成0开始 g.add_edge(u - 1, v - 1, w) return g我之前踩过最隐蔽的坑是同一对节点在文件里出现了多条边比如先写了1 2 5后面又写了2 1 3。理论上它们是同一条边但程序会当成两条平行边处理导致算法结果错误。正确做法是在add_edge里做去重判断def add_edge(self, u, v, weight): for existing_v, existing_w in self.adj[u]: if existing_v v: # 保留较小权重那一条 if weight existing_w: self.adj[u].remove((existing_v, existing_w)) self.adj[v].remove((u, existing_w)) else: return break self.adj[u].append((v, weight)) self.adj[v].append((u, weight))这个细节在教科书上几乎不会讲但在现实数据里一旦出现基本就是排查半天。3. 单源最短路径Dijkstra算法的完整代码与原理剖析加权无向图最有名的问题就是单源最短路径给定起点s求s到所有其他节点的最短路径长度。Dijkstra算法是最常用的解法前提是边的权重不能为负数。3.1 算法流程别把它想成动态规划或贪心的玄学Dijkstra的思路用一句话概括每次从未确定最短路径的节点中选一个当前距离最小的节点把它标记为已确定然后尝试用它去松弛更新它所有邻居的距离。重复这个过程直到所有节点都被确定。这里的当前距离最小就是从起点出发、经过已确定节点、到达该节点的最优距离。因为边权非负所以任何绕路都不可能让这个距离变得更短于是它一旦被选中就可以永久确定。3.2 优先队列实现能处理十万级节点不用优先队列的朴素版本复杂度是O(n²)而用堆优化的版本是O((n m) log n)其中m是边数。在有边数稀疏的现实网络里堆优化版本优势明显。import heapq def dijkstra(g, start): n g.n INF float(inf) dist [INF] * n dist[start] 0 visited [False] * n prev [-1] * n # 记录路径前驱方便回溯 pq [(0, start)] # (距离, 节点) while pq: d, u heapq.heappop(pq) if visited[u]: continue visited[u] True for v, w in g.neighbors(u): if visited[v]: continue new_dist d w if new_dist dist[v]: dist[v] new_dist prev[v] u heapq.heappush(pq, (new_dist, v)) return dist, prev def reconstruct_path(prev, target): path [] cur target while cur ! -1: path.append(cur) cur prev[cur] path.reverse() return path注意这里的visited判断同一个节点可能被优先队列加入多次但每次弹出的距离值不同。一旦弹出时发现它已经被确定过就直接跳过。我见过不少新手把这步遗漏导致结果虽然在大多数数据上没问题但遇到相同距离的节点时会出错。还有一个细节堆里存的是(距离, 节点)因为Python元组按第一个元素比较这样堆顶永远是距离最小的项。3.3 手动推演一轮为什么BFS直接扩展行不通写几行代码容易知道它为什么正确才值钱。看这个最小例子节点0到节点30到1的边权重为40到2的边权重为11到3的边权重为12到3的边权重为5如果像无权图BFS那样按层数扩展会走0→1→3总代价415。但正确路径是0→2→3总代价156吗等一下重新算156大于5所以BFS恰好歪打正着。换个构造0到1权重10到2权重0.51到3权重0.52到3权重10。BFS先走0→1→3总代价1.5而Dijkstra会先确认节点2距离0.5再确认节点1时已是0.511.5两者结果一样但如果再改成0到1权重1000到2权重11到3权重12到3权重1。BFS按层数是0→1→3代价101正确是0→2→3代价2。这个例子很好地说明了经过最少边≠权重最小必须按权重从小到大扩展而不是按跳数扩展。Dijkstra每一次扩展都是全局最优候选并且由于所有边权非负不会出现先绕了一下很长的路再到目标反而更短的情况。3.4 最短路径树可以顺带解决一堆子问题上面代码里的prev数组本质上构建了从起点出发的一棵最短路径树。这棵树的价值在于给定同一个起点它能一次性回答到任意节点k的最短路径是什么而不需要重新跑算法。比如快递中心到所有配送点的最优路线、分布式系统里心跳包的最优扩散树都能复用这棵树。但如果换了一个起点必须重新计算。4. 最小生成树Prim算法的直觉、代码与典型误区第二个核心问题是给定一个加权无向连通图选择一部分边使得所有节点连通并且选中边的总权重最小。注意这里的目标不是点到点的路径最短而是连通全局的总成本最低。4.1 Prim算法的核心直觉从一个点开始“自然地长成一棵树”Prim算法可以理解成每次从已经连通的集合向外选择一条能连接集合外节点的、权重最小的边把那个节点拉进集合。重复直到所有节点都被拉进来。因为每次只扩展一个节点、只增加一条边且永远不会形成环所以结果一定是一棵树又因为每次选的都是当前割的最小边最后由交换论证可以证明它是全局最优的最小生成树。def prim(g, start0): n g.n INF float(inf) dist [INF] * n parent [-1] * n visited [False] * n dist[start] 0 pq [(0, start)] # (到当前树的距离, 节点) mst_weight 0 mst_edges [] while pq: d, u heapq.heappop(pq) if visited[u]: continue visited[u] True mst_weight d if parent[u] ! -1: mst_edges.append((parent[u], u, d)) for v, w in g.neighbors(u): if not visited[v] and w dist[v]: dist[v] w parent[v] u heapq.heappush(pq, (w, v)) return mst_weight, mst_edges注意这里跟Dijkstra的关键差异Prim里比较的是节点到生成树的距离也就是生成树集合里某个节点到外部节点的边权而不是路径总距离。虽然代码长得几乎一样dist的语义完全不同。4.2 那个常见的误区把Prim写成Dijkstra我第一次手写Prim就是直接抄Dijkstra把new_dist d w当成新的候选距离结果生成树总权重比正确值大不少。原因在于Prim只需要当前外部节点连到树上的一条最小边积累路径总长度反而会把之前的边权重复计入让短边的节点被错误延迟。要记住的检查方法是跑完后把选中的所有边权相加用朴素DFS验证所有节点是否连通并且检查总边数是否为n-1。如果多了说明产生了环如果少了说明原图本身不连通。4.3 何时选Prim而不选KruskalPrim适合稠密图因为它每次都在已连通的树的边界上选最小边堆操作次数约等于边数。用邻接矩阵实现Prim可以做到O(n²)在完全图每对节点都有边上也稳定。而后续要讲的Kruskal需要把所有边排序稠密图里排序成本很高所以一般稠密选Prim、稀疏选Kruskal。5. 最小生成树另一解法Kruskal并查集实现与选择对比如果说Prim是从一个点往外长Kruskal就是把所有边拿过来排队能连就连注意别连成环。5.1 算法步骤边排序并查集防环先把所有边按权重从小到大排序然后逐条尝试。如果一条边连接的两个节点目前还不属于同一个连通分量就选它如果已经连通就跳过否则会形成环。这个判断是否同一个连通分量的操作最适合用并查集做好路径压缩后近O(1)。class DSU: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): rx, ry self.find(x), self.find(y) if rx ry: return False if self.rank[rx] self.rank[ry]: self.parent[rx] ry elif self.rank[rx] self.rank[ry]: self.parent[ry] rx else: self.parent[ry] rx self.rank[rx] 1 return True def kruskal(g): edges [] for u in range(g.n): for v, w in g.neighbors(u): if u v: # 避免重复记录无向边 edges.append((w, u, v)) edges.sort(keylambda x: x[0]) dsu DSU(g.n) mst_weight 0 mst_edges [] for w, u, v in edges: if dsu.union(u, v): mst_weight w mst_edges.append((u, v, w)) if len(mst_edges) g.n - 1: break return mst_weight, mst_edges这里有个容易忽略的重边问题无向图里一条边在邻接表中会被存两次比如adj[0]里包含(1, 5)adj[1]里也会包含(0, 5)。如果两条都加进edges虽然并查集会跳过其中一条但排序和遍历成本翻倍。用if u v只取一端既省空间又防止重复统计权重。我第一次没处理导致统计出的总权重恰好是两份排查了很久才发现是数据源的问题。5.2 Prim与Kruskal的对比什么场景该用谁对比项Prim堆优化Kruskal核心操作用优先队列在树边界选最小边对所有边排序后逐条尝试时间复杂度O((n m) log n)O(m log n)主要花在排序数据结构邻接表/邻接矩阵 堆边列表 并查集稠密图m接近n²更优无需全局排序排序成本偏高稀疏图m接近n也不错但堆操作多更直观通常更快实现细节要区分dist和路径距离要注意无向边去重我的建议是如果代码是自己维护、节点数量在几千到几万之间两者性能差距肉眼几乎感知不到选你觉得更不容易写错的。但如果图特别大、边数特别多Kruskal的排序可能成为瓶颈反过来如果图是天然带坐标的网格图比如游戏地图格子Prim反而更容易利用空间局部性。5.3 不连通图的最小生成树行为一个经典问题图本身不连通时算法会怎样Prim会提前结束此时visited里还有false节点说明不存在包含所有节点的生成树。Kruskal结束后len(mst_edges) n - 1同样说明图不连通。很多竞赛题会把判连通和求MST同时考所以代码里不要盲目假设一定选得够n-1条边。可以在算法跑完后检查边数用这个指标判断图是否连通而不是再单独跑一遍DFS。6. 负权边、断图与性能实测我亲历的几个排错现场前面所有算法原理都建立在边权非负这个前提上。现实世界的成本、距离、时间一般不会是负数但有些建模场景里负权会出现——比如收益、折扣率或者图里存在奖励边。这种情况下直接套Dijkstra会得到错误结果。6.1 负权边为什么让Dijkstra翻车Dijkstra的每次选中距离最小的节点就永久确定依赖一个隐含事实任何后续路径只要经过了更多边总权重就不可能比当前值更小。但如果存在负权边绕路反而可能让总权重变小之前的永久确定就被打破了。构造一个最简单的反例0→1边权为50→2边权为102→1边权为-5。从0出发Dijkstra会先确认距离为5的节点1路径是0→1。但实际上0→2→1的总权重是10(-5)5跟0→1一样如果我把0→1改成100→2改成102→1改成-5那正确结果是5Dijkstra却会在第一步就确认节点1距离10之后再发现路径0→2→1时已经晚了。面对负权边正确的标准解法是Bellman-Ford算法它通过对所有边做n-1轮松弛来找到最短路径能处理负权但不能处理负权环。6.2 大图性能实测堆优化Dijkstra到底能跑多快我在一个模拟项目里用随机生成的稀疏图做过测试节点数n100000边数m≈300000起点设置为0。堆优化Dijkstra跑完整轮返回所有节点的最短路径PyPy环境下耗时大约0.8秒左右换成朴素O(n²)版本在同样数据上直接跑出几十秒甚至更久。影响性能的另一个因素是Python的heapq在频繁push/pop时的对象开销。可以用懒更新策略不主动删除堆里过期的旧距离只在弹出时判断是否比dist里的值大如是则跳过。上面的代码已经用了这个策略实际效果非常明显少了大量heapq删除操作。另一个优化技巧是用预分配的数组代替字典存dist。如果节点编号不是从0开始的连续整数可以先做一个编号映射。我在某个图数据里看到节点编号从1000跳到了99999直接开数组内存爆炸后来用字典做映射把稀疏编号压缩成连续编号内存和速度都得到了保证。6.3 输入数据正确性的几个隐藏陷阱除了前面说过的重复边还有几个高频问题自环节点到自己的边权重不管多大在最短路径和MST里都不应该产生影响。但代码里如果不判断可能会把自环重复加进MST的候选导致误判。权重精度很多图数据的权重是浮点数直接用判断两条路径权重是否相等可能因为浮点误差带来随机性。我习惯在比较时加一个极小epsilon如1e-9或者干脆把权重放大成整数处理。节点编号从0还是从1开始文件里多半从1开始数组下标从0开始转换漏掉一处就会越界。我写load_graph_from_file时专门做了一个offset 1 if min_node_id 1 else 0的适配这样既能处理从0开始也能处理从1开始的数据。有向边混入无向图文件数据源如果来自某些爬虫或者多模态系统会混入单向边。如果不检测只用add_edge(u, v, w)加双向往返会把单向路径错误地当成可逆路径。处理这些问题的更稳妥方案是写一个统一的validate_graph函数在加载后遍历所有邻接表检查每条边是否对称存在、权重是否一致、是否存在负权、节点编号是否越界。这比在算法里加一百个if更靠谱。7. 这段旅程的最终收获与三个可复用小工具加权无向图作为一个基础数据结构真正难的不是理解概念而是亲手把一个真实世界的网络问题成功映射成图然后用合适的算法跑通、跑快、跑准。我在前前后后花了约两周时间反复写、反复优化之后最终的收获可以浓缩成几个可以直接复用的判断准则路线的总成本最小问题优先想到Dijkstra全部节点要连通、总成本最小优先想到Prim或Kruskal图的存储能上邻接表就不上邻接矩阵算法跑不通时先检查图的读入数据有没有重复边、自环、负权、单向不对称而不是盯着算法本身死磕。我还顺手封装了三个小工具build_graph_from_edges从边列表建图并自动去重、validate_graph检查图结构完整性、visualize_small_graph用文本方式输出邻接表便于调试。对小型图来说文本打印邻接表往往比可视化库更快定位问题。最后记录一个我个人的小习惯写完最短路径、最小生成树这类图算法后一定要额外构造至少一个特殊用例来验证。我的固定测试集包含单节点图、两个节点的单边图、完全图、链状图、不连通图、重复边图和带自环图。跑完这些用例之后代码的稳定性会有一个肉眼可见的提升。希望这篇梳理能帮你在自己的项目里少走几个弯路。