最小生成树

1.普利姆(Prim)算法

以某顶点为起点，逐步找各顶点上最小权值的边来构成最小生成树。
1.初始化选择一个顶点作为开始顶点
2.将这个顶点与各顶点相连的边的权值放入最小边权值数组
3.在最小边权值数组中找到最小的边，取到另一顶点
4.比较另一顶点到各边的权值与第一顶点到各边的权值大小，若小，则最小边权值数组元素替代

  public static void prim(int[][] arr) {

        int length = arr.length;

        //保存相关顶点下表
        int[] adjvex = new int[length];

        //保存相关顶点边的权值
        int[] lowcost = new int[length];

        //初始化第一个权值为0，即v0加入生成树,lowcost的值为0，在这里就是此下标的顶点已经加入生成树
        lowcost[0] = 0;

        //初始化第一个顶点下表为0
        adjvex[0] = 0;

        for (int i = 1; i < length; i++) {
            //将v0顶点与之有边的权值存入数组
            lowcost[i] = arr[0][i];

            //初始化都为v0的下标
            adjvex[i] = 0;

        }

        int min, j, k;
        for (int i = 1; i < length; i++) {
            //初始化最小权值为不可能的大数字
            min = MAX_VALUE;

            j = 1;
            k = 0;

            while (j < length) {
                if (lowcost[j] != 0 && lowcost[j] < min) {
                    //当前权值为最小值，让当前最小值的下标存入k
                    min = lowcost[j];
                    k = j;
                }
                j++;
            }

            System.out.println("找到顶点(" + adjvex[k] + ", " + k + ")");
            //将当前顶点的权值设置为0，表示已完成任务
            lowcost[k] = 0;

            for (j = 1; j < length; j++) {
                //若下标为k顶点各边权值小于此前这些顶点未被加入生成树权值
                if (lowcost[j] != 0 && arr[k][j] > 0 && arr[k][j] < lowcost[j]) {

                    //最小权值存入lowcost
                    lowcost[j] = arr[k][j];

                    //将下标为k的顶点存入
                    adjvex[j] = k;
                }
            }

        }

    }

2.克鲁斯卡尔(Kruskal)算法

以边为目标，找最小权值的边来构建生成树。

    private static class Edge {

        private int begin;

        private int end;

        private int weight;

        public Edge(int begin, int end, int weight) {
            this.begin = begin;
            this.end = end;
            this.weight = weight;
        }
    }

    public static void kruskal(int[][] arr) {

        Edge[] edges = convert(arr);
        int length = edges.length;

        //用来判断边与边是否形成回路,下标与值连接
        int[] parent = new int[arr.length];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = 0;
        }

        int n, m;
        for (int i = 0; i < length; i++) {
            n = find(parent, edges[i].begin);
            m = find(parent, edges[i].end);

            //n.m不等，说明此边没有与现有生成树形成环路
            if (n != m) {
                parent[n] = m;
                System.out.println("begin:" + edges[i].begin + "end:" + edges[i].end + "weight:" + edges[i].weight);
            }
        }

    }

    /**
     * 查找连线顶点的尾部下标
     *
     * @param parent
     * @param f
     * @return
     */
    private static int find(int[] parent, int f) {
        while (parent[f] > 0) {
            f = parent[f];
        }

        return f;
    }

    /**
     * 邻接矩阵转换为边集数组
     *
     * @param arr
     * @return
     */
    private static Edge[] convert(int[][] arr) {
        Edge[] edges = new Edge[arr.length * 2];
        int k = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i ; j < arr.length; j++) {

                if (arr[i][j] != 0 && arr[i][j] != MAX_VALUE) {
                    Edge edge = new Edge(i, j, arr[i][j]);
                    edges[k] = edge;
                    k++;
                }
            }
        }
        Edge[] newEdges = new Edge[k];

        System.arraycopy(edges,0,newEdges,0,k);

        //根据权值进行排序，从小到大
        for (int m = 0; m < k - 1; m++) {
            for (int i = m + 1; i < k; i++) {

                //判断，如果前边的大于后边的，则交换
                if (newEdges[m].weight > newEdges[i].weight) {
                    Edge t = newEdges[m];
                    newEdges[m] = newEdges[i];
                    newEdges[i] = t;
                }

            }

        }

        return newEdges;

    }