数据结构—图—最小生成树

悠悠 2022-04-12 04:50 715阅读 0赞

### 什么是最小生成树 ###

一个有 n 个结点的[连通图][Link 1]的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。 \[1\]  最小生成树可以用[kruskal][]（克鲁斯卡尔）算法或[prim][]（普里姆）算法求出。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjIzNDI4_size_16_color_FFFFFF_t_70][]

2、普里姆算法—Prim算法

算法思路：  
首先就是从图中的一个起点a开始，把a加入U集合，然后，寻找从与a有关联的边中，权重最小的那条边并且该边的终点b在顶点集合：（V-U）中，我们也把b加入到集合U中，并且输出边（a，b）的信息，这样我们的集合U就有：\{a,b\}，然后，我们寻找与a关联和b关联的边中，权重最小的那条边并且该边的终点在集合：（V-U）中，我们把c加入到集合U中，并且输出对应的那条边的信息，这样我们的集合U就有：\{a,b,c\}这三个元素了，一次类推，直到所有顶点都加入到了集合U。

下面我们对下面这幅图求其最小生成树：

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

假设我们从顶点v1开始，所以我们可以发现（v1,v3）边的权重最小，所以第一个输出的边就是：v1—v3=1:  
![这里写图片描述][SouthEast 1]

然后，我们要从v1和v3作为起点的边中寻找权重最小的边，首先了（v1,v3）已经访问过了，所以我们从其他边中寻找，发现(v3,v6)这条边最小，所以输出边就是：v3—v6=4  
![这里写图片描述][SouthEast 2]

然后，我们要从v1、v3、v6这三个点相关联的边中寻找一条权重最小的边，我们可以发现边(v6,v4)权重最小，所以输出边就是：v6—v4=2.  
![这里写图片描述][SouthEast 3]

然后，我们就从v1、v3、v6、v4这四个顶点相关联的边中寻找权重最小的边，发现边（v3，v2）的权重最小，所以输出边：v3—–v2=5  
![这里写图片描述][SouthEast 4]

然后，我们就从v1、v3、v6、v4，v2这2五个顶点相关联的边中寻找权重最小的边，发现边（v2，v5）的权重最小，所以输出边：v2—–v5=3  
![这里写图片描述][SouthEast 5]

最后，我们发现六个点都已经加入到集合U了，我们的最小生成树建立完成。

## 时间复杂度 ##

<table> 
 <tbody> 
  <tr> 
   <th>最小边、权的数据结构</th> 
   <th>时间复杂度（总计）</th> 
  </tr> 
  <tr> 
   <td><a href="https://baike.baidu.com/item/%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5" rel="nofollow">邻接矩阵</a>、搜索</td> 
   <td>O(N^2)</td> 
  </tr> 
  <tr> 
   <td><a href="https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E5%A0%86" rel="nofollow">二叉堆</a>（后文伪代码中使用的数据结构）、<a href="https://baike.baidu.com/item/%E9%82%BB%E6%8E%A5%E8%A1%A8" rel="nofollow">邻接表</a></td> 
   <td>O((N + E) log(N)) = O(E log(N))</td> 
  </tr> 
  <tr> 
   <td><a href="https://baike.baidu.com/item/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E5%A0%86" rel="nofollow">斐波那契堆</a>、<a href="https://baike.baidu.com/item/%E9%82%BB%E6%8E%A5%E8%A1%A8" rel="nofollow">邻接表</a></td> 
   <td>O(E + N log(N))</td> 
  </tr> 
 </tbody> 
</table>

通过邻接矩阵图表示的简易实现中，找到所有最小权边共需O（V）的运行时间。使用简单的二叉堆与邻接表来表示的话，普里姆算法的运行时间则可缩减为O(ElogV)，其中E为连通图的边数，V为顶点数。如果使用较为复杂的斐波那契堆，则可将运行时间进一步缩短为O(E+VlogV)，这在连通图足够密集时（当E满足Ω（VlogV）条件时），可较显著地提高运行速度。

### 代码实现： ###

#define MAXN 1000
    #define INF 1<<30
    int closest[MAXN],lowcost[MAXN],m;//m为节点的个数
    int G[MAXN][MAXN];//邻接矩阵
    int prim()
    {
        for(int i=0; i<m; i++)
        {
            lowcost[i]=INF;
        }
        for(int i=0; i<m; i++)
        {
            closest[i]=0;
        }
        closest[0]=-1;//加入第一个点，-1表示该点在集合U中，否则在集合V中
        int num=0,ans=0,e=0;//e为最新加入集合的点
        while(num<m-1)//加入m-1条边
        {
            int micost=INF,miedge=-1;
            for(int i=0; i<m; i++)
                if(closest[i]!=-1)
                {
                    int temp=G[e][i];
                    if(temp<lowcost[i])
                    {
                        lowcost[i]=temp;
                        closest[i]=e;
                    }
                    if(lowcost[i]<micost)
                        micost=lowcost[miedge=i];
                }
            ans+=micost;
            closest[e=miedge]=-1;
            num++;
        }
        return ans;
    }

[应用实例：畅通工程之局部最小花费问题][Link 2]

Kruskal—克鲁斯卡算法

算法思路：  
（1）将图中的所有边都去掉。  
（2）将边按权值从小到大的顺序添加到图中，保证添加的过程中不会形成环  
（3）重复上一步直到连接所有顶点，此时就生成了最小生成树。这是一种贪心策略。

