1. 简介
在本文中，我们将重点介绍两个图论中的经典问题：最小生成树（Minimum Spanning Tree, MST） 和 最短路径树（Shortest Path Tree, SPT）。
这两个问题都可以使用贪心算法来解决，且它们的算法结构非常相似。理解它们之间的异同，有助于我们更好地掌握图算法的设计思路。
2. 生成树（Spanning Tree）
生成树是一个无向图 G 的子图，它连接了图中的所有节点，且不包含环，边的数量最少。
一个图可能有多个不同的生成树。下图展示了一个图及其一个生成树（红色边）：
3. 最小生成树（Minimum Spanning Tree）
如果图的边有权重，我们可以定义一个生成树的总权重为它所有边的权重之和。最小生成树就是所有生成树中权重最小的那个。
下图展示了一个边加权图的最小生成树：
我们可以通过多种算法求解 MST，包括 Prim 算法、Kruskal 算法 和 Boruvka 算法。
我们以 Prim 算法为例，因为它与最短路径树的解法结构相似：
algorithm PrimsAlgorithmForMST:
// INPUT
// G = a graph with weighted edges
// OUTPUT
// Returns the minimum spanning tree
Initialize a node set S1 with an arbitrary node u from G
Put all the other nodes in G into a node set S2
Initialize an empty edge set T to store minimum spanning tree edges
Initialize an edge set E to store edges that have one end node in S1 and another end node in S2
Insert all edges {{u, v} | v in S2} into E
while S2 is not empty:
Select an edge {u, v | u in S1, v in S2} from E that has the minimum weight
Add {u, v} to T
Remove {u, v} from E
Remove v from S2 and add it to S1
Insert all edges {v, w | w in S2} into E
return T
我们来用图示逐步运行 Prim 算法：
Prim 算法的时间复杂度取决于图的表示方式：
- 如果使用邻接矩阵，复杂度为 ✅ O(V²)
- 如果使用邻接表 + 优先队列，复杂度为 ✅ O(E log V)
4. 最短路径树（Shortest Path Tree）
最短路径树问题中，我们从一个源节点 s 出发，目标是构建一棵生成树，使得从 s 到图中任意节点 v 的路径都是最短的。
换句话说：最短路径树是一棵以 s 为根节点的生成树，树中每个节点到根节点的路径都是原图中该节点到根节点的最短路径。
这个问题可以用 Dijkstra 算法解决：
algorithm DijkstrasAlgorithmForShortestPathTree:
// INPUT
// G = a graph with weighted edges
// s = the source node
// OUTPUT
// A shortest path tree of G rooted at s
Initialize a node set S1 with s
Assign a distance value 0 to node s: Dist(s) <- 0
Put all the other nodes in G into a node set S2
Initialize an empty edge set T to store shortest path tree edges
Initialize an edge set E to store edges that have one end node in S1 and another end node in S2
Add all edges {u, v | v in S2} into E
while S2 is not empty:
Select an edge {u, v | u in S1, v in S2} from E that has the minimum Dist(u) + weight(u, v)
Add {u, v} to T
Remove {u, v} from E
Remove v from S2 and add it to S1
Dist(v) <- Dist(u) + weight(u, v)
Add all edges {v, w | w in S2} into E
return T
Dijkstra 算法的结构和 Prim 算法非常相似，但选择策略不同：
| 算法 | 选择策略 |
|---|---|
| Prim | 选择连接 S1 和 S2 的最小权重边 |
| Dijkstra | 选择从源点出发路径最短的节点 |
因此，对于同一个图，MST 和 SPT 可能不同。
我们用图示运行 Dijkstra 算法，源节点为 0：
比如，节点 0 到 3 的最短路径是 0->1->3，但这条边不在最小生成树中，说明两种算法生成的树结构是不同的。
Dijkstra 的时间复杂度也取决于图的表示方式：
- 邻接矩阵：✅ O(V²)
- 邻接表 + 优先队列：✅ O(E log V)
5. 总结
| 对比点 | 最小生成树 (MST) | 最短路径树 (SPT) |
|---|---|---|
| 目标 | 总权重最小的生成树 | 每个节点到源点的路径最短 |
| 常用算法 | Prim, Kruskal | Dijkstra |
| 选择策略 | 最小边权重 | 最短路径长度 |
| 应用场景 | 网络铺设、电力布线 | 路由选择、导航系统 |
✅ 踩坑提醒：
- 不要混淆 Prim 和 Dijkstra 的选择标准，一个是看边权，一个是看路径长度。
- 实现时注意数据结构的选择，尤其是优先队列的使用对性能影响很大。
详细的实现可参考我们关于 Prim 算法 和 Dijkstra 算法 的专题文章。