Java 版 Prim 算法求最小生成树

快来打我* 2022-07-12 15:48 150阅读 0赞

最小生成树： 一个具有n个顶点的加权的无相连通图，用n-1条边连接这n个顶点，并且使得连接之后的所有边的权值之和最小的树。

Prim算法：先以一个结点作为最小生成树的第一个结点，然后以迭代的方式找出与最小生成树中各结点权值最小边，加到最小生成树中。加入之后如果产生回路则跳过这条边，选择下一个结点。当所有结点都加入到最小生成树中之后，就找出最小生成树了。

举个例子：

![这里写图片描述][SouthEast]

根据下图3个步骤找出最小生成树：

![这里写图片描述][SouthEast 1]

在写程序时，需要把连通图转化为邻接矩阵输入。假设A、B、C、D 为 1、2、3、4 ：

![这里写图片描述][SouthEast 2]

代码如下：

package minSpanningTree;
    
    import java.util.Scanner;
    
    public class Prim {
    
        //用来初始化数组的，比结点数大就行
        private static final int MAXN = 100;
        //INF表示不存在边的长度，用一个很大的数表示它
        private static final int INF = 100000001;
    
        public static void main(String[] args) {
    
            Scanner s = new Scanner(System.in);
            System.out.println("请输入结点个数:");
            int n = Integer.parseInt(s.nextLine()); 
            System.out.println("结点个数: " + n);
            //邻接矩阵
            int[][] w = new int[MAXN][MAXN];
            //存放父结点的集合
            int[] f = new int[MAXN];
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                    int t = Integer.parseInt(s.nextLine());
                    w[i][j] = (t == 0) ? INF :t;
                }
            }
            //生成最小生成树
            toPrim(w, f, n);
            for(int i = 2; i <= n; i++) {
                System.out.println(i + "------>" + f[i]);
            }
        }
    
        private static void toPrim(int w[][], int f[], int n) {
            //用于存放结点的权值的集合
            int d[] = new int[INF];
            int k = 0;
            int m;
            //第一个结点与其它结点的权值加入集合中
            for(int j = 1; j <= n; j++) {
                d[j] = (j == 1 ? 0 : w[1][j]);
                //第一个结点没有父结点，初始化为1
                f[j] = 1;
            }
            //从第二个结点开始
            for(int i = 2; i <= n; i++) {
                m = INF;
                //遍历与当前结点相连接的各个结点的权值并找出具有最小权值的结点
                for(int j = 1; j <= n; j++) {
                    if(d[j] <= m && d[j] != 0) {
                        m = d[j];
                        k = j;
                    }   
                }
                //将上面找到的结点加入到集合中
                d[k] = 0;
                //更新父d[]，将k结点与其它结点连接的最小权值放进d[j]中
                for(int j = 1; j <= n; j++) {
                    if(d[j] > w[k][j] && d[j] != 0) {
                        d[j] = w[k][j];
                        f[j] = k;
                    }
                }
            }
        }
    }

输出结果：

![这里写图片描述][SouthEast 3]

2——>1 —-> A –B  
3——>2 —-> B –C  
4——>1 —-> A –D

[SouthEast]: /images/20220709/5e8c950c1a664c9a923b8d1abc009b44.png
[SouthEast 1]: /images/20220709/1ce7e94535e041119297df8b20a2ff09.png
[SouthEast 2]: /images/20220709/120f0ad9fbb249adb5b38342c61b9576.png
[SouthEast 3]: /images/20220709/8196e7d53ae440c2b5319cceab1cdf40.png