这里同样我们给出一个和Prim算法讲解中同样的例子，模拟克鲁斯卡算法生成最小生成树的详细的过程：

首先完整的图如下图：  
![这里写图片描述][SouthEast 6]

然后，我们需要从这些边中找出权重最小的那条边，可以发现边（v1，v3）这条边的权重是最小的，所以我们输出边：v1—-v3=1  
![这里写图片描述][SouthEast 7]

然后，我们需要在剩余的边中，再次寻找一条权重最小的边，可以发现边（v4，v6）这条边的权重最小，所以输出边：v4—v6=2  
![这里写图片描述][SouthEast 8]

然后，我们再次从剩余边中寻找权重最小的边，发现边（v2，v5）的权重最小，所以可以输出边：v2—v5=3，  
![这里写图片描述][SouthEast 9]

然后，我们使用同样的方式找出了权重最小的边：（v3，v6），所以我们输出边：v3—v6=4  
![这里写图片描述][SouthEast 10]

好了，现在我们还需要找出最后一条边就可以构造出一颗最小生成树，但是这个时候我们有三个选择：（v1,V4），（v2，v3），（v3，v4）,这三条边的权重都是5，首先我们如果选（v1，v4）的话，得到的图如下：  
![这里写图片描述][SouthEast 11]  
我们发现，这肯定是不符合我们算法要求的，因为它出现了一个环，所以我们再使用第二个（v2，v3）试试，得到图形如下：  
![这里写图片描述][SouthEast 12]

我们发现，这个图中没有环出现，而且把所有的顶点都加入到了这颗树上了，所以（v2，v3）就是我们所需要的边，所以最后一个输出的边就是：v2—v3=5

#include<iostream>
    #include<queue>
    using namespace std;
    struct EdgeNode
    {
        int v1;
        int v2;
        int value;
        bool operator<(const EdgeNode &a) const
        {
            return a.value<value;
        }
    };
    int *root;
    priority_queue<EdgeNode> pq;
    int Find(int x)
    {
        int i=x;
        while(i!=root[i])
            i=root[i];
        while(i!=root[x])
        {
            temp=root[x];
            root[x]=i;
            x = temp;
        }
        return i;
    }
    void Union(int a,int b)
    {
        a=Find(a);
        b=Find(b);
        if(a!=b)
            root[a]=b;
    }
    void Kruskal()
    {
        EdgeNode b;
        cout<<"加入最小生成树中的边依次为: "<<endl;
        while(!pq.empty())
        {
            b=pq.top();
            pq.pop();
            if(Find(b.v1)!=Find(b.v2))
            {
                cout<<b.v1<<"----"<<b.v2<<endl;
                Union(b.v1,b.v2);
            }
        }
    }
    void main()
    {
        int n=0;
        int m=0;
        cout<<"请输入图中点的个数: "<<endl;
        cin>>n;
        root=new int [n+1];
        for(int i=1; i<=n; i++)
            root[i]=i;
        cout<<"请输入图中边的条数: "<<endl;
        cin>>m;
        EdgeNode a;
        cout<<"请依次输入每条边的两个顶点及其权重: "<<endl;
        while(m--)
        {
            cin>>a.v1>>a.v2>>a.value;
            pq.push(a);
        }
        Kruskal();
    }

[实例：畅通工程之最低成本建设问题 ][Link 3]

[Link 1]: https://baike.baidu.com/item/%E8%BF%9E%E9%80%9A%E5%9B%BE/6460995
[kruskal]: https://baike.baidu.com/item/kruskal/10242089
[prim]: https://baike.baidu.com/item/prim/10242166
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjIzNDI4_size_16_color_FFFFFF_t_70]: /images/20220412/36e5d1403fd54473a7022e0b6b7f739f.png
[SouthEast]: /images/20220412/8ac28f266e994fb7a42ad5e95fc93e58.png
[SouthEast 1]: /images/20220412/6a1f23d6430b4317b4f8e8f843105ee4.png
[SouthEast 2]: /images/20220412/a44d749ead034505a52b62d15bae9f65.png
[SouthEast 3]: /images/20220412/05637e3985634013a0dc95ebeaddbae2.png
[SouthEast 4]: /images/20220412/2c20606f5b1348d6a467f8a2b3e8c266.png
[SouthEast 5]: /images/20220412/7375a988c8114b9ea49bf38def6bb946.png
[Link 2]: https://blog.csdn.net/qq_42623428/article/details/82911022
[SouthEast 6]: /images/20220412/85e1fefa4b614518a77f0f0c32b6d926.png
[SouthEast 7]: /images/20220412/6844dad5f0de4f678dc8b0c4d380d335.png
[SouthEast 8]: /images/20220412/3d0c9835965c4112b9318b8499c9cfc2.png
[SouthEast 9]: /images/20220412/f8af8dffaf9a432798ffd8d7699b4306.png
[SouthEast 10]: /images/20220412/72a82bc4a0a9488b867089d9ff6775e9.png
[SouthEast 11]: /images/20220412/6f9437a31f1f44678e1aaef352825e3d.png
[SouthEast 12]: /images/20220412/9e11e77ce3704b2d863b4386379a838d.png
[Link 3]: https://blog.csdn.net/qq_42623428/article/details/84192655