目录
一、概念介绍
在无向连通加权图中，生成树是一个包含所有顶点的无环子图。 如果我们为每条边赋予权重（通常表示成本、距离、时间等），则最小生成树是所有生成树中权重之和最小的那棵树。
最小生成树的性质：
顶点数固定：MST包含图中所有的顶点。
边数为 n-1：对于 n 个顶点的连通无向图，生成树恰好有 n-1 条边。
无环性：MST中不允许出现环。
最小权重：总权重在所有生成树中是最小的。
应用场景：
网络设计：构建通信网络、电网、计算机网络时，最小化建设成本。
道路规划：最小化公路、铁路或管道的建设长度。
聚类分析：在数据聚类中用MST来发现数据的结构。
图像处理：用于图像分割等计算机视觉任务。
物流配送：寻找最经济的配送路径（不是最短路径问题，而是覆盖所有地点的最小代价）。
概念理解：
节点（Node） 图中的顶点，代表实体（例如城市、网络设备、仓库等）。
边（Edge） 图中连接两个顶点的线段，带有权重（例如距离、费用、延迟等）。
权重（Weight） 边的数值属性，用于衡量连接两个节点的“成本”。
无向图 边的方向不区分“起点”和“终点”，即边
(u, v)与(v, u)等价。连通性 从任意节点可以到达其他任意节点的图称为连通图。
无环性 图中不存在回路。生成树一定是无环的。
并查集（Union-Find） 一种用于检测两个顶点是否属于同一个连通分量的数据结构，常用于 Kruskal 算法中避免形成环。
二、两种典型的MST算法
1. Prim 算法
算法思想
Prim 算法从某个起始节点出发，不断选择权重最小且能连接新的未访问节点的边，直到所有节点都被包含进来。 其过程类似于“从一个点出发，不断扩展到最近的未访问节点”。
核心步骤
从任意一个顶点开始，将其加入已访问集合。
将该顶点的所有边加入优先队列（按权重排序）。
从优先队列中取出权重最小的边，如果它连接的节点未被访问，则将该节点加入已访问集合，并将其边加入优先队列。
重复步骤3，直到所有顶点都被访问或队列为空。
Java实现（Prim）：
package graph;
import java.util.*;
/**
* 无向图 无环 连通
*/
public class MinimumSpanningTrees {
/**
* prim算法求解最小生成树
*
* @param nodes
*/
public static List<Edge> primMST(List<Node> nodes) {
if (nodes.isEmpty()) return Collections.emptyList();
List<Edge> mst = new ArrayList<>();
PriorityQueue<Edge> edgeQueue = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight)); // 存储访问过的节点集合对应的边集合，并且按照权重排序
Set<Node> visited = new HashSet<>(); // 存储访问过的节点集合
// 从第一个节点开始
Node startNode = nodes.get(3);
visited.add(startNode);
edgeQueue.addAll(startNode.adj);
while (!edgeQueue.isEmpty() && visited.size() < nodes.size()) {
Edge minEdge = edgeQueue.poll();
Node nextNode = minEdge.to;
if (!visited.contains(nextNode)) {
visited.add(nextNode);
mst.add(minEdge);
// 添加新节点的所有边到优先队列
for (Edge edge : nextNode.adj) {
if (!visited.contains(edge.to)) {
edgeQueue.add(edge);
}
}
}
}
return mst;
}
public static void main(String[] args) {
Node v1 = new Node("v1");
Node v2 = new Node("v2");
Node v3 = new Node("v3");
Node v4 = new Node("v4");
Node v5 = new Node("v5");
Node v6 = new Node("v6");
Node v7 = new Node("v7");
v1.addEdge(v2,2);
v1.addEdge(v3,4);
v1.addEdge(v4,1);
v2.addEdge(v1,2);
v2.addEdge(v5,10);
v2.addEdge(v4,3);
v3.addEdge(v1,4);
v3.addEdge(v4,2);
v3.addEdge(v6,5);
v4.addEdge(v1,1);
v4.addEdge(v2,3);
v4.addEdge(v3,2);
v4.addEdge(v5,7);
v4.addEdge(v6,8);
v4.addEdge(v7,4);
v5.addEdge(v2,10);
v5.addEdge(v4,7);
v5.addEdge(v7,6);
v6.addEdge(v3,5);
v6.addEdge(v4,8);
v6.addEdge(v7,1);
v7.addEdge(v4,4);
v7.addEdge(v5,6);
v7.addEdge(v6,1);
List<Node> nodes = Arrays.asList(v1, v2, v3, v4, v5, v6, v7);
List<Edge> edges = primMST(nodes);
System.out.println("Total weight: " + edges.stream().map(item -> item.weight).reduce(0, Integer::sum));
for(Edge edge:edges){
System.out.println(edge.from.name + "->" + edge.to.name + ":" + edge.weight);
}
}
}
执行结果
Total weight: 16 v4->v1:1 v4->v3:2 v1->v2:2 v4->v7:4 v7->v6:1 v7->v5:6
2. Kruskal 算法
算法思想
Kruskal 算法是一种“边驱动”策略，按权重升序对所有边排序，然后依次选择最小的边加入生成树，但前提是不会形成环。 使用并查集判断加入边后是否形成环。
核心步骤
将所有边按权重升序排序。
初始化并查集，每个节点是一个独立集合。
依次取最小的边，若该边的两个端点属于不同集合，则将其加入MST，并合并两个集合。
当MST中边数达到
n-1时结束。
Java实现（Kruskal）：
package graph;
import java.util.*;
/**
* 无向图 无环 连通
*/
public class MinimumSpanningTrees {
/**
* Kruskal算法求解最小生成树
*
* @param nodes 图中的所有节点
* @return 最小生成树的边集合
*/
public static List<Edge> kruskalMST(List<Node> nodes) {
if (nodes.isEmpty()) return Collections.emptyList();
List<Edge> mst = new ArrayList<>();
// 收集所有边,按权重从小到大排序
List<Edge> allEdges = new ArrayList<>();
for (Node node : nodes) {
allEdges.addAll(node.adj);
}
allEdges.sort(Comparator.comparingInt(e -> e.weight));
// 使用【并查集】来检测环
UnionFind uf = new UnionFind(nodes);
for (Edge edge : allEdges) {
Node from = edge.from;
Node to = edge.to;
if (!uf.isConnected(from, to)) { // 判断两个集合能否联通
mst.add(edge);
uf.union(from, to);
}
// 如果已经连接了所有节点，提前退出
if (mst.size() == nodes.size() - 1) {
break;
}
}
return mst;
}
public static void main(String[] args) {
Node v1 = new Node("v1");
Node v2 = new Node("v2");
Node v3 = new Node("v3");
Node v4 = new Node("v4");
Node v5 = new Node("v5");
Node v6 = new Node("v6");
Node v7 = new Node("v7");
v1.addEdge(v2,2);
v1.addEdge(v3,4);
v1.addEdge(v4,1);
v2.addEdge(v1,2);
v2.addEdge(v5,10);
v2.addEdge(v4,3);
v3.addEdge(v1,4);
v3.addEdge(v4,2);
v3.addEdge(v6,5);
v4.addEdge(v1,1);
v4.addEdge(v2,3);
v4.addEdge(v3,2);
v4.addEdge(v5,7);
v4.addEdge(v6,8);
v4.addEdge(v7,4);
v5.addEdge(v2,10);
v5.addEdge(v4,7);
v5.addEdge(v7,6);
v6.addEdge(v3,5);
v6.addEdge(v4,8);
v6.addEdge(v7,1);
v7.addEdge(v4,4);
v7.addEdge(v5,6);
v7.addEdge(v6,1);
List<Node> nodes = Arrays.asList(v1, v2, v3, v4, v5, v6, v7);
List<Edge> edges = kruskalMST(nodes);
System.out.println("Total weight: " + edges.stream().map(item -> item.weight).reduce(0, Integer::sum));
for(Edge edge:edges){
System.out.println(edge.from.name + "->" + edge.to.name + ":" + edge.weight);
}
}
}
并查集（Union-Find）实现
/**
* 并查集
*/
class UnionFind {
private Map<Node, Node> parent; // 构造森林
private Map<Node, Integer> rank;
public UnionFind(List<Node> nodes) {
parent = new HashMap<>();
rank = new HashMap<>();
for (Node node : nodes) {
parent.put(node, node);
rank.put(node, 0);
}
}
public Node find(Node node) {
if (parent.get(node) != node) {
parent.put(node, find(parent.get(node))); // 递归路径压缩
}
return parent.get(node);
}
public boolean isConnected(Node x, Node y) {
return find(x) == find(y);
}
public void union(Node x, Node y) {
Node rootX = find(x);
Node rootY = find(y);
if (rootX == rootY) return;
// 按秩合并
if (rank.get(rootX) > rank.get(rootY)) {
parent.put(rootY, rootX);
} else if (rank.get(rootX) < rank.get(rootY)) {
parent.put(rootX, rootY);
} else {
parent.put(rootY, rootX);
rank.put(rootX, rank.get(rootX) + 1);
}
}
}
三、两种算法对比
| 算法 | 思路 | 数据结构 | 复杂度 | 适用场景 |
|---|---|---|---|---|
| Prim | 从点出发扩展最小边 | 优先队列 + 集合 | O(E log V) | 稠密图 |
| Kruskal | 从小边开始构建树 | 排序 + 并查集 | O(E log E) | 稀疏图 |
Prim 更适合稠密图（边很多），因为它每次只扩展到一个新的节点。
Kruskal 更适合稀疏图（边少），因为它先全局排序再选择边