一个连通图的生成树是一个极小的连通子图,包含图中全部顶点,但只有足以构成一棵树的n-1条边。于是,将构造连通网的最小代价生成树称为最小生成树(Minimum Cost Spanning Tree)。经典的算法有两种,普里姆算法和克鲁斯卡尔算法,下面详细介绍。
/*Prim算法生成最小生成树,邻接矩阵,时间复杂度O(n^2)*/
void MiniSpanTree(MGraph G){
int min,i,j,k;
int adjvex[MAXSIZE]; //保存相关顶点下标
int lowcost[MAXSIZE]; //保存边的权值
lowcost[0]=0; //初始化,将v0加入生成树,下标为0的已加入树
adjvex[0]=0; //初始化第一个顶点下标为0
/*读取邻接矩阵第一行数据,并将数组赋值给lowcost数组*/
for(i=1;i
首先将 v0 加入最小生成树, v0 行的邻接矩阵为 [0,10,∞,∞,∞,11,,∞,∞,∞] ,adjvex全部为0,lowcost等于其邻接矩阵,找到其中的最小值10,对应的顶点为 v1;
将 v1 加入到最小生成树中,并将lowcost和 v1 这行的邻接矩阵进行比较,更小的加入到lowcost中,为0的不参与比较,所以lowcost=[0,0,18,∞,∞,11,16,∞,12] ,adjvex={0,0,1,0,0,0,1,0,1},发现当前的lowcost中的最小值为11,下标为5,对应的顶点为 v5;
将 v5 加入到最小生成树中,并将lowcost和 v5 这行的邻接矩阵进行比较,更小的加入到lowcost中,为0的不参与比较,所以lowcost=[0,0,18,∞,26,0,16,∞,12] ,adjvex={0,0,1,0,5,0,1,0,1},发现当前的lowcost中的最小值为12,下标为8,对应的顶点为 v8;
将 v8 加入到最小生成树中,并将lowcost和 v8 这行的邻接矩阵进行比较,更小的加入到lowcost中,为0的不参与比较,所以lowcost=[0,0,8,21,26,0,16,∞,0] ,adjvex={0,0,8,8,5,0,1,0,1},发现当前的lowcost中的最小值为8,下标为2,对应的顶点为 v2;
将 v2 加入到最小生成树中,并将lowcost和 v2 这行的邻接矩阵进行比较,更小的加入到lowcost中,为0的不参与比较,所以lowcost=[0,0,0,21,26,0,16,∞,0] ,adjvex={0,0,8,8,5,0,1,0,1},发现当前的lowcost中的最小值为16,下标为6,对应的顶点为 v6;
将 v6 加入到最小生成树中,并将lowcost和 v6 这行的邻接矩阵进行比较,更小的加入到lowcost中,为0的不参与比较,所以lowcost=[0,0,0,21,26,0,0,19,0] ,adjvex={0,0,8,8,5,0,1,6,1},发现当前的lowcost中的最小值为19,下标为7,对应的顶点为 v7;
将 v7 加入到最小生成树中,并将lowcost和 v7 这行的邻接矩阵进行比较,更小的加入到lowcost中,为0的不参与比较,所以lowcost=[0,0,0,16,7,0,0,0,0] ,adjvex={0,0,8,7,7,0,1,6,1},发现当前的lowcost中的最小值为7,下标为4,对应的顶点为 v4;
将 v4 加入到最小生成树中,并将lowcost和 v4 这行的邻接矩阵进行比较,更小的加入到lowcost中,为0的不参与比较,所以lowcost=[0,0,0,16,0,0,0,0,0] ,adjvex={0,0,8,7,7,0,1,6,1},发现当前的lowcost中的最小值为16,下标为3,对应的顶点为 v3;
将 v3 加入到最小生成树中,并将lowcost和 v3 这行的邻接矩阵进行比较,更小的加入到lowcost中,为0的不参与比较,所以lowcost=[0,0,0,0,0,0,0,0,0] ,adjvex={0,0,8,7,7,0,1,6,1},完成。
克鲁斯卡尔(Kruskal)算法
普里姆(Prim)算法是以某顶点为起点,逐步找各顶点上最小权值的边来构建最小生成树。直接以边为目标构建,权值在边上,直接找最小权值的边来构建生成树,在构建时要考虑是否会形成环路,因此用到图的存储结构中的边集数组结构。
/*对边集数组Edge的定义*/
typedef struct{
int begin;
int end;
int weight;
}Edge;
将图转变为对应的边集数组,并且将它们按权值由小到大排序,如下图所示:
数组 |
begin |
end |
weight |
---|---|---|---|
edges[0] |
4 |
7 |
7 |
edges[1] |
2 |
8 |
8 |
edges[2] |
0 |
1 |
10 |
edges[3] |
0 |
5 |
11 |
edges[4] |
1 |
8 |
12 |
edges[5] |
3 |
7 |
16 |
edges[6] |
1 |
6 |
16 |
edges[7] |
5 |
6 |
17 |
edges[8] |
1 |
2 |
18 |
edges[9] |
6 |
7 |
19 |
edges[10] |
3 |
4 |
20 |
edges[12] |
3 |
8 |
21 |
edges[13] |
3 |
6 |
24 |
edges[14] |
4 |
5 |
26 |
/*Kruskal算法生成最小生成树,边集数组,时间复杂度O(eloge)*/
void MiniSpanTree_Kruskal(MGraph G){
int i,n,m;
Edge edges[MAXEDGE]; //定义边集数组,MAXEDGE边数极大值
int parent[MAXVEX]; //判断边与边是否形成环路
/*省略将邻接矩阵G转化为边集数组edges并按权由小到大排序的代码,形成edges一维数组*/
for(i=0;i0) f=parent[f];
return f;
}
开始i=0,查询边集数组得到(
然后i=1,查询边集数组,edges[1]得到边(
然后i=2,查询边集数组,edges[2]得到边(
然后i=3,查询边集数组,edges[3]得到边(
然后i=4,查询边集数组,edges[4]得到边(
然后i=5,查询边集数组,edges[5]得到边(
然后i=6,查询边集数组,edges[6]得到边(
然后i=7,查询边集数组,edges[7]得到边(
然后i=8,查询边集数组,edges[8]得到边(
然后i=9,查询边集数组,edges[9]得到边(
此后面的循环均会造成环路,最终最小生成树的构造过程如下:
小结:Kruskal算法针对边展开,边数少时效率很高,即对稀疏图有很大优势;Prim算法对于稠密图,即边数非常多时会更好。