数据结构——图（二）

数据结构与算法——图（二）

前几天学习完图的遍历后，马上就开始了图的最小生成树，结果就心态爆炸，完全理解不了这两个算法——prim算法与Kruskal算法。接下来将对这两个算法进行解密，并且提供简单易于理解的解释。

Prim算法

首先熟悉一下接下来需要求最小生成树的图：

如果还不了解图的话，还是建议先理解数据结构与算法——图（一）的内容。接下来的内容会让大脑感到非常舒适，请坚持住！

作为一名程序员我们还是先看看代码吧，只需要关注prim方法即可。

public class GraphPrim<T> {

    public static void main(String[] args) {
        Integer[] vertex = new Integer[] { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
        int[][] matrix = new int[][] {
                { 0, 10, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT },
                { 10, 0, 18, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, MAX_WEIGHT, 12 },
                { MAX_WEIGHT, 18, 0, 22, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 8 },
                { MAX_WEIGHT, MAX_WEIGHT, 22, 0, 20, MAX_WEIGHT, 24, 16, 21 },
                { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 20, 0, 26, MAX_WEIGHT, 7, MAX_WEIGHT },
                { 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 26, 0, 17, MAX_WEIGHT, MAX_WEIGHT },
                { MAX_WEIGHT, 16, MAX_WEIGHT, 24, MAX_WEIGHT, 17, 0, 19, MAX_WEIGHT },
                { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, 7, MAX_WEIGHT, 19, 0, MAX_WEIGHT },
                { MAX_WEIGHT, 12, 8, 21, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 0 },
        };
        GraphPrim<Integer> graph = new GraphPrim<>(vertex, matrix);
        graph.prim();
    }

    public static final int MAX_WEIGHT = 100000;
    private T[] vertex;
    private int[][] matrix;

    public GraphPrim(T[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
    }

    public void prim() {
        int size = this.vertex.length;
        int[] cost = new int[size];
        int[] index = new int[size];
        int min, minIndex, sum = 0;
        for (int i = 0; i < size; i++) {
            cost[i] = this.matrix[0][i];
        }
        for (int i = 1; i < size; i++) {
            min = MAX_WEIGHT;
            minIndex = 0;
            for (int j = 1; j < size; j++) {
                if (cost[j] > 0 && cost[j] < min) {
                    min = cost[j];
                    minIndex = j;
                }
            }
            System.out.println("顶点: " + this.vertex[minIndex] + " 权值: " + min);
            sum += min;
            cost[minIndex] = 0;
            index[minIndex] = min;
            for (int j = 1; j < size; j++) {
                if (cost[j] != 0 && this.matrix[minIndex][j] < cost[j]) {
                    cost[j] = this.matrix[minIndex][j];
                }
            }
        }
        System.out.println(sum + "  最小生成树数组: " + Arrays.toString(index));
    }
}

根据上图，这样的解出来的结果是( 99 最小生成树权值总和数组: [0, 10, 8, 16, 7, 11, 16, 19, 12] )。为什么会是这样的结果呢？我们将这个过程当做修路来思考，每条边的权值就是修路的花费。

• 从顶点0开始，当我们在顶点0时，我们只能看到顶点1与顶点5的距离，那么我们会选择以修顶点0到顶点1的路。
• 当修到顶点1时，我们能看到顶点2、顶点8、顶点6与顶点5，那么这时候顶点5的花费是最小的，我们就修了顶点0到顶点5的路。
• 这时候又多了几个选择，我们以箭头表示(v1->v2, v1->v8, v1->v6, v5->v6, v5->v4)，再根据之前的做法，选择花费最小的路，依次循环下去，直到每个地方都去过为止。

这就是prim算法的思路，图解如下：

Kruskal算法

实际上Kruskal算法也差不多，只不过它更简单一些，思路非常简单，那就是根据邻接表按权值排序从小到大找非回环路线。下面用一张图来表示它的执行过程：

这里对上图进行解释一下，图上邻接表中表示的1-15是循环的轮次，图中的箭头为对应轮次不造成回环响应的轮次。

• 第一次从邻接表的第一个开始，即顶点4到顶点7然后发现没有回环，进行将其走势存到parent数组中，进行下一轮循环。
• 第二次从邻接表的第二个开始，即顶点2到顶点8然后发现没有回环，继续下去，并且走到第七轮都没有发现回环。
• 第八轮从邻接表的第八个开始时，发现从顶点5到顶点6的话会出现回环，因此不进行任何操作，剩下的节点除了第十轮外，都因为产生了回环，所以最终结果就是sum为99。

其最终的parent数组的情况为{1,5,8,7,7,8,7,0,6,0,0,0,0,0,0}。下面附上Kruskal算法的代码：

package graph;

import com.sun.javafx.geom.Edge;

import java.util.Arrays;

/**
 * 克鲁斯卡尔算法
 */
public class GraphKruskal<T> {

    public static void main(String[] args) {
        Integer[] vertex = new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
        Edge[] table = new Edge[15];
        table[0] = new Edge(4, 7, 7);
        table[1] = new Edge(2, 8, 8);
        table[2] = new Edge(0, 1, 10);
        table[3] = new Edge(0, 5, 11);
        table[4] = new Edge(1, 8, 12);
        table[5] = new Edge(3, 7, 16);
        table[6] = new Edge(1, 6, 16);
        table[7] = new Edge(5, 6, 17);
        table[8] = new Edge(1, 2, 18);
        table[9] = new Edge(6, 7, 19);
        table[10] = new Edge(3, 4, 20);
        table[11] = new Edge(3, 8, 21);
        table[12] = new Edge(2, 3, 22);
        table[13] = new Edge(3, 6, 24);
        table[14] = new Edge(4, 5, 26);
        GraphKruskal<Integer> graphs = new GraphKruskal<>(vertex, table);
        graphs.kruskal();
    }

    private T[] vertex;
    private Edge[] table;

    public GraphKruskal(T[] vertex, Edge[] table) {
        this.vertex = vertex;
        this.table = table;
    }

    public void kruskal() {
        int begin, end, sum = 0;
        int[] parent = new int[table.length];
        for (int i = 0; i < table.length; i++) {
            parent[i] = 0;
        }
        for (int i = 0; i < table.length; i++) {
            begin = find(parent, table[i].getBeginIndex());
            end = find(parent, table[i].getEndIndex());
            if (begin != end) {
                parent[begin] = end;
                System.out.println(begin + " -> " + end);
                sum += table[i].getWeight();
            }
        }
        System.out.println("sum = " + sum);
    }

    private int find(int[] parent, int index) {
        while (parent[index] > 0) {
            index = parent[index];
        }
        return index;
    }

    private static class Edge {
        private int beginIndex;
        private int endIndex;
        private int weight;

        public Edge(int beginIndex, int endIndex, int weight) {
            this.beginIndex = beginIndex;
            this.endIndex = endIndex;
            this.weight = weight;
        }

        public int getBeginIndex() {
            return beginIndex;
        }

        public void setBeginIndex(int beginIndex) {
            this.beginIndex = beginIndex;
        }

        public int getEndIndex() {
            return endIndex;
        }

        public void setEndIndex(int endIndex) {
            this.endIndex = endIndex;
        }

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }
    }

}

现在算是初步理解了Prim算法和Kruskal算法的基本原理了，文中有表述不到位或者表述不当的地方，可以联系我，大家一起共同学习共同进步！