当前位置：首页 > news >正文

图论(5)最小生成树算法

news 2025/8/15 14:04:19

一、概念介绍

二、两种典型的MST算法

1. Prim 算法

2. Kruskal 算法

三、两种算法对比

一、概念介绍

在无向连通加权图中，生成树是一个包含所有顶点的无环子图。如果我们为每条边赋予权重（通常表示成本、距离、时间等），则最小生成树是所有生成树中权重之和最小的那棵树。

最小生成树的性质：

顶点数固定：MST包含图中所有的顶点。
边数为 n-1：对于 n 个顶点的连通无向图，生成树恰好有 n-1 条边。
无环性：MST中不允许出现环。
最小权重：总权重在所有生成树中是最小的。

应用场景：

网络设计：构建通信网络、电网、计算机网络时，最小化建设成本。
道路规划：最小化公路、铁路或管道的建设长度。
聚类分析：在数据聚类中用MST来发现数据的结构。
图像处理：用于图像分割等计算机视觉任务。
物流配送：寻找最经济的配送路径（不是最短路径问题，而是覆盖所有地点的最小代价）。

概念理解：

节点（Node） 图中的顶点，代表实体（例如城市、网络设备、仓库等）。
边（Edge） 图中连接两个顶点的线段，带有权重（例如距离、费用、延迟等）。
权重（Weight） 边的数值属性，用于衡量连接两个节点的“成本”。
无向图 边的方向不区分“起点”和“终点”，即边 (u, v) 与 (v, u) 等价。
连通性 从任意节点可以到达其他任意节点的图称为连通图。
无环性 图中不存在回路。生成树一定是无环的。
并查集（Union-Find） 一种用于检测两个顶点是否属于同一个连通分量的数据结构，常用于 Kruskal 算法中避免形成环。

二、两种典型的MST算法

1. Prim 算法

算法思想

Prim 算法从某个起始节点出发，不断选择权重最小且能连接新的未访问节点的边，直到所有节点都被包含进来。其过程类似于“从一个点出发，不断扩展到最近的未访问节点”。

核心步骤
1. 从任意一个顶点开始，将其加入已访问集合。
2. 将该顶点的所有边加入优先队列（按权重排序）。
3. 从优先队列中取出权重最小的边，如果它连接的节点未被访问，则将该节点加入已访问集合，并将其边加入优先队列。
4. 重复步骤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 算法是一种“边驱动”策略，按权重升序对所有边排序，然后依次选择最小的边加入生成树，但前提是不会形成环。使用并查集判断加入边后是否形成环。

核心步骤
1. 将所有边按权重升序排序。
2. 初始化并查集，每个节点是一个独立集合。
3. 依次取最小的边，若该边的两个端点属于不同集合，则将其加入MST，并合并两个集合。
4. 当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);}}
}