Kruscal算法实现最小生成树

主方法

1 import java.util.Arrays; 2 import java.util.Comparator; 3 import java.util.Scanner; 4  5 public class Solution4 { 6     static class Edge{ 7         int u, v; 8         int cost; 9     };10     public static Edge[] edges = new Edge[10010];   // 存储所有的边的数据11     public static int[] root = new int[110];      // 存储每个结点所在集合12     public static int e, v;     // 分别表示边数和顶点数13 14     public static void main(String[] args) {15         Scanner in = new Scanner(System.in);16         while((e = in.nextInt()) != 0){17             // 初始化每个顶点所在的集合为自己单独所处的集合18             for(int i = 0; i < 110; i++){19                 root[i] = i;20             }21             // 读入所有边的数据22             v = in.nextInt();23             int a, b;24             for(int i = 0; i < e; i++){25                 edges[i] = new Edge();26                 edges[i].u = in.nextInt();27                 edges[i].v = in.nextInt();28                 edges[i].cost = in.nextInt();29             }30 31             // 进行 Kruscal 算法构建最小生成树32             int price = Krusal();33             if(price == -1)34                 System.out.println("?");35             else36                 System.out.println(price);37         }38 39     }40 }

Krusal()函数

1 // Kruscal 算法生成最小生成树 2 public static int Krusal(){ 3     // 对所有边进行排序 4     Arrays.sort(edges, 0, e, new Comparator
     
      (){ 5         public int compare(Edge e1, Edge e2){ 6             return e1.cost - e2.cost; 7         } 8     }); 9     int cost = 0;   // 总花费10     int edgeCount = 0;  // 当前已归纳的边数11     // 遍历所有的边，统计当前生成树中边的数量12     for(int i = 0; i < e; i++){13         // 判断 边的链各个顶点是否属于同一个集合14         int uRoot = findRoot(edges[i].u);15         int vRoot = findRoot(edges[i].v);16         // 如果不输于则合并17         if(uRoot != vRoot){18             root[vRoot] = uRoot;19             cost += edges[i].cost;20             edgeCount++;21             if(edgeCount == v - 1)22                 return cost;23         }24         // 如果边的数量等于顶点数减一，那么可以退出循环25     }26     return -1;27 28 }
     

这里主要注意的并查集的findRoot()方法，非常巧妙，内部使用了一个递归来压缩路径

1 　　private static int findRoot(int u) {2         if(root[u] == u)3             return u;4         int uRoot = findRoot(root[root[u]]);    // 路径压缩5         root[u] = uRoot;6         return uRoot;7     }

prim()算法实现最小生生成树

1 import java.util.Arrays; 2 import java.util.Scanner; 3  4 public class PrimTest { 5     // 构建最小生成树 6     public static int[][] G = new int[110][110];    // 村庄的图 7     public static boolean[] vis = new boolean[110]; // 判断某个村庄是否已经被访问过 8     public static int[] dis = new int[110];     // 存放每个村庄到当前生成树集合的距离 9     public static int e;10     public static final int INF = 1 << 30;11     public static int v;12 13     public static void main(String[] args) {14         // 读入数据15         Scanner in = new Scanner(System.in);16 17         e = in.nextInt();18         v = in.nextInt();19         for (int i = 0; i < v; i++) {20             Arrays.fill(G[i], INF);21         }22         Arrays.fill(vis, false);23         int a, b;24         // 对这个数据进行prim最小生成树算法25         for (int i = 0; i < e; i++) {26             a = in.nextInt();27             b = in.nextInt();28             G[a - 1][b - 1] = in.nextInt();29             G[b - 1][a - 1] = G[a - 1][b - 1];30         }31 32         // 如果仍有点的距离为 -1,说明不可达，输出？33         int price = prim(0);34         if (price == -1)35             System.out.println("?");36         else37             System.out.println(price);38     }39 }

prim()函数

1 private static int prim(int u) { 2     int price = 0; 3     // 初始化距离数组 4     Arrays.fill(dis, INF); 5     dis[u] = 0; 6     // 对每个村庄进行循环判断，每次选出其中一个点 7     for (int i = 0; i < v; i++) { 8         int min = INF, vil = -1; 9         for (int j = 0; j < v; j++) {10             if (vis[j] == false && dis[j] < min) {11                 min = dis[j];12                 vil = j;13             }14         }15         if (min == INF) {16             return -1;      // 说明不可达17         }18         // 标记为已访问19         vis[vil] = true;20         price += dis[vil];21         // 更新剩下的dis[]值,更新这个村庄周边到当前生成树的最短距离22         for (int j = 0; j < v; j++) {23             if (vis[j] == false && G[vil][j] != INF && dis[j] > G[vil][j]) {24                 dis[j] = G[vil][j];25             }26         }27     }28     return price;29 }