做图论或者日常写路径规划、网络拓扑、推荐关系链的朋友，一定绕不开一个基础又灵活的数据结构——加权无向图。它解决的是一个很朴素的问题：一堆节点之间有相连的边，每条边有一个代价值，你怎么在图上求出从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', encoding='utf-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到节点3：

• 0到1的边权重为4，0到2的边权重为1
• 1到3的边权重为1，2到3的边权重为5

如果像无权图BFS那样按"层数"扩展，会走0→1→3，总代价4+1=5。但正确路径是0→2→3，总代价1+5=6吗？等一下，重新算：1+5=6，大于5，所以BFS恰好歪打正着。换个构造：0到1权重1，0到2权重0.5，1到3权重0.5，2到3权重10。BFS先走0→1→3总代价1.5，而Dijkstra会先确认节点2距离0.5，再确认节点1时已是0.5+1=1.5，两者结果一样；但如果再改成0到1权重100，0到2权重1，1到3权重1，2到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, start=0): 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而不选Kruskal

Prim适合稠密图，因为它每次都在"已连通的树"的边界上选最小边，堆操作次数约等于边数。用邻接矩阵实现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(key=lambda 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的对比：什么场景该用谁

我的建议是：如果代码是自己维护、节点数量在几千到几万之间，两者性能差距肉眼几乎感知不到，选你觉得更不容易写错的。但如果图特别大、边数特别多，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边权为5，0→2边权为10，2→1边权为-5。从0出发，Dijkstra会先确认距离为5的节点1，路径是0→1。但实际上0→2→1的总权重是10+(-5)=5，跟0→1一样；如果我把0→1改成10，0→2改成10，2→1改成-5，那正确结果是5，Dijkstra却会在第一步就确认节点1距离10，之后再发现路径0→2→1时已经晚了。面对负权边，正确的标准解法是Bellman-Ford算法，它通过对所有边做n-1轮松弛来找到最短路径，能处理负权但不能处理负权环。

6.2 大图性能实测：堆优化Dijkstra到底能跑多快

我在一个模拟项目里用随机生成的稀疏图做过测试：节点数n=100000，边数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（用文本方式输出邻接表便于调试）。对小型图来说，文本打印邻接表往往比可视化库更快定位问题。

最后记录一个我个人的小习惯：写完最短路径、最小生成树这类图算法后，一定要额外构造至少一个特殊用例来验证。我的固定测试集包含：单节点图、两个节点的单边图、完全图、链状图、不连通图、重复边图和带自环图。跑完这些用例之后，代码的稳定性会有一个肉眼可见的提升。希望这篇梳理能帮你在自己的项目里少走几个弯路。