最小生成树

目录

最小代价生成树

目前为止的学习,我们能够看到现实中的很多问题都和图结构息息相关,因为现实中的关系往往不是一对一或一对多的关系,而是多对多的关系。例如有这样一个场景,假设我要在 n 个城市之间架设通信联络网,首先我们先明确一个前提:任意两个城市之间都需要架设通信网络?答案是否定的,因为这么做劳民伤财的,其实两个城市之间的互联可以通过多条链路连通,并不需要一定是直达的。
最小生成树
根据这一点,我们就能够明白,连通 n 个城市需要 n - 1 条链路。接下来考虑下一个问题,不同城市间可能存在着多条路径,路径有长短,也就是说假设的 n - 1 条链路会因为城市间距离的不同而产生成本上的差异。因此我们需要考虑如何选择出这样 n - 1 条路径,使得线路假设的成本最小。
最小生成树
在一个连通图中的所有生成树中,存在各边代价之和最小的生成树,则称该生成树为该联通网的最小代价生成树。在上面的例子中可以用联通网表示,在一个图结构中的顶点可以用于表示 n 个城市,边表示顶点之间的路径,用权表示城市之间的距离,这个使我们判断成本的重要参考。

MST

MST 性质是一些构造最小生成树算法使用的原理,因此先学习 MST 性质是下文的预备知识。

性质

假设 N = (V,E) 是一个连通网,U 是顶点集 V 的一个非空子集。若 (u,v) 是一条具有最小生成树权值(代价)的边,其中 u ∈ U,v ∈ V - U,则必存在一棵包含边 (u,v) 的最小生成树。
需要注解的是,在生成树构造时,图结构中的 n 个顶点分属于 2 个集合:

  1. 已落在生成树上的顶点集:U
  2. 尚未落在生成树上的顶点集:V - U

那么我们就需要在所连通的 U 中顶点和 V - U 中顶点的边中选取权值最小的边。

证明

反证法:假设网 N 的任何一棵最小生成树都不包含 (u,v)。设 T 是连通网上的一棵最小生成树,当将边 (u,v) 加入到 T 中时,由生成树的定义,T 中必存在一条包含 (u,v) 的回路。另一方面,由于 T 是生成树,则在 T 上必存在另一条边 (u',v'),其中 u' ∈ U,v'∈ Y - U,且 u 和 u' 之间、v 和 v' 之间均有路径相通。删去边 (u',v'),便可消除上述回路,同时得到另一棵生成树 T'。因为 (u,v) 的权值不高于 (u',v'),则 T 的权值亦不高于 T,T’ 是包含 (u',v') 的一棵最小生成树。由此和假设矛盾。 ——《数据结构(C语言版)》

Prim 算法(加点法)

该算法时间复杂度为 O(n2),与图结构的边数无关,适合稠密图。由于直接讲算法难以理解,所以我先模拟一下算法。

算法模拟

所谓加点法就是每次操作的都是点啦。假设有如下图结构,从顶点 0 出发构造最小生成树。
最小生成树
首先顶点 0 选择它能够延伸出去的最短路径,那就是 0->1,因此我们把顶点 1 加入到点集中。
最小生成树
接着顶点 0,1 选择它能够延伸出去的最短路径,那就是 0->3,因此我们把顶点 3 加入到点集中。
最小生成树
接着顶点 0,1,3 选择它能够延伸出去的最短路径,那就是 1->2,因此我们把顶点 2 加入到点集中。
最小生成树
接着顶点 0,1,3,2 选择它能够延伸出去的最短路径,那就是 2->5,因此我们把顶点 5 加入到点集中。(由于我们要保证选取的边不能构成环,因此不能选择已经在点集中的 0->2 路径。)
最小生成树

最后顶点 0,1,3,2,5 选择它能够延伸出去的最短路径,那就是 5->4,因此我们把顶点 4 加入到点集中。到此所有的点都被添加到生成树中了,构造完毕。
最小生成树

算法流程

假设 N = (V,E) 是连通网,TE 是 N 上最小生成树中边的结合。

  1. U = {u0}(u0 ∈ V),TE = {};
  2. 在所有 u ∈ U,v ∈ V - U 的边 (u,v)∈ E 中找到一条权值最小的边 (u0,v0) 并入集合 TE,同时 v0 并入 U;
  3. 重复第二步,直至 U = V 为止。
  • 每次选择最小边的时候,可能存在多条同样权值的边可选,不要犹豫任选其一就行。

算法实现

结构设计

当我使用邻接矩阵来存储时,由于需要描述 U 到 V-U 具有最小权值的边,因此需要两个数组来辅助:

  1. lowcost 数组:存储最小边上的权值;
  2. adjvex 数组:存贮最小边在 U 中的顶点。

算法步骤

