贪心算法之最小生成树详细解读（附带Java代码解读）
最小生成树（MST）是连接图中所有顶点的一个生成树，并且使得树中所有边的权重之和最小。常见的计算最小生成树的算法有两种：Kruskal算法和Prim算法。
1. Kruskal算法
Kruskal算法是一种基于贪心思想的算法，它通过将图中的边按权重从小到大排序，然后逐步选择不会形成环的边，直到构造出最小生成树。
算法步骤：
- 将图中的所有边按照权重升序排序。
- 初始化一个空的边集，用于存储最小生成树的边。
- 使用并查集（Disjoint Set Union，DSU）来管理每个顶点的连通性。最开始每个顶点各自是一个集合。
- 按顺序遍历每条边：
- 如果该边连接的两个顶点属于不同的集合，则将该边加入最小生成树，并合并这两个顶点的集合。
- 否则，跳过这条边。
- 重复此过程，直到最小生成树中包含 n−1n-1n−1 条边（其中 nnn 是图的顶点数）。
Kruskal算法的Java实现
import java.util.*;class Edge implements Comparable<Edge> {int src, dest, weight;public Edge(int src, int dest, int weight) {this.src = src;this.dest = dest;this.weight = weight;}// 按照边的权重升序排序public int compareTo(Edge compareEdge) {return this.weight - compareEdge.weight;}
}class Subset {int parent, rank;
}public class KruskalMST {int vertices, edges;Edge[] edgeArray;public KruskalMST(int vertices, int edges) {this.vertices = vertices;this.edges = edges;edgeArray = new Edge[edges];}// 找到子集的根节点int find(Subset[] subsets, int i) {if (subsets[i].parent != i) {subsets[i].parent = find(subsets, subsets[i].parent);}return subsets[i].parent;}// 合并两个子集void union(Subset[] subsets, int x, int y) {int xroot = find(subsets, x);int yroot = find(subsets, y);if (subsets[xroot].rank < subsets[yroot].rank) {subsets[xroot].parent = yroot;} else if (subsets[xroot].rank > subsets[yroot].rank) {subsets[yroot].parent = xroot;} else {subsets[yroot].parent = xroot;subsets[xroot].rank++;}}// Kruskal最小生成树算法void kruskalMST() {Edge[] result = new Edge[vertices]; // 最终存储最小生成树的边int e = 0; // 当前结果中的边的数量int i = 0; // 排序后的边的索引for (i = 0; i < vertices; ++i) {result[i] = new Edge(0, 0, 0);}// 按照边的权重升序排序Arrays.sort(edgeArray);// 创建子集Subset[] subsets = new Subset[vertices];for (i = 0; i < vertices; ++i) {subsets[i] = new Subset();subsets[i].parent = i;subsets[i].rank = 0;}i = 0;while (e < vertices - 1) {// 选择最小权重的边Edge nextEdge = edgeArray[i++];int x = find(subsets, nextEdge.src);int y = find(subsets, nextEdge.dest);// 如果边的两个顶点不在同一个集合中，则加入结果集if (x != y) {result[e++] = nextEdge;union(subsets, x, y);}}// 输出最小生成树System.out.println("以下是最小生成树的边：");for (i = 0; i < e; ++i) {System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);}}public static void main(String[] args) {int vertices = 4; // 图的顶点数int edges = 5; // 图中的边数KruskalMST graph = new KruskalMST(vertices, edges);// 添加边graph.edgeArray[0] = new Edge(0, 1, 10);graph.edgeArray[1] = new Edge(0, 2, 6);graph.edgeArray[2] = new Edge(0, 3, 5);graph.edgeArray[3] = new Edge(1, 3, 15);graph.edgeArray[4] = new Edge(2, 3, 4);// 执行Kruskal算法graph.kruskalMST();}
}
Kruskal算法说明
- 边结构通过
Edge类来表示，其中每条边有三个属性：源顶点src，目标顶点dest，和权重weight。 - 使用并查集
Subset来处理图中顶点的连通性，通过find()方法查找根节点，union()方法合并集合。 - 通过
Arrays.sort()对边进行排序，确保按照权重的升序选择边。
2. Prim算法
Prim算法也是基于贪心思想的算法，与Kruskal不同的是，Prim算法以顶点为中心，逐步构造最小生成树。它每次从当前的生成树中选择一条最小权重的边，将一个新顶点加入树中。
算法步骤：
- 从任意一个顶点开始，将其加入生成树。
- 找到一个与当前生成树相连的、权重最小的边，并将该边加入生成树。
- 重复上述步骤，直到生成树包含所有顶点。
Prim算法的Java实现
import java.util.*;public class PrimMST {private static final int V = 5; // 图中顶点的数量// 查找key[]中的最小值，并返回对应顶点int minKey(int key[], Boolean mstSet[]) {int min = Integer.MAX_VALUE, minIndex = -1;for (int v = 0; v < V; v++) {if (!mstSet[v] && key[v] < min) {min = key[v];minIndex = v;}}return minIndex;}// 打印最小生成树void printMST(int parent[], int graph[][]) {System.out.println("边 \t 权重");for (int i = 1; i < V; i++) {System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);}}// Prim最小生成树算法void primMST(int graph[][]) {int parent[] = new int[V]; // 用来存储生成树int key[] = new int[V]; // 用来存储每个顶点的最小权重Boolean mstSet[] = new Boolean[V]; // 用来表示是否包含在最小生成树中// 初始化for (int i = 0; i < V; i++) {key[i] = Integer.MAX_VALUE;mstSet[i] = false;}key[0] = 0; // 第一个顶点的权重为0parent[0] = -1; // 第一个顶点是根节点for (int count = 0; count < V - 1; count++) {// 从还没有加入MST的顶点中选择key值最小的顶点int u = minKey(key, mstSet);mstSet[u] = true;// 更新邻接顶点的key值for (int v = 0; v < V; v++) {if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {parent[v] = u;key[v] = graph[u][v];}}}printMST(parent, graph);}public static void main(String[] args) {PrimMST t = new PrimMST();int graph[][] = new int[][]{{0, 2, 0, 6, 0},{2, 0, 3, 8, 5},{0, 3, 0, 0, 7},{6, 8, 0, 0, 9},{0, 5, 7, 9, 0}};// 执行Prim算法t.primMST(graph);}
}
Prim算法说明
graph是邻接矩阵，表示图的顶点之间的连接关系和权重。minKey()方法用于找到未被包含在MST中的顶点中具有最小权重的顶点。primMST()方法实现了Prim算法，通过选取权重最小的边将顶点逐步加入生成树。
Kruskal算法和Prim算法的比较
-
适用场景：
- Kruskal算法在稀疏图（边较少）上表现较好，因为它每次处理边，边的数量较少。
- Prim算法在稠密图（边较多）上表现较好，因为它是基于顶点选择的。
-
时间复杂度：
- Kruskal算法的时间复杂度为 O(ElogE)O(E \log E)O(ElogE)，其中 EEE 是边的数量，排序边是主要的开销。
- Prim算法的时间复杂度为 O(V2)O(V^2)O(V2)（使用简单实现），或者 O(ElogV)O(E \log V)O(ElogV)（使用优先队列优化），其中 VVV 是顶点数量，EEE 是边数量。
这两种算法都可以用于求解最小生成树，具体使用哪种取决于图的结构和规模。