文章目录

• 最小生成树
• Prim算法
• • 1.介绍
  • 2.图解步骤
  • 3.算法分析
  • • 算法问题
    • 解决方案
  • 4.代码实现
• Kruskal算法
• • 1.介绍
  • 2.图解
  • 3.算法分析
  • • 算法问题
    • 解决方案
  • 4.代码实现

最小生成树

在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。

例如，对于上图中的连通网可以有多棵权值总和不相同的生成树。

Prim算法

1.介绍

普里姆（Prim）算法，也是求加权连通图的最小生成树的算法。

基本思想
对于图G而言，V是所有顶点的集合；现在，设置两个新的集合U和T，其中U用于存放G的最小生成树中的顶点，T存放G的最小生成树中的边。从所有的 u∈U ，v∈(V-U)（V-U表示除去U的所有顶点）的边中选取权值最小的边（u，v），将顶点v加入U中，将边（u,v）加入集合T中，如此不断重复，直到U=V为止，最小生成树构造完毕，此时集合T中包含了最小生成树中的所有边。

2.图解步骤

以上图G4为例，来对普里姆进行演示(从第一个顶点A开始通过普里姆算法生成最小生成树)。

初始状态：V是所有顶点的集合，即V={A,B,C,D,E,F,G}；U和T都是空

第1步：将顶点A加入到U中。 此时，U={A}。

第2步：将顶点B加入到U中。

上一步操作之后，U={A}, V-U={B,C,D,E,F,G}；因此，边(A,B)的权值最小。将顶点B添加到U中；此时，U={A,B}。

第3步：将顶点F加入到U中。

上一步操作之后，U={A,B}, V-U={C,D,E,F,G}；因此，边(B,F)的权值最小。将顶点F添加到U中；此时，U={A,B,F}。

第4步：将顶点E加入到U中。

上一步操作之后，U={A,B,F}, V-U={C,D,E,G}；因此，边(F,E)的权值最小。将顶点E添加到U中；此时，U={A,B,F,E}。

第5步：将顶点D加入到U中。

上一步操作之后，U={A,B,F,E}, V-U={C,D,G}；因此，边(E,D)的权值最小。将顶点D添加到U中；此时，U={A,B,F,E,D}。
第6步：将顶点C加入到U中。

上一步操作之后，U={A,B,F,E,D}, V-U={C,G}；因此，边(D,C)的权值最小。将顶点C添加到U中；此时，U={A,B,F,E,D,C}。
第7步：将顶点G加入到U中。

上一步操作之后，U={A,B,F,E,D,C}, V-U={G}；因此，边(F,G)的权值最小。将顶点G添加到U中；此时，U=V。

此时，最小生成树构造完成！它包括的顶点依次是：A B F E D C G。

3.算法分析

算法问题

根据前面介绍的普里姆算法的基本思想和做法，我们能够了解到，普里姆算法重点需要解决的以下两个问题：

• 问题一 比较当前路径能到达其他点的所有最小权重，找到最小的边权重。
• 问题二 将这个权重及其到达点加入到路径中，并重新计算当前路径到达其他点的最小权重。

解决方案

问题一：用一个遍历再判断下最小即可。
问题二：比较之前路径能到点的边的所有权重与现在新加入的点到的点的权重，遍历找到两者最小的即可替换（听不懂看图）：

在将A、B、F加入到最小生成树R中，当前整个路径到达点：

到达 C：6
到达 D：到不了
到达 E：2
到达 G：9

经过普利姆算法，下一个新加入点是E：

此时E 的到达点及其权重：

到达 C：5
到达 D：4
到达 E：本身，上一轮就被标记了
到达 G：8

此时进行比较：

到达 C：6>5 : 5
到达 D：到不了>4 :4
到达 E：
到达 G：9>8 :8

所以更新这个到达点的权重数组为现在最小的：5、4、8

4.代码实现

package com.yyl.algorithm.minnumtree;

