贪心算法：最小生成树
假设无向图为：
A-B:1
A-C:3
B-C:1
B-D:4
C-D:1
C-E:5
D-E:6
一、使用Prim算法：
public class Prim {//声明了两个静态常量，用于辅助 Prim 算法的实现private static final int V = 5;//点数private static final int INF = Integer.MAX_VALUE;//若直接使用 0 表示无边，会与边权为 0 的情况冲突。而 Integer.MAX_VALUE 是一个极大的值，在比较边权时不会被误认为有效边权。public static void main(String[] args){int [][] graph = new int[][]{{0, 1, 3, 0, 0},{1, 0, 1, 4, 0},{3, 1, 0, 1, 5},{0, 4, 1, 0, 6},{0, 0, 5, 6, 0}};//用二维数组表示无向图primMST(graph);}private static void primMST(int[][] graph) {int[] parent = new int[V];//记录每个结点的父节点int[] key = new int[V];//记录每个结点当前最小边权boolean[] mstSet = new boolean[V];//标记顶点是否已被加入MSTfor(int i =0;i<V;i++){key[i] = INF;mstSet[i] = false;}//初始化key[0] = 0;parent[0] = -1;//初始化for(int count =0;count<V-1;count++){int u = minKey(key,mstSet);//从未加入 MST 的顶点中选择 key 值最小的顶点 umstSet[u] = true;//将 u 加入 MST
//遍历所有与 u 相邻的顶点 v：
//如果 v 未被加入 MST 且边 (u, v) 的权值小于 v 的当前 key，则更新 v 的 key 和 parent。for(int v=0;v<V;v++){if(graph[u][v] != 0&&mstSet[v]==false&&graph[u][v] < key[v]){parent[v] = u;key[v] = graph[u][v];}}}printMST(parent,graph);}
//打印结果private static void printMST(int[] parent, int[][] graph) {System.out.println("Edge \tWeight");for (int i = 1; i < V; i++) {System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);}}private static int minKey(int[] key, boolean[] mstSet) {int min = INF,minIndex = -1;//初始化for(int v = 0;v<V;v++){if(mstSet[v]==false && key[v]<min){min = key [v];minIndex = v;}}return minIndex;}}
二、使用Kruskal算法：
import java.util.*;public class Kruskal{private static final int V = 5; // Number of vertices in the graphprivate Edge[] edges; // 存储所有边，包含三个成员变量：src（源顶点）、dest（目标顶点）和 weight（边的权重）。private int edgeCount = 0; // 边的数量class Edge implements Comparable<Edge> {int src, dest, weight;public int compareTo(Edge compareEdge) {return this.weight - compareEdge.weight;}}
//用于实现并查集class subset {//用于跟踪每个顶点的父节点和秩int parent, rank;}
//查找顶点 i 的根节点，并实现路径压缩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++;}}public static void main(String[] args) {int[][] graph = new int[][]{{0, 1, 3, 0, 0},{1, 0, 1, 4, 0},{3, 1, 0, 1, 5},{0, 4, 1, 0, 6},{0, 0, 5, 6, 0}};Kruskal kruskal = new Kruskal();kruskal.kruskalMST(graph);}void kruskalMST(int[][] graph) {// 计算边的数量并初始化edges数组int edgeCount = 0;//初始化for (int i = 0; i < V; i++) {for (int j = i + 1; j < V; j++) {if (graph[i][j] != 0) {edgeCount++;}}}edges = new Edge[edgeCount];edgeCount = 0;// 初始化边数组for (int i = 0; i < V; i++) {for (int j = i + 1; j < V; j++) {if (graph[i][j] != 0) {edges[edgeCount] = new Edge();edges[edgeCount].src = i;edges[edgeCount].dest = j;edges[edgeCount].weight = graph[i][j];edgeCount++;}}}// 步骤1: 按权重升序排列边Arrays.sort(edges);// 步骤2: 初始化子集subset[] subsets = new subset[V];for (int i = 0; i < V; i++) {subsets[i] = new subset();subsets[i].parent = i;subsets[i].rank = 0;}// 步骤3: 用于存储MST的边Edge[] result = new Edge[V - 1];int e = 0; // 结果数组的索引int i = 0; // 排序后边的索引// 步骤4: 遍历每条边并添加到MST中(如果不形成环)while (e < V - 1 && i < edges.length) {Edge next_edge = edges[i++];int x = find(subsets, next_edge.src);int y = find(subsets, next_edge.dest);if (x != y) {result[e++] = next_edge;Union(subsets, x, y);}}// 输出结果System.out.println("Following are the edges in the constructed MST");for (i = 0; i < e; i++) {System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);}}
}