首先将初始顶点 u 加入 U 中,对其每一个顶点 vj,将 lowcost 数组和 adjvex 数组初始化为到 u 的边信息。
接着循环 n - 1 次,每次循环进行如下操作:

  1. 从各个边中选出最小的边 lowcost[k] 选出;
  2. 将 k 顶点加入 U 中;
  3. 更新剩余每组最小边的信息,对于 V-U 中的边,若存在新的边权值比现有边更小,则更新 lowcost 数组为新的权值。

代码实现

#define INFINITY 65535
void MiniSpanTree_Prim(MGraph G)
{
    int min;
    int i,j,k;
    int adjvex[MAXV];    //保存相关顶点下标
    int lowcost[MAXV];    //保存相关顶点间边的权值
    
    lowcost[0] = 0;    //v0 加入生成树
    adjvex[0] = 0;    //初始化第一个顶点下标为 0
    for(i = 1; i < G.n; i++)    //初始化,循环除下标 0 外的所有顶点
    {
        lowcost[i] = G.edges[0][i];    //将 v0 顶点存在边的权值存入 lowcost
        adjvex[i] = 0;    //初始化都为 v0 的下标
    }
    for(i = 1; i < G.n; i++)
    {
        min = INFINITY;    //初始化最小权值为 ∞
        j = 1;
        k = 0;
        while(j < G.n)    //循环全部顶点
        {
            if(lowcost[j] != 0 && lowcost[j] < min)
            {                //若权值不为 0 且小于 min
                min = lowcost[j];    //令当前权值为最小值
                k = j;    //当前最小值的下标拷贝给 k
            }
            j++;
        }
        cout << adjvex[k] << k;    //输出当前顶点边中权值最小边
        lowcost[k] = 0;    //将顶点权值设为 0 表示添加入生成树
        for(j = 1; j < G.n; j++)
        {
            if(lowcost[j] != 0 && G.edges[k][j] < lowcost[j])
            {         //若下标为 k 的顶点各边权值小于当前顶点未被加入生成树权值
                lowcost[j] = G.edges[k][j];    //将最小权值存入 lowcost
                adjvex[j] = k;    //将下标为 k 的顶点存入 adjvex
            }
        }
    }
}

Kruskal 算法(加边法)

假若以“堆”结构来存放边进行堆排序,对于包含 e 条边的网,上述算法排序的时间复杂度为 O(e㏒2e)。只要采取合适的数据结构,算法的时间复杂度为 O(e㏒2e)。与普里姆算法相比,该算法更适合于求稀疏图的最小生成树。由于直接讲算法难以理解,所以我先模拟一下算法。

算法模拟

所谓加边法就是每次操作的都是点啦,假设有如下图结构。
最小生成树
在所有边挑选出一条最短的边为 (0,1),添加边。
最小生成树
对于还未被添加的边,挑选出一条最短的边为 (0,3),添加边。
最小生成树
对于还未被添加的边,挑选出一条最短的边为 (1,2),添加边。
最小生成树
对于还未被添加的边,挑选出一条最短的边为 (4,5),添加边。
最小生成树
对于还未被添加的边,挑选出一条最短的边为 (0,2),但是添加了这条边之后会形成回路,因此不能添加。
最小生成树
继续挑选出一条最短的边为 (2,5),添加边,到此所有的点都被被连通,构造完毕。
最小生成树

算法流程

假设 N = (V,E) 是连通网,将 N 中的边按权值从小到大的顺序排列。

  1. 初始状态只有 n 个顶点而没有边的非连通图 T = (V,{}),图中每个顶点都自成一个连通分量;
  2. 在 E 中选择权值最小的边,若该边依附的顶点落在 T 中不同的连通分量上(不形成回路),则将此边加入到 T 中,否则不添加而选择下一条权值最小的边;
  3. 重复步骤 2,直至 T 中的所有顶点都在同一连通分量上为止。

算法实现

结构设计

由于我们的视角放在“边”上,因此我们选择边集数组来存储图结构,为我们提取边的信息提供方便。同时为了判断是否形成回路,我们可能需要结合并查集来判断。

算法步骤

首先将边集数组中的元素按权值从小到大排序。
接着依次检查边集数组的所有边,做如下操作:

  1. 从边集数组中选择一条边 (U1,U2);
  2. 在顶点数组中分别查找 v1 和 v2 所在的连通分量 vs1 和 vs2,进行判断。若 vs1 和 vs2 不相等,表明所选的两个顶点分别属于不同的连通分量,则合并连通分量 vs1 和 vs2。若相等,表明所选的两个顶点属于同一个连通分量属于同一个连通分量,舍弃这个边,选择下一条权值最小的边。

代码实现