public class PrimGraph {
    /**
     * 边的类：包括边两端的点与权重值
     */
    public static class Graph {
        int v1;  //v1顶点
        int v2;  //v2顶点
        int weight;  //权值

        public Graph() {
            // TODO Auto-generated constructor stub
        }

        public Graph(int v1, int v2, int weight) {
            super();
            this.v1 = v1;
            this.v2 = v2;
            this.weight = weight;
        }
    }


    /**
     * 创建图
     *
     * @param a 输入图的数组
     * @param m 顶点个数
     */
    public static void CreateGraph2(int a[][], int m) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                // 咱们就是呢，如果说当前的是0（本身）或者是-1（没有连接）就把权重设置为最大
                if (a[i][j] == -1 || a[i][j] == 0) {
                    a[i][j] = Integer.MAX_VALUE;
                }
            }
        }
    }

    // 贪心算法解最小生成树（普里姆算法）
    public static void prim(int a[][], int m) {
        int sum = 0;
        int num = 0;
        int pointnum = m;
        int min = 0, k = 0;
        Boolean visited[] = new Boolean[m];       // 判断哪些点取到了
        Graph minWeight[] = new Graph[m];   // 当前点到其他点的最小权重
        Graph tracing[] = new Graph[m];     // 最小生成树的解,最后一个放最小生成树的权值和

        minWeight[0] = new Graph(1, 1, a[0][0]);
        visited[0] = true;
        // 第一次初始化各个点
        for (int i = 1; i < m; i++) {
            minWeight[i] = new Graph(1, i + 1, a[0][i]);
            visited[i] = false;
        }
        for (int i = 1; i < m; i++) {
            min = Integer.MAX_VALUE;
            for (int j = 0; j < m; j++) {
                if (minWeight[j].weight < min && !visited[j]) {
                    min = minWeight[j].weight;
                    k = j;
                }
            }
            // 当前的K点就是最小权值的点
            visited[k] = true;
            // 设置当前点为下一个路径点，最小路径和加上当前最小权重，点数+1
            tracing[num++] = minWeight[k];
            sum += min;
            pointnum--;

            for (int j = 0; j < m; j++) {
                // 如果当前点没被访问过 并且 当前点到其他点的权重小于上一个点到其他点的权重，就把当前点到那个点的权重替换为小的
                if (!(visited[j]) && a[k][j] < minWeight[j].weight) {
                    minWeight[j] = new Graph(k + 1, j + 1, a[k][j]);
                }
            }
        }
        // 因为m个点 所以路径上是m-1个边 那么最后一个 tracing 就放最终结果了
        tracing[m - 1] = new Graph(Integer.MAX_VALUE, Integer.MAX_VALUE, sum);
        // m-1个边 求m-1次 这个次数最终就是1
        if (pointnum == 1) {
            // 打印路径及结果
            printTrancing(tracing);
        } else{
            System.out.println("不存在最小生成树");
        }
    }

    //遍寻最小生成树的边
    public static void printTrancing(Graph tracing[]) {
        for (int i = 0; i < tracing.length - 1; i++){
            System.out.println((tracing[i].v1 - 1) + "<-->" + (tracing[i].v2 - 1)+" 权重："+tracing[i].weight);
        }
        System.out.println("得到的最小生成树的权值和是：" + tracing[tracing.length - 1].weight);
    }


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int m = 9;  //总共9个顶点
        // 设置权重：自己和自己连的是0，没有边的是-1，其他的都是自己权重值
        int[][] a = {
                {0, 10, -1, -1, -1, 11, -1, -1, -1},
                {10, 0, 18, -1, -1, -1, 16, -1, 12},
                {-1, 18, 0, 22, -1, -1, -1, -1, 8},
                {-1, -1, 22, 0, 20, -1, 24, 16, 21},
                {-1, -1, -1, 20, 0, 26, -1, 7, -1},
                {11, -1, -1, -1, 26, 0, 17, -1, -1},
                {-1, 16, -1, 24, -1, 17, 0, 19, -1},
                {-1, -1, -1, 16, 7, -1, 19, 0, -1},
                {-1, 12, 8, 21, -1, -1, -1, -1, 0}
        };

        CreateGraph2(a, m);
        System.out.println("生成的最小生成树是：");
        prim(a, m);
    }
}

