最小生成树之普里姆算法

package com.ex.prim;

//无向图中找最短路径：普利姆算法
public class Prim {
    static final int N=10000;
    public static void main(String[] args) {
        //节点数组
        char[] node=new char[]{‘A‘,‘B‘,‘C‘,‘D‘,‘E‘,‘F‘,‘G‘};
        //权值数组
        int [][]weight=new int[][]{
                {N,5,7,N,N,N,2},
                {5,N,N,9,N,N,3},
                {7,N,N,N,8,N,N},
                {N,9,N,N,N,4,N},
                {N,N,8,N,N,5,4},
                {N,N,N,4,5,N,6},
                {2,3,N,N,4,6,N},};
        //获得最小生成树
        MGraph graph = new MGraph(node.length,node,weight);
        int sum = graph.prim(3);
        System.out.println("路径总长度："+sum);
    }
}

//无向图
class MGraph{
    //节点个数
    private int count;
    //结点
    private char[] node;
    //边的权值
    private int[][] weight;
    //不可达标记
    static final int N=10000;

    public MGraph(int count, char[] node, int[][] weight) {
        this.count = count;
        this.node = node;
        this.weight = weight;
    }

    /**
     *
     * @param n 从哪个结点开始，n记录该节点在node数组的下标
     * @return
     */
    public int prim(int n){
        //记录访问过的结点
        int[] visited=new int[count];
        //记录路径长度
        int sum=0;
        //从当前结点出发，找到N-1条边将所有结点纳入集合
        visited[n]=1;
        for (int k = 1; k ) {
            //找到和已访问过的结点距离最近的那条边，将新节点纳入集合，并记录其权值
            int minWeight=N;
            int h1=-1;
            int h2=-1;
            for (int i = 0; i ) {
                for (int j = 0; j ) {
                    if (visited[i]==1 && visited[j]==0 && weight[i][j]minWeight){
                        minWeight=weight[i][j];
                        h1=i;
                        h2=j;
                    }
                }
            }
            //将找到的新顶店纳入集合
            visited[h2]=1;
            sum+=minWeight;
            System.out.println(node[h1]+"—>"+node[h2]+"："+minWeight);
        }
        //算法完成
        return sum;
    }
}