数据结构值图的最小生成树

迷南。 2022-05-30 02:56 183阅读 0赞

**最小生成树（最小连通网）**

假设在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。

在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。n个城市之间，最多可能设置n（n-1）/2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢？

可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市间的线路，赋予边的权值表示相应的代价。如下图所示：

![70][]

对于n个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。如下面这些图所示（红线部分）：

![70 1][] ![70 2][] ![70 3][]

现在，我们要选择这样一颗生成树，也就是使总的耗费最少。这个问题就是构造连通网的最小代价生成树的问题。一棵生成树的的代价就是树上各边的代价之和。

构造最小生成树可以有多种算法。其中多数算法利用了最小生成树的下列一种简称MST的性质：假设N=(V,\{E\})是一个连通网，U是顶点集V的一个非空子集。若（u,v）是一条具有最小权值的边，其中u∈U，v∈V-U，则必存在一颗包含边（u,v）的最小生成树。

普利姆（Prim）算法和克鲁斯卡尔（Kruskal）算法是两个利用MST性质构造最小生成树的算法。

首先介绍普利姆算法。

基本思想：

1. 从图 N = \{ V, E \}中选择某一顶点 u0进行标记，之后选择与它关联的具有最小权值的边(u(u0, v)，并将顶点 v 进行标记；

2.反复在一个顶点被标记，而另一个顶点未被标记的各条边中选择权值最小的边(u, v),并将未标记的顶点进行标记；

3.如此继续下去，直到图中的所有顶点都被标记为止。

算法步骤：

1.从某一顶点 u0 出发, 使得U=\{u0\}, TE=\{\}；

2.每次选择一条边，这条边是所有(u, v)中权值最小的边，且u∈U, v∈V-U。修改U和TE：

TE = TETE + \{ (u,v) \}

U = U + \{ v \}；

3.当U≠V时，转2；否则，结束。

下面我们假设以二维数组表示网的连接矩阵，且令两个顶点之间不存在的边的权值为机内允许的最大值来实现普利姆算法：

根据算法思想我们知道实现算法之前需要附设几个辅助数组，如下：

#define VNUM 9           // 顶点数
    #define MV 65536         // 最大数值
    
    int P[VNUM];             // 辅助数组
    int Cost[VNUM];          // 存放耗费成本，权值
    int Mark[VNUM];          // 标记数组

当然，前提是我们得有一个图，手动生成如下：

// 邻接矩阵定义图  MV表示顶点间没有变，不邻接
    int Matrix[VNUM][VNUM] =
    {
        {0, 10, MV, MV, MV, 11, MV, MV, MV},
        {10, 0, 18, MV, MV, MV, 16, MV, 12},
        {MV, 18, 0, 22, MV, MV, MV, MV, 8},
        {MV, MV, 22, 0, 20, MV, MV, 16, 21},
        {MV, MV, MV, 20, 0, 26, MV, 7, MV},
        {11, MV, MV, MV, 26, 0, 17, MV, MV},
        {MV, 16, MV, MV, MV, 17, 0, 19, MV},
        {MV, MV, MV, 16, 7, MV, 19, 0, MV},
        {MV, 12, 8, 21, MV, MV, MV, MV, 0},
    };

普利姆算法实现代码如下：

// 普利姆算法
    void Prim(int sv) // O(n*n)
    {
        int i = 0;
        int j = 0;
        // 参数合法性检查
        if( (0 <= sv) && (sv < VNUM) )
        {
        	// 初始化
            for(i=0; i<VNUM; i++)
            {
                Cost[i] = Matrix[sv][i];         // 初始化当前顶点与其他顶点的权值  
                P[i] = sv;            
                Mark[i] = 0;                     // 全未标记
            }
            // 标记初始顶点sv
            Mark[sv] = 1;
            // 遍历图
            for(i=0; i<VNUM; i++)
            {
                int min = MV;
                int index = -1;
                // 遍历所有未标记的顶点
                for(j=0; j<VNUM; j++)
                {
                	  // 选择与当前标记顶点关联的具有最小权值的未标记的顶点
                    if( !Mark[j] && (Cost[j] < min) )
                    {
                        min = Cost[j];       // 最小权值
                        index = j;           // 与当前标记顶点关联的具有最小权值的边的顶点
                    }
                }
                // 将找到的顶点标记，打印边及权值
                if( index > -1 )
                {
                    Mark[index] = 1;         // 标记顶点
                    
                    printf("(%d, %d, %d)\n", P[index], index, Cost[index]);
                }
                // 遍历所有其他未标记的顶点
                for(j=0; j<VNUM; j++)
                {
                	  // 更新与标记顶点关联的所有具有较小权值的边 
                	  // 找到所有与以标记顶点相邻的未标记顶点的边，留着选择最小边      
                	  // 重新选择具有最小代价的边     	  
                    if( !Mark[j] && (Matrix[index][j] < Cost[j]) )
                    {
                        Cost[j]  = Matrix[index][j];
                        P[j] = index;
                    }
                }
            }
        }
    }

分析算法，假设网中有n个顶点，则第一个进行初始化的循环语句的频度为n，第二个循环语句的频度也为n。其中有两个内循环：其一是在Cost\[\]中求最小值，其二是重新选择具有最小代价的边，频度都为n。由此，普利姆算法的时间复杂度为O(n2)，与网中的边数无关，因此适用于求边稠密的网的最小生成树。

既然最小连通网是以边的权值之和为最终目标，那么是不是可以直接选择边，而不是通过顶点来选择边呢？

克鲁斯卡尔算法就是直接选择边来求图的最小生成树的。

基本思想：

1.对于 n 个顶点的图 G = \{ V, E \}；

2. 构造一个只有 n 个顶点, 没有边的图 G**’** = \{ V, ∅ \}；

3. 在 E 中选择一条具有最小权值的边, 若该边的两个顶点不构成回路，则将此边加入到 T 中; 否则将此边舍去，重新选择一条权值最小的边；

4. 如此重复下去，直到所有顶点都连通为止。

算法实现步骤：

1. 定义边结构体；

![70 4][]

2. 定义边集数组并排序；

![70 5][] ![70 6][]

定义辅助数组 P\[n\],其中 n 为顶点数目，P\[n\]的用于记录边顶点的首尾连接关系，例如：

![70 7][]

算法核心思想：

1.遍历 edges 数组中的每个元素

1.1.通过 P 数组查找 begin 顶点的最终连接点 v1

1.2.通过 P 数组查找 end 顶点的最终连接点 v2

1.2.1.v1 != v2 则：当前边为最小连通网中的边，记录连接关系P\[v1\] = v2;

1.2.2. v1 == v2 则: 产生回路，舍弃当前边。

克鲁斯卡尔算法实现参见：[克鲁斯卡尔算法][Link 1]

[70]: /images/20220530/a60cfa096a5a4f468deda51ae92c0fe7.png
[70 1]: https://img-blog.csdn.net/20180302215526492?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxNDc1NDg0MQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 2]: https://img-blog.csdn.net/20180302215535914?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxNDc1NDg0MQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 3]: /images/20220530/bcaacd943eca4a0a844eb77d3e700f0f.png
[70 4]: /images/20220530/d96801a6d65a405b8124410ba416eafd.png
[70 5]: https://img-blog.csdn.net/20180302222803653?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxNDc1NDg0MQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 6]: /images/20220530/597bd492a69d48109cc46ab9b5c3b2cf.png
[70 7]: /images/20220530/1ec3a72904dd4eb2bd638ef37da38d0a.png
[Link 1]: http://www.cnblogs.com/qianbixin/p/5005161.html