运行结果：

Kruskal算法

1.介绍

克鲁斯卡尔（Kruskal）算法，是用来求加权连通图的最小生成树的算法。

基本思想：按照权值从小到大的顺序，按照排好的顺序依次选择最小的边，总共选择n-1条边，并保证选择的这n-1条边不构成回路。
具体做法：首先构造一个只含n个顶点的森林，然后依照权值从小到大从连通网中选择边加入到森林中，并使得森林不产生回路，直到森林变成一棵树为止。

2.图解

以图G4为例（更详细的可以参考《算法导论》p367），对Kruskal进行演示（假设，用数组R保存最小生成树结果）。

第1步：将边<E,F>加入R中。

边<E,F>的权值最小，因此将它加入到最小生成树结果R中。
第2步：将边<C,D>加入R中。

上一步操作之后，边<C,D>的权值最小，因此将它加入到最小生成树结果R中。
第3步：将边<D,E>加入R中。

上一步操作之后，边<D,E>的权值最小，因此将它加入到最小生成树结果R中。
第4步：将边<B,F>加入R中。

上一步操作之后，边<C,E>的权值最小，但<C,E>会和已有的边构成回路；因此，跳过边<C,E>。同理，跳过边<C,F>。将边<B,F>加入到最小生成树结果R中。
第5步：将边<E,G>加入R中。

上一步操作之后，边<E,G>的权值最小，因此将它加入到最小生成树结果R中。
第6步：将边<A,B>加入R中。

上一步操作之后，边<F,G>的权值最小，但<F,G>会和已有的边构成回路；因此，跳过边<F,G>。同理，跳过边<B,C>。将边<A,B>加入到最小生成树结果R中。

此时，最小生成树构造完成！它包括的边依次是：<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。

3.算法分析

算法问题

根据前面介绍的克鲁斯卡尔算法的基本思想和做法，我们能够了解到，克鲁斯卡尔算法重点需要解决的以下两个问题：
问题一 对图的所有边按照权值大小进行排序。
问题二 将边添加到最小生成树中时，怎么样判断是否形成了回路。

解决方案

问题一：用排序算法排序即可解决。
问题二：记录顶点在“最小生成树”中的终点，顶点的终点是“在最小生成树中与它连通的最大顶点"(关于这一点，后面会通过图片给出说明)。然后每次需要将一条边添加到最小生成树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。 以下图来进行说明：

在将<E,F> <C,D> <D,E>加入到最小生成树R中之后，这几条边的顶点就都有了终点：

(01) C的终点是F。
(02) D的终点是F。
(03) E的终点是F。
(04) F的终点是F。

关于终点，就是将所有顶点按照从小到大的顺序排列好之后；某个顶点的终点就是"与它连通的最大顶点"。 因此，接下来，虽然<C,E>是权值最小的边。但是C和E的终点都是F，即它们的终点相同，因此，将<C,E>加入最小生成树的话，会形成回路。这就是判断回路的方式。

同理接下来的<C,F>也是一样的，他们的终点相同，也会判断出回路。

到<F,B>，B还没有加到树里面，B没有终点，所以直接进。

4.代码实现

我没打啊下面的代码，最近哎，没时间，遗憾，但是也贴下了，凑活看吧

