最小代价生成树

目前为止的学习，我们能够看到现实中的很多问题都和图结构息息相关，因为现实中的关系往往不是一对一或一对多的关系，而是多对多的关系。例如有这样一个场景，假设我要在 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 个集合：

已落在生成树上的顶点集：U
尚未落在生成树上的顶点集：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(n²)，与图结构的边数无关，适合稠密图。由于直接讲算法难以理解，所以我先模拟一下算法。

算法模拟

所谓加点法就是每次操作的都是点啦。假设有如下图结构，从顶点 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 上最小生成树中边的结合。

U = {u0}(u0 ∈ V)，TE = {}；
在所有 u ∈ U，v ∈ V - U 的边 (u，v)∈ E 中找到一条权值最小的边 (u0,v0) 并入集合 TE，同时 v0 并入 U；
重复第二步，直至 U = V 为止。

每次选择最小边的时候，可能存在多条同样权值的边可选，不要犹豫任选其一就行。

算法实现

结构设计

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

lowcost 数组：存储最小边上的权值；
adjvex 数组：存贮最小边在 U 中的顶点。

算法步骤

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

从各个边中选出最小的边 lowcost[k] 选出；
将 k 顶点加入 U 中；
更新剩余每组最小边的信息，对于 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㏒₂e)。只要采取合适的数据结构，算法的时间复杂度为 O(e㏒₂e)。与普里姆算法相比，该算法更适合于求稀疏图的最小生成树。由于直接讲算法难以理解，所以我先模拟一下算法。

算法模拟

所谓加边法就是每次操作的都是点啦，假设有如下图结构。

在所有边挑选出一条最短的边为 (0,1)，添加边。

对于还未被添加的边，挑选出一条最短的边为 (0,3)，添加边。

对于还未被添加的边，挑选出一条最短的边为 (1,2)，添加边。

对于还未被添加的边，挑选出一条最短的边为 (4,5)，添加边。

对于还未被添加的边，挑选出一条最短的边为 (0,2)，但是添加了这条边之后会形成回路，因此不能添加。

继续挑选出一条最短的边为 (2,5)，添加边，到此所有的点都被被连通，构造完毕。

算法流程

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

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

算法实现

结构设计

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

算法步骤

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

从边集数组中选择一条边 (U1,U2);
在顶点数组中分别查找 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;
}

实例：公路村村通

情景需求

测试样例

输入样例

输出样例

情景分析

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

代码实现

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;
}

实例：通信网络设计

情景需求

测试样例

输入样例

输出样例

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

情景分析

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

建图算法

我需要构造一个并查集来确定有多少个集合，因此我可以在建立邻接矩阵的时候顺手建好并查集。对于并查集不是很熟悉的朋友可以看我的另一篇博客并查集(Union Find)。

伪代码

代码实现

void CreateMGraph(MGraph& g, int n, int e, int parent[])
{
	int i, j;
	int point1, point2;
        int money;

	g = new GraphNode;
	for (i = 1; i <= n; i++)
	{
                parent[i] = i;
		for (j = 1; j <= n; j++)
		{
                      if (i == j)
                            g->edges[i][j] = 0;
                      else
	                    g->edges[i][j] = INFINITY;
		}
	}
	g->n = n;
	g->e = e;

	for (i = 0; i < e; i++)
	{
		cin >> point1 >> point2 >> money;
		g->edges[point1][point2] = g->edges[point2][point1] = money;
                Union(parent, point1, point2);
	}
}

主函数

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

伪代码

代码