void MiniSpanTree_Kruskal(MGraph G)
{
    int i,n,m;
    Edge edges[MAXE];    //定义边集数组
    int parent[MAXV];    //判断回路的并查集

    for(i = 0; i < G.n; i++)
    {
        n = Find(parent, edges[i].begin);    //“查”操作
        m = Find(parent, edges[i].end);
        if(m != n)    //若 n 和 m 不相等,说明回路不存在
        {
            parent[n] = m;    //将此边结尾顶点放入下标为起点的 parent 中
            cout << edges[i].begin <<  edges[i].end << edges[i].weight << endl;
        }
    }
}

int Find(int *parent, int f)    //“查”操作
{
    while(parent[f] > 0)
        f = parent[f];
    return f;
}

实例:公路村村通

情景需求

最小生成树

测试样例

输入样例

6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3

输出样例

12

情景分析

这个情景思路很明确,就是让我们找最小生成树,然后求一下最小生成树中权值的和。需要注意的是输入数据不足以保证畅通,这句话的意思是说给出的所有顶点可能会因为缺边导致无法连通,因此我们就需要对这种情况进行判断。

代码实现

Prim 算法

与上文的代码几乎无异,需要添加一个判断图是否连通的功能而已。判断方法是看看每一轮循环 k 值有没有被修改,如果没有被修改就证明图的连接被切断,也就是不连通,直接 return 就行了。

int MiniSpanTree_Prim(MGraph G)
{
    int min;
    int i, j, k;
    int adjvex[MAXV];    //保存相关顶点下标
    int lowcost[MAXV];    //保存相关顶点间边的权值
    int cost = 0;

    lowcost[1] = 0;    //v1 加入生成树
    adjvex[1] = 0;    //初始化第一个顶点下标为 1
    for (i = 2; i <= G->n; i++)    //初始化,循环除下标 1 外的所有顶点
    {
        lowcost[i] = G->edges[1][i];    //将 v1 顶点存在边的权值存入 lowcost
        adjvex[i] = 1;    //初始化都为 v1 的下标
    }
    for (i = 2; i <= G->n; i++)
    {
        min = INFINITY;    //初始化最小权值为 ∞
        j = 1;
        k = 0;
        while (j <= G->n)    //循环全部顶点
        {
            if (lowcost[j] != 0 && lowcost[j] < min)
            {                //若权值不为 0 且小于 min
                min = lowcost[j];    //令当前权值为最小值
                k = j;    //当前最小值的下标拷贝给 k
            }
            j++;
        }
        if (k != 0)    //若 k 值被修改,证明成功添加了点
        {
            cost += min;    //计算费用
            lowcost[k] = 0;    //将顶点权值设为 0 表示添加入生成树
        }
        else    //若 k 值没被修改,证明图不连通,断了联系
        {
            return -1;
        }
        for (j = 2; j <= G->n; j++)
        {
            if (lowcost[j] != 0 && G->edges[k][j] < lowcost[j])
            {         //若下标为 k 的顶点各边权值小于当前顶点未被加入生成树权值
                lowcost[j] = G->edges[k][j];    //将最小权值存入 lowcost
                adjvex[j] = k;    //将下标为 k 的顶点存入 adjvex
            }
        }
    }
    return cost;
}

实例:通信网络设计

情景需求

最小生成树

测试样例

输入样例

5 4
1 2 3
1 3 11
2 3 8
4 5 9

输出样例

NO!
1 part:1 2 3
2 part:4 5

情景分析

这个情景思路也很明确,就是让我们找最小生成树,然后求一下最小生成树中权值的和。不过,我们可能会遇到像样例那样缺乏数据支撑的情况,也就是图被分割成了好几部分,这个情景对找到图被分割的各个部分提出了要求。
如何实现这个功能?我们联想到并查集,这是因为并查集这个结构能够描述一堆数据元素所在的集合关系,我们可以用并查集来确定一下图结构中被分为了几个部分。若所有点都属于同一个集合中,说明图是连通的,可以找最小生成树,若并查集中存在超过 1 个集合,说明图被分割成了好几部分,那就要分别输出各部分。
两种算法都可以实现功能,我选择 Prim 算法,不过我只有确定并查集中仅存在一个集合我才启动算法。

建图算法

我需要构造一个并查集来确定有多少个集合,因此我可以在建立邻接矩阵的时候顺手建好并查集。

伪代码

最小生成树

代码实现

主函数

在主函数需要先判断并查集中是否仅存在一个集合,若仅存在一个集合才启动 Prim 算法。

伪代码

最小生成树

代码

参考资料

《大话数据结构》—— 程杰 著,清华大学出版社
《数据结构(C语言版|第二版)》—— 严蔚敏 李冬梅 吴伟民 编著,人民邮电出版社

上一篇:二叉树的非递归(迭代)统一实现“前中后序遍历”详解


下一篇:P5787 【模板】线段树分治