普里姆算法（Prim）-最小生成树

1. 首先转为图，从一个顶点出发，找到相邻的最短路径的顶点，然后再找前俩个节点的所有路径中最短路径的顶点，依次类推

public class PrimAlgorithm {

    public static void main(String[] args) {
        char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int verxs = data.length;
        int[][] weight = {
                {10000, 5, 7, 10000, 10000, 10000, 2},
                {5, 10000, 10000, 9, 10000, 10000, 3},
                {7, 10000, 10000, 10000, 8, 10000, 10000},
                {10000, 9, 10000, 10000, 10000, 4, 10000},
                {10000, 10000, 8, 10000, 10000, 5, 4},
                {10000, 10000, 10000, 4, 5, 10000, 6},
                {2, 3, 10000, 10000, 4, 6, 10000}
        };
        MinTree mt = new MinTree();
        MGraph graph = mt.createGraph(verxs, data, weight);
        mt.show(graph);
        mt.prim(graph, 0);
    }


}

class MinTree {

    public MGraph createGraph(int verxs, char[] data, int[][] weight) {
        MGraph graph = new MGraph(verxs, data, weight);
        return graph;
    }

    public void show(MGraph graph) {
        for (int i = 0; i < graph.weight.length; i++) {
            System.out.println(Arrays.toString(graph.weight[i]));
        }
    }


    public void prim(MGraph graph, int v) {
        int[] visited = new int[graph.verxs];
        visited[v] = 1;
        int minWeight = 1000;

        int minX = 0, minY = 0;
        for (int i = 1; i < graph.verxs; i++) {

            for (int j = 0; j < graph.verxs; j++) {
                for (int k = 0; k < graph.verxs; k++) {
                    if (visited[j] == 1 && visited[k] == 0 && graph.weight[j][k] < minWeight) {
                        minWeight = graph.weight[j][k];
                        minX = j;
                        minY = k;
                    }
                }
            }
            System.out.println("点:" + graph.data[minX] + "====点:" + graph.data[minY] + "---weight:"
                    + graph.weight[minX][minY]);
            visited[minY] = 1;
            minWeight = 10000;
        }
    }
}


class MGraph {

    int verxs;
    char[] data;
    int[][] weight;

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