int main()
{
    MGraph g;
    int n, e;
    int count = 0;
    int parent[MAXV];
    int i, j;
    int fre = 1;

    cin >> n >> e;
    CreateMGraph(g, n, e, parent);
    for (int i = 1; i <= n; i++)
    {
        if (parent[i] == i)
        {
            count++;
        }
    }
    if (count == 1)
    {
        cout << "YES!\n" << "Total cost:" << MiniSpanTree_Prim(g) << endl;
    }
    else
    {
        cout << "NO!" << endl;
        for ( i = 1; i <= n; i++)
        {
            if (parent[i] == i)
            {
                cout << fre << " part:" << i;
                for ( j = i + 1; j <= n; j++)
                {
                    if (parent[j] == i)
                    {
                        cout << " " << j;
                    }
                }
                fre++;
                cout << endl;
            }
        }
    }
    return 0;
}

破圈法

避圈法和破圈法

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边，在一个连通图中的所有生成树中，存在如此各边代价之和最小的生成树，则称该生成树为该联通网的最小代价生成树。
我们熟知的 Prim 算法和 Kruskal 算法可以用来找到最小生成树，不过这两种算法的思想其实是一致的：一开始我只有有限的信息，无论是所有顶点做加边法，还是所有的边做加点法，一开始的信息都是不完整的。其实无论是加点还是加边，本质上是从最小的权的边开始，添加的是在未选中的边中的最小权值边，原理都是使用了 MST 性质去做的。在做 Prim 算法和 Kruskal 算法时我们比较关心每添加了一次边就检查看看有没有出线回路，因为生成树是不能有回路。那也就是说我要避免回路的出现，在重复添加最小权值边时就能保证将最小生成树添加出来，这种手法就被称为避圈法。
现在我们来考虑另一种思路，避圈法是把最小生成树建出来，现在我有全套的信息，我要怎么把最小生成树找出来？由于最小生成树是 n 个顶点 n - 1 条边，因此我需要将边的数量减少到 n - 1 条，一旦我满足了这点就可以认为是找到了最小生成树。所以现在的问题是怎么找需要删除的边？回顾一下什么叫生成树，生成树是没有回路的，那也就是说我只需要把边给删除掉，使得该结构不存在回路即可。当然你可能要问了直接随意删除不就好了吗？这样剩余 n - 1 条边绝对是不存在回路的。但是这么做可能会导致本来我的生成树是可以保证连通的，但是就被拆成了多个部分，这个不是我们愿意发生的事情。所以删除边的时候都需要验证这条边的有或无是否导致回路的存在。
还有一个问题是，如果我漫无目的地删除边，那么这样得到的生成树未必不是最小生成树。这个问题解决还是比较容易的，我直接去找现有的权值最大边即可，然后判断回路存在后直接把最长边。这样每次操作的都是最长边，剩余的边就会是短边，对应的生成树就是最小生成树。

模拟生成

我们还是拿这个图结构来看，首先对于破圈法来说，我拥有全套信息。

接下来我去找权值最大的边，应该是 3-5，判断一下有这条边将存在回路，删除。

继续寻找权值最大的边，应该是 1-4，判断一下有这条边将存在回路，删除。

继续寻找权值最大的边，应该是 2-5，判断一下有这条边对生成树存在回路是没有影响的。因为现在回路存在于 0,1,2 这 3 个点(用橙色标出) 2-5 的存在与否并不影响，因此保留。

继续寻找权值最大的边，应该是 0-2，判断一下有这条边将存在回路，删除。

此时边的数量已经缩小至 n - 1,说明构造完毕。

参考资料

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

数据结构：最小生成树

最小代价生成树

MST

性质

证明

Prim 算法(加点法)

算法模拟

算法流程

算法实现

结构设计

算法步骤

代码实现

Kruskal 算法(加边法)

算法模拟

算法流程

算法实现

结构设计

算法步骤

代码实现

实例：公路村村通

情景需求

测试样例

输入样例

输出样例

情景分析

代码实现

Prim 算法

实例：通信网络设计

情景需求

测试样例

输入样例

输出样例

情景分析

建图算法

伪代码

代码实现

主函数

伪代码

代码

破圈法

避圈法和破圈法

模拟生成

参考资料

推荐阅读