package com.yyl.algorithm.minnumtree;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class KruskalGraph {
    /**
     * 边的类：包括边两端的点与权重值
     */
    public static class Graph {
        int v1;  //v1顶点
        int v2;  //v2顶点
        int weight;  //权值

        public Graph() {
            // TODO Auto-generated constructor stub
        }

        public Graph(int v1, int v2, int weight) {
            super();
            this.v1 = v1;
            this.v2 = v2;
            this.weight = weight;
        }
    }


    //贪心算法解最小生成树（克鲁斯卡尔法）
    public static void kruskal(Graph tempGraph[], int m, int k) {
        int numPoint = m;  // 未加入路径结点数
        int v1;  // 访问点1
        int v2;  // 访问点2
        List<Graph> minST = new ArrayList<Graph>();  //寄存选取的最小生成树的边

        int a[] = new int[m];  // 将根记录下来

        // 将每个点设为一个根
        for (int i = 0; i < m; i++)
            a[i] = i;

        for (int i = 0; i < k && numPoint > 1; i++) {
            v1 = tempGraph[i].v1 - 1;
            v2 = tempGraph[i].v2 - 1;

            //判断两个点是不是属于同一个根元素点
            if (UnitRoot(v1, v2, a)) {
                minST.add(tempGraph[i]);
                numPoint--;
            }
        }

        if (numPoint == 1){
            printTracing(minST);
        }
        else{
            System.out.println("不存在最小生成树");
        }
    }

    // 访问根节点
    public static int FindRoot(int a[], int root) {
        if (root == a[root])
            return root;  //如果访问点就是根则直接返回
        return a[root] = FindRoot(a, a[root]);  //否则递归找到访问节点的根元素
    }

    // 将根元素合并
    public static Boolean UnitRoot(int root1, int root2, int a[]) {
        int temp1 = FindRoot(a, root1);
        int temp2 = FindRoot(a, root2);
        if (temp1 != temp2) {
            a[temp2] = temp1;  //若两个节点根元素不一样，则将标号大的点作为根赋给标号为小的点
            return true;
        } else
            return false;  //若两个节点根元素一样，则说明这两个点再连接就会是一个闭合的图，而不再是树
    }

    // 遍寻最小生成树的边
    public static void printTracing(List<Graph> minST) {
        int sum = 0;
        System.out.println("生成的最小生成树是：");

        for (int i = 0; i < minST.size(); i++) {
            System.out.println((minST.get(i).v1 - 1) + "<-->" + (minST.get(i).v2 - 1));
            sum += minST.get(i).weight;
        }

        System.out.println("得到的最小生成树的权值和是：" + sum);
    }

    // 创建图
    public static Graph[] CreateGraph(int m, int a[][]) {
        int k = 0;
        Graph graph[] = new Graph[m * a.length];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < i; j++) {
                if (a[i][j] > 0) {
                    graph[k] = new Graph(i + 1, j + 1, a[i][j]);
                    k++;
                }
            }

        Graph tempGraph[] = new Graph[k];
        for (int i = 0; i < k; i++){
            tempGraph[i] = graph[i];
        }
        return tempGraph;
    }


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int m = 9;  // 总共9个顶点
        // 设置权重：自己和自己连的是0，没有边的是-1，其他的都是自己权重值
        int[][] a = {
                {0, 10, -1, -1, -1, 11, -1, -1, -1},
                {10, 0, 18, -1, -1, -1, 16, -1, 12},
                {-1, 18, 0, 22, -1, -1, -1, -1, 8},
                {-1, -1, 22, 0, 20, -1, 24, 16, 21},
                {-1, -1, -1, 20, 0, 26, -1, 7, -1},
                {11, -1, -1, -1, 26, 0, 17, -1, -1},
                {-1, 16, -1, 24, -1, 17, 0, 19, -1},
                {-1, -1, -1, 16, 7, -1, 19, 0, -1},
                {-1, 12, 8, 21, -1, -1, -1, -1, 0}
        };

        Graph tempGraph[] = CreateGraph(m, a);

        // 按权值进行升序排序
        Arrays.sort(tempGraph, new Comparator<Graph>() {
            public int compare(Graph o1, Graph o2) {
                return o1.weight - o2.weight;
            }

            ;
        });
        kruskal(tempGraph, m, tempGraph.length);
    }
}

运行结果：