最小生成树：Prim算法（两种步骤）（java)

最小生成树：Prim算法（两种方法）（java)

运行：
C:\aaa>java MST
5 8
0 1 2
1 4 9
4 3 7
3 0 10
0 2 12
2 4 3
1 2 8
2 3 6

a b 2
b c 8
c e 3
c d 6

方法二：时间复杂度O(n^2)

import java.io.BufferedInputStream;import java.util.Scanner;import java.util.Arrays;public class PrimTest{    private int[][] arr;//邻接矩阵    private boolean flag[];  //用来标记节点i是否已加入到MST    private int n; //顶点数    private int sum;//最小权值和    static final int maxInt = Integer.MAX_VALUE;    public PrimTest(int[][] arr,int n){         this.arr=arr;         this.n=n;         flag=new boolean[n];    }    public static void main(String[] args) {        Scanner s = new Scanner(new BufferedInputStream(System.in));                         int n = 7;            int arr[][] =                {{maxInt,28,    maxInt,maxInt,maxInt, 10,    maxInt},                 {28,    maxInt,16,    maxInt,maxInt, maxInt,14     },                 {maxInt,16,    maxInt,12,    maxInt, maxInt,maxInt},                 {maxInt,maxInt,12,    maxInt,22,     maxInt,18    },                 {maxInt,maxInt,maxInt,22,    maxInt, 25,    24    },                 {10,    maxInt,maxInt,maxInt,25,     maxInt,maxInt},                 {maxInt,14,    maxInt,18,    24,     maxInt,maxInt}};          System.out.println(new PrimTest(arr,n).prim());                 }                       public int prim(){            sum = 0;            flag[0] = true; //选取第一个节点            int mst[]=new int[n];//存储最小权值边的起点            Arrays.fill(mst,0);//最小权值边的起点默认为0                         for(int k=1; k<n; k++){    //循环n-1次                int min = maxInt,min_i = 0;                for(int i=0; i<n; i++){//选一条权值最小的。                    if( !flag[i] && arr[0][i] < min){                        min = arr[0][i];                        min_i = i;                    }                }                                flag[min_i] = true; //加入                System.out.print("边"+mst[min_i]+"-"+min_i);                for(int i=0; i<n; i++){ //更新                    if( !flag[i] && arr[0][i] > arr[min_i][i]){//若同一个未加入点与多个已加入点相连接，取权值较小的。                        arr[0][i] = arr[min_i][i];                        mst[i] = min_i;//更新最小权值边的起点                    }                                   }                System.out.println("--"+arr[0][min_i]);                sum += arr[0][min_i];//加上权值            }                                   return sum;                    }}


运行：
边0-5--10
边5-4--25
边4-3--22
边3-2--12
边2-1--16
边1-6--14
99

下载源码：