[图](7)最小生成树
无向图的连通分量和生成树
在对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问到图中所有顶点
对非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集
例如下图中的连通分量为：
对应上图G3的邻接表如下图所示：
对如上邻接表进行深度优先搜索遍历，3次调用DFS过程(分别从顶点A、D和G出发)得到的顶点访问序列为：
- A L M J B F C D
- D E
- G K H I
这3个顶点集分别加上所有依附于这些顶点的边，便构成了非连通图G3的3个连通分量，设E(G)为连通图G中所有便得集合，则从不图中任一顶点出发遍历图时，必定将E(G)分成两个集合T(G)和B(G)，其中T(G)是遍历图过程中历经得边得集合
B(G)是剩余的边的集合，显然，T(G)和图G中所有顶点一起构成连通图G的极小连通子图，按照生成树的定义，它是连通图的一棵生成树，并且称由深度优先搜索得到的为深度优先生成树，由广度优先搜索得到的为广度优先生成树
例如下图所示：
图中虚线为集合B(G)的边
对于非连通图，每个连通分量中的顶点集，和遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的生成森林，例如下图所示：
它是由3棵深度优先生成树组成
假设以孩子兄弟链表作生成森林的存储结构，则下列算法生成非连通图的深度优先生成森林
/*typedef struct CSNode{
GNtype data;
struct CSNode *lchild;
struct CSNode *rchild;
}*CSTree;*/
void DFSForest(Graph G, CSTree* T) {
//建立无向图G的深度优先生成森林的(最左)孩子(右)兄弟链表T
T = NULL;
for (int v = 0; v < G.vexnum; v++)
visited[v] = FALSE;
for (int v = 0; v < G.vexnum; v++) {
if (!visited[v]) {//第v顶点为新的生成树的根结点
p = (CSTree)malloc(sizeof(CSNode));//分配根结点
*p = { GetVex(G,v),NULL,NULL };//给该结点赋值
if (!T) T = p;//是第一棵生成树的根(T的根)
else q->nextsibling = p;//是其他生成树的根(前一棵的根的“兄弟”)
q = p;
DFSTree(G, v, p);//建立以p为根的生成树
}
}
return;
}
void DFSTree(Graph G, int v, CSTree* T) {
//从第v个顶点出发深度优先遍历图G，建立以T为根的生成树
visited[v] = TRUE;
first = TRUE;
for (w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
if (!visited[w]) {
p = (CSTree)malloc(sizeof(CSNode));//分配孩子结点
*p = { GetVex(G,w),NULL,NULL };
if (first) {//w是v的第一个未被访问的邻接顶点
T->lchild = p;//是根的左孩子结点
first = FALSE;
}
else {
q->nextsibling = p;//是上一邻接顶点的右兄弟结点
}
q = p;
DFSTree(G, w, q);//从第w个顶点出发深度优先遍历图G，建立子生成树q
}
}
return;
}有向图的强连通分量
深度优先搜索是求有向图的强连通分量的一个新的有效方法，假设以十字链表作为有向图的存储结构，则强连通分量的步骤如下：
-
在有向图G上，从某个顶点出发沿以该顶点为尾的弧进行深度优先搜索遍历，并按其所有邻接点的搜索都完成(即退出DFS函数)的顺序将顶点排列起来，此时需对上述算法作如下两点修改：
- 在进入DFSTraverse函数时，首先进行计数变量的初始化，即在入口出加上count=0的语句
- 在退出DFS函数之前将完成搜索的顶点号记录在另一个辅助数组finished[vexnum]中，即在DFS函数结束之前加上finished[++count]=v的语句
-
在有向图G上，从最后完成搜索的顶点(即finished[vexnum-1]中的顶点)出发，沿着以该顶点为头的弧作逆向的深度优先搜索遍历，若此次遍历不能访问到有向图中所有顶点，则从余下的顶点中最后完成搜索的那个顶点出发，继续作逆向的深度优先搜索遍历
以此类推，直至有向图中所有顶点都被访问到为止，此时调用DFSTraverse时需作如下修改：
- 函数中第二个循环语句的边界条件应改为v从finished[vexnum-1]至fin-ished[0]
- 由此，每一次调用DFS作逆向深度优先遍历所访问到的顶点集便是有向图G中一个强连通分量的顶点集
例如从下列所示的有向图顶点v1出发，作深度优先搜索遍历，得到finished数组中的顶点号为(1,3,2,0)
则再从顶点v1出发作逆向的深度优先搜索遍历，得到两个顶点集{v1,v3,v4}和{v2}，这就是该有向图的两个强连通分量的顶点集
上述求强连通分量的第二步，其实质为：
- 构造一个有向图Gr，设G=(V,{A})，则Gr=(V,{Ar}),对于所有<v1,vj>∈A，必有<vj,vi>∈Ar，即Gr中拥有和G方向相反的弧
- 在有向图Gr上，从顶点finished[vexnum-1]出发作深度优先搜索遍历，可以证明，在Gr所得深度优先生成森林中每一棵树的顶点集即为G的强连通分量的顶点集
显然，利用遍历求强连通分量的时间复杂度和遍历相同。
我们在此来理解下以上三个概念：
- 生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图
- 极小连通子图：拥有图G的所有点的，即其所有顶点均是连通的，不包含回路的
- 生成森林：在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树组成了一个非连通图的生成森林
最小生成树
假设要在n个城市之间建立通信联络网，则连通n个城市只需n-1条路线，这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网
在每两个城市之间都可以设置一条线路，相应的都要付出一定的经济代价，n个城市之间，最多可能设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，以使得总的耗费最少呢？
可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价，对于n个顶点的连通网可以建立许多不同的生成树
每一棵生成树都可以是一个通信网，现在，我们要选择这样一棵生成树，也就是使总的耗费最少，这个问题就是构造连通网的最小代价生成树(Minimun Cost Spanning Tree)(简称为最小生成树)的问题。
一棵生成树的代价就是树上各边的代价之和
最小生成树的定义
生成树的代价：设G=(V,E)是一个无向连通网，生成树上各边的权值之和称为该生成树的代价
最小生成树：在图G所有生成树中，代价最小的生成树称为最小生成树
MST性质
构造最小生成树可以又多种算法，其中多数算法利用了最小生成树的下列一种简称为MST的性质，假设N=(V,{E})是一个联通网，U是顶点集V的一个非空子集，若(u,v)是一条具有最小权值(代价)的边，其中u∈U,v∈V-U，则必存在一棵包含边(u,v)的最小生成树
可以用反证法证明之，假设网N的任何一棵最小生成树都不包含(u,v)，设T是连通网上的一棵最小生成树，当将边(u，v)加入到T中时，由生成树的定义，T中必存在一条包含(u,v)的回路，另以方面，由于T是生成树，则在T上必存在另一条边(u'，v')，消除上述回路，同时得到另一棵生成树T'，因为(u，v)的代价不高于(u',v')，则T'的代价亦不高于T，T’是包含(u,v)的一棵最小生成树，由此和假设矛盾
普利姆(Prim)算法和克鲁斯卡尔(Kruskal)算法是两个利用MST性质构造最小生成树的算法
普利姆(Prim)算法
核心思想：从一个点出发，依次加入点形成集
基本思想：
-
设G=(V,E)是具有n个顶点的连通网，T=(U,TE)是G的最小生成树
T的初始状态为：{U0}(U0∈V)，TE={}
重复执行下述操作：在所有u∈U，v∈V-U的边(u,v)∈E中找一条代价最小的边(u0,v0)并入集合TE，同时v0并入U，直至U=V为止
此时TE中必有n-1条边，则T=(V,{TE})为N的最小生成树
Prim算法的基本思想用伪代码描述如下：
1.初始化：U={v0} TE={}；
2.重复下述操作直到U=V：
2.1 在E中寻找最短边(u,v),且满足u∈U，v∈V-U
2.2 U=U+{v};
2.3 TE=TE+{(u,v)};为实现这个算法需附设一个辅助数组closedge，以记录从U到V-U具有最小代价的边，对每个顶点ui∈V-U，在辅助数组中存在一个相应分量closedge[i-1]，它包括两个域，其中lowcost存储该边上的权，显然有：
closedge[i-1].lowcost=Min{cost(u,vi)} | u∈U
- cost(u,v)表示赋于边(u,v)的权
Prim算法建立最小生成树的过程如下所示：
vex域存储该边依附的在U中的顶点，例如上图按照Prim算法构造无向网的一棵最小生成树的过程，在构造过程中辅助数组各分量值的变化如下表格所示：
| 1 | 2 | 3 | 4 | 5 | U | V-U | k | 对应图 | |
|---|---|---|---|---|---|---|---|---|---|
| ▲adjvex | v1 | v1 | v1 | {v1} | {v2,v3,v4,v5,v6} | 2 | (b) | ||
| lowcost | 6 | 1 | 5 | ||||||
| ▲adjvex | v3 | v1 | v3 | v3 | {v1,v3} | {v2,v4,v5,v6} | 5 | (c) | |
| lowcost | 5 | 0 | 5 | 6 | 4 | ||||
| ▲adjvex | v3 | v6 | v3 | {v1,v3,v6} | {v2,v4,v5} | 3 | (d) | ||
| lowcost | 0 | 2 | 6 | 0 | |||||
| ▲adjvex | v3 | v3 | {v1,v3,v6,v4} | {v2,v5} | 1 | (e) | |||
| lowcost | 5 | 0 | 0 | 6 | 0 | ||||
| ▲adjvex | v2 | {v1,v3,v6,v4,v2} | {v5} | 4 | (f) | ||||
| lowcost | 0 | 0 | 0 | 3 | 0 | ||||
| ▲adjvex | {v1,v3,v6,v4,v2,v5} | {} | |||||||
| lowcost | 0 | 0 | 0 | 0 | 0 |
k为邻接矩阵/表 中顶点集的下标
初始状态时，由于U={v1}，则到V-U中各顶点的最小边，即为从依附于顶点 1 的各条边中，找到一条代价最小的边(u0,v0)=(1,3)为生成树上的第一条边，同时将v0(=v3)并入集合U
然后修改辅助数组中的值:
- 首先将closedge[2].lowcost改为0，以示顶点v3已并入U
- 然后，由于边(v3,v2)上的权值小于closedge[1].lowcost，则需修改closedge为边(v3,v2)及其权值
- 同理修改closedge[4]和closedge[5]，以此类推，直到U=V
- 假设以二维数组表示网的邻接矩阵，且令两个顶点之间不存在的边的权值为机内允许的最大值(INT_MAX),则算法如下所示：
/*Closedge数组抽象类型定义
typedef struct ClosedgeNode {
VRType adjvex;
InfoType lowcost;
}Closedge[MAX_VERTEX_NUM];
*/
/*找寻当前耗费最小的邻接点*/
int MinVex(MGraph G, Closedge A) {
int Min = INFINITY;
int index = 0;
for (int i = 0; i < G.vexnum; i++) {
if (A[i].adjvex == 0) continue;
if (Min > A[i].lowcost) {
Min = A[i].lowcost;
index = i;
}
}
return index + 1;
}
Status Prim(MGraph G,VRType v) {
//从v出发寻找其最短路径
Closedge A;//生成辅助数组A，用来存储此时的 U集合
for (int i = 0; i < G.vexnum; i++) {
//初始化Closedge辅助数组
A[i].adjvex = v;
A[i].lowcost = G.arcs[v - 1][i].adj;
}
A[v - 1].adjvex = 0;//标记为0，代表已将该领导添加至U集合中
A[v - 1].lowcost = 0;
printf("V(%d)--> ", v);//输出该顶点
for (int i = 0; i < G.vexnum - 1; i++) {
int k = MinVex(G, A);//找寻最近的邻接点
printf("V(%d)--> ", k);
A[k - 1].adjvex = 0;//将其添入集合U
A[k - 1].lowcost = 0;
for (int j = 0; j < G.vexnum; j++) {
//更新当前集合U中所有边集
if (A[j].adjvex != 0 && G.arcs[k - 1][j].adj < A[j].lowcost) {
A[j].adjvex = k;
A[j].lowcost = G.arcs[k - 1][j].adj;
}
}
}
return OK;
}假设对上图中的无向网，利用Prim算法，将输出的边集如下所示：
分析Prim算法，假设网中有n个顶点，则第一个进行初始化的循环语句的频度为n，第二个循环语句的频度为n-1，其中有两个内循环，其一是在closedge[v].lowcost中求最小值，其频度为n-1，其二是重新选择最具有最小代价的边，其频度为n
由此，Prim算法的时间复杂度为O(n²)，与网中的边数无关，因此适用于求边稠密的网的最小生成树
而克鲁斯卡尔算法恰恰相反，它的实际复杂度为O(eloge)(e为网中边的数目)，因此它相对于Prim算法而言，适合求边稀疏的网的最小生成树。
克鲁斯卡尔(Kruskal)算法
基本思想：
- 设无向连通图G=(V,E)，令G的最小生成树为T=(U,TE)，其初始状态为U=V，TE={}
- 然后，按照边的权值由大到小的顺序，考察G的边集E中各条边
- 若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量
- 若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树
若将上述用伪代码描述，则如下所示：
- 初始化：U=V,TE={}
- 重复下述操作直到T中的连通分量个数为1：
- 在E中寻找最短边(u,v)
- 如果顶点u、v位于T的两个不同连通分量，则：
- 将边(u,v)并入TE
- 将这两个连通分量合为一个
- 标记边(u,v)，使得(u,v)不参加后续最短边的选取
关键：如何判别被考察边的两个顶点是否位于两个连通分量
下述图例为依照克鲁斯卡尔算法构造一棵最小生成树的过程：
边集数组
在克鲁斯卡尔算法中，因为其是对边进行操作，邻接矩阵和邻接表都不会合适，因为其需要搜索所有边才能找到最短边，则需要改进数据结构用于克鲁斯算法
因此考虑用边集数组存储图中的边，为了提高查找速度，使用快排或堆排提高查找速度
我们把连通分量全部看为树，然后通过判断这些树是否有同一个根节点，即可判断其是否已形成回路
边集数组的抽象数据类型定义如下所示：
#define MaxVertex 10
#define MaxEdge 100
typedef int dataType;//顶点集类型
struct EdgeType {
int from, to;//边依附的两个顶点
int weight;//边上的权值
};
struct EdgeGraph {
dataType vertex[MaxVertex];//存放图顶点的数据
EdgeType edge[MaxEdge];//存放边的数组
int vertexNum, edgeNum;//图的顶点数和边数
};数据结构逻辑图如下所示：
连通分量：Kruskal算法实质上是使生成树以一种随意的方式生长，初始时每个顶点构成一棵生成树，然后每生长一次就将两棵树合并，到最后合并成一棵树
因此，可以设置一个数组parent[n]，元素parent[i]表示顶点i的双亲，初始时，parent[i]=-1，表示顶点i没有双亲，即该结点是所在生成树的根结点，对于边(u,v)，设vex1和vex2，分别表示两个顶点所在树的根结点，如果vex1≠vex2，则顶点u和v必位于不同的连接分量，令parent[vex2]=vex1，实现将两棵树合并
算法如下所示：
void Qsort(EdgeGraph* G,int L,int R) {
if (L >= R) return;
int x = G->edge[L].weight;
int left = L - 1, right = R + 1;
while (left < right) {
do left++; while (G->edge[left].weight < x);
do right--; while (G->edge[right].weight > x);
if (left < right) {
EdgeType temp = G->edge[left];
G->edge[left] = G->edge[right];
G->edge[right] = temp;
}
}
Qsort(G, L, right);
Qsort(G, right + 1, R);
}
//查找其根结点
int Findroot(int *parent, int i) {
int root = i;
while (parent[root] > -1) root = parent[root];
return root;
}
//创建边集数组
Status CreateEdgeArray(EdgeGraph *G) {
char tmp;
scanf("%d,%d%c", &G->vertexNum, &G->edgeNum, &tmp);
for (int i = 0; i < G->vertexNum; i++)
scanf("%d%c", &G->vertex[i], &tmp);
for (int i = 0; i < G->edgeNum; i++)
scanf("%d,%d,%d%c", &G->edge[i].from, &G->edge[i].to, &G->edge[i].weight, &tmp);
Qsort(G, 0, G->edgeNum - 1);//对边集数组按权值排序
return OK;
}
Status Kruskal(EdgeGraph G) {
int* parent = (int*)malloc(sizeof(int) * G.vertexNum);
for (int i = 0; i < G.vertexNum; i++) parent[i] = -1;//初始化双亲数组
int count = 0;
for (int j = 0; j < G.edgeNum; j++) {
int vex1 = Findroot(parent, G.edge[j].from);//找到所在生成树的根节点
int vex2 = Findroot(parent, G.edge[j].to);
if (vex1 != vex2) {//如果其不属于同一个连通分量，则代表可以并入生成树
printf("<%d,%d,%d>、", G.edge[j].from, G.edge[j].to,G.edge[j].weight);
parent[vex2] = vex1;
count++;//边树++
if (count == G.vertexNum - 1)
return OK;
}
}
return OK;
}克鲁斯卡尔算法至多对每条边扫描一次，若采用堆排或快排则每次选择最小代价的边仅需O(loge)的时间
Prim和Kruskal算法比较
- Prim算法是对点做操作，维护一个在最小生成树中的点的顶点集U，以及一个待处理点的顶点集V-U，每次找出连接这两个集合的最短边，构成最小生成树，并将顶点加入集合U，直到所有顶点都处理完毕
- Kruskal算法是对边做操作，每次选出一条最短边，如果它和当前最小生成树不构成回路，就将其加入最小生成树，否则将其删除，直到所有边都处理完毕