图的最小生成树算法

清疚 2022-09-28 13:03 173阅读 0赞

在上一篇文章中，我们看了一下图的遍历算法，主要是对图的深度优先遍历和图的广度优先遍历算法思想的介绍。接下来让我们来看一下图的最小声成树算法。

首先，我们要知道，图的最小生成树是针对于有权图而言的，笔者的上一篇文章只介绍了无权图，其实有权图和无权图唯一的区别就是有权图的边是有权值的，不同的边权值可以不同，对于无权图我们可以把它看成所有边的权值都相等的有权图。好了，下面我们来看一个有权图：

![图片来源：百度百科][SouthEast]

这是百度百科上的一张有权图的图片，和无权图相比多了边的权值。Ok，那么最小生成树算法是什么呢？其实就是我们从给定的无向图中构造出一个无向且无回路子图（图的顶点不能减少），使得图的任意两个顶点都能通过若干条边直接或者间接连同，当构造的子图的边的权值之和最小的时候，这个子图就是这个图的最小生成树。

求最小生成树的算法主要有两种：克鲁斯卡尔（Kruskal）算法和普里姆（Prim）算法。下面一一介绍这两种算法：

Kruskal 算法的思想，简单来说，就是**如果一个图有 n 个顶点，选出总权值最小并且不会构成回路的 n-1 条边使得图中的任意两个顶点都能通过这 n-1 条边中的若干条边连通。**  
这里可能有些小伙伴要问了，为什么选择 n-1 条边就能使得图的任意两个顶点连通？因为在图中的两个顶点之间**如果没有回路**的话最多相隔 n-1 条边，不信的话你可以画几个图看看（注意这里说的是没有回路的图）。

对于 Kruskal 算法的实现，既然要选择选择 n-1 条边并且边的总权值最小，那么我们可以先对这个图的所有边按权值进行从小到大排序，然后依次选择边。在 Kruskal 算法中一个比较麻烦的就是如何判断当前选择的边会不会和已经选择的边产生回路，这里我们可以运用查并集的思想（对查并集不了解的小伙伴可以看一下这篇文章[http://blog.csdn.net/hacker\_zhidian/article/details/60965556][http_blog.csdn.net_hacker_zhidian_article_details_60965556]）。  
我们我们将已经选择了的边的顶点看做一个集合（它们有共同的祖先），对于没有加入生成树的顶点将它们每个顶点单独看成一个集合。那么我们选择边的时候只需要判断边的两个顶点是不是在同一个集合中，如果不在同一个集合中，那么这条边和已经加入生成树的边就不会产生回路，就可以选择这条边，否则的话就不能加入生成树中。重复这个过程，直到选择了 n-1 条边。  
以上面那个无向图为例，我们来模拟一下最小生成树的构造过程：

![这里写图片描述][SouthEast 1]

这是笔者在纸上模拟的过程，到最后，生成的最小生成树的权值之和为 15 。

下面我们来看一下 Prim 算法的核心思想：  
我们换个角度思考一下：既然最后我们需要的最小生成树一定要有 n 个顶点，那么我们直接向这个最小生成树加入图的顶点就行了。**每次向生成树中加入距生成树的距离最小并且还未被加入生成树的顶点，同时通过这个加入的点对其他还未加入生成树的点进行松弛，缩小其他顶点到生成树的距离，重复这个过程，直到 n 个顶点都加入了生成树中。**

Prim算法不需要用到查并集的思想，它使用的是 Dijkstra 单源最短路径的思想，只不过我们这里把源节点换成了生成树，如果你熟悉 Dijkstra 算法，那么我觉得 Prim 算法对你一点难度都没有，因为它们都是同一个思想，不熟悉 Dijkstra 算法的小伙伴可以参考一下这篇文章：[http://blog.csdn.net/hacker\_zhidian/article/details/54915152][http_blog.csdn.net_hacker_zhidian_article_details_54915152]

下面给出这两种算法的源代码：  
Kruskal算法：

#include <iostream>
    #include <algorithm>
    using namespace std;
    const int N = 5010;
    int f[N];
    
    struct node { // 储存边的信息的结构体 
        int x;
        int y;
        int w;
    };
    node e[N];
    
    bool compare(node e1, node e2) { // 排序比较方法 
        return e1.w < e2.w;
    }
    
    // 找到该顶点所在的集合的祖先方法 
    int getF(int v) { 
        if(v == f[v]) {
            return v;
        }
        return f[v] = getF(f[v]);
    }
    
    /*
     * 检测两个顶点是否已经在同一个集合中，
     * 如果是，那么合并这两个顶点 
     */
    int merge(int v, int u) {
        int t1 = getF(v);
        int t2 = getF(u);
        /*
         * 如果两个顶点的“祖先”不相同，
         * 那么证明这条边和最小生成树中已有的边不会构成回路， 
         * 可以加入最小生成树中 
         */
        if(t1 != t2) {
            f[t2] = t1;
            return 1;
        }
        return 0;
    }
    
    int main() {
        int sum = 0, count = 0;
        int m, n;
        cin >> m >> n; // 输入点和边数 
        int x, y, w;
        for(int i = 0; i < n; i++) { // 输入每条边的信息 
            cin >> x >> y >> w;
            e[i].x = x;
            e[i].y = y;
            e[i].w = w;
        }
    
        sort(e, e+n, compare); // 通过边的权值来将图的所有边进行从小到大排序 
    
        // 查并集数组初始化，每一个顶点都是自己的祖先 
        for(int i = 0; i < m; i++) {  
            f[i] = i;
        }
    
        for(int i = 0; i < n; i++) { // kruskal 算法核心代码，对所有的边进行筛选 
            // 合并两个顶点，判断这条边是否能够选进最小生成树中 
            if(merge(e[i].x, e[i].y)) {  
                count++;
                sum += e[i].w;
            }
            if(count == n-1) {
                break;
            }
        }
    
        cout << sum << endl;
    
        return 0;
    }

运行结果：

![这里写图片描述][SouthEast 2]

和我们手动模拟的没有差别。

下面是Prim算法：

#include <iostream>
    using namespace std;
    const int inf = 999999999;
    const int N = 510;
    int dis[N]; // 每个顶点到最小生成树的距离 
    int book[N]; // 标记顶点是否已经加入生成树中 
    int e[N][N]; // 储存图信息的邻接矩阵 
    
    
    int main() {
        int n, m, count = 0, sum = 0;
        cin >> n >> m; // 输入图的点和边
    
        for(int i = 0; i < n; i++) { // 初始化图的邻接矩阵 
            for(int j = 0; j < n; j++) {
                if(i == j) {
                    e[i][j] = 0;
                } else 
                {
                    e[i][j] = e[j][i] = inf;
                }
            }
        }
    
        int x, y, w;
        for(int i = 0; i < m; i++) { // 读入图的边的信息 
            cin >> x >> y >> w;
            e[--x][--y] = e[y][x] = w;
        }
    
        for(int i = 0; i < n; i++) { // 初始化 dis 数组,刚开始只有 0 号一个顶点 
            dis[i] = e[0][i];
        } 
    
        book[0] = 1; // 1 号顶点已经加入 
        count++;
    
        int min = inf;
        int index = 0;
        while(count < n) { // 当加入的顶点小于 n 个时，执行循环 
            min = inf;
            // 循环找出未被加入最小生成树的并且距离最小生成树最小的顶点 
            for(int i = 0; i < n; i++) { 
                if(book[i] == 0 && dis[i] < min) {
                    min = dis[i];
                    index = i;
                }
            }
            book[index] = 1; // 加入这个顶点进入最小生成树中 
            count++; 
            /*
             * 更新最小生成树的总权值：最小生成树的总权值等于最小生成树原来的权值 
             * 加上刚刚加入最小生成树的顶点到最小生成树的距离 
             */
            sum += dis[index]; 
    
            /*
             * 枚举各个顶点，通过第 index 顶点更新各个还没有加入最小生成树中的顶点
             * 到最小生成树的距离 
             */
            for(int i = 0; i < n; i++) { 
                if(book[i] == 0 && dis[i] > e[index][i]) {
                    dis[i] = e[index][i];
                }
            } 
        }
    
        cout << sum << endl;
    
        return 0;
    }

结果：

![这里写图片描述][SouthEast 3]

两个算法得出的结果一样！

Kruskal 算法和 Prim 算法的思想区别：Kruskal 算法从边下手，每次选取的是符合条件的边，而 Prim 算法是从点下手，每次选择的是符合条件的顶点。  
Kruskal算法的时间复杂度由排序算法决定，若采用快排则时间复杂度为O(n\*log n)。  
在这里给的Prim算法的代码时间复杂度为 O(n\*n) ，Prim 算法的耗费时间主要在选距离生成树最近的点和利用选择的点进行松弛的过程，这两个可以用堆和通过邻接表来优化，使得事件复杂度降为O(n\*log n)。

如果博客中有什么不正确的地方，还请多多指点。如果觉得我写的不错，请点个赞支持我吧。

谢谢观看。。。

[SouthEast]: /images/20220708/3cc38a7befb549afbc5c331299ce36de.png
[http_blog.csdn.net_hacker_zhidian_article_details_60965556]: http://blog.csdn.net/hacker_zhidian/article/details/60965556
[SouthEast 1]: /images/20220708/b14e447b219b4643b9834baac83acee6.png
[http_blog.csdn.net_hacker_zhidian_article_details_54915152]: http://blog.csdn.net/hacker_zhidian/article/details/54915152
[SouthEast 2]: /images/20220708/51d9a405f5d6405094be3ed735d601b1.png
[SouthEast 3]: /images/20220708/dda9e4916f384e39bb0ba024a3496a86.png