一个连通图的生成树是一个极小的连通子图,它含有图中全部顶点,但只有足以构成一棵树的n-1条边。那么我们把构造连通网的最小代价生成树称为最小生成树。
找连通网的最小生成树,经典的有两种算法,普里姆算法和克鲁斯卡尔算法。下面分别介绍两种算法。
一、普里姆(Prim)算法
普里姆算法,图论中的一种算法,可在加权连通图里搜索最小生成树。意即此算法搜索到的边子集所构成的树中,不但包括连通图里的所有顶点,且其所有边的权值之和亦为最小。
1.1 算法描述
从单一顶点开始,普里姆算法按照以下步骤逐步扩大树中所含顶点的数目,直到遍及连通图的所有顶点。
(1)输入:一个加权连通图,其中顶点集合为V,边集合为E;
(2)初始化:Vnew =
{x},其中x为集合V中的任一节点(起始点),Enew = {};
(3)重复下列操作,直到Vnew =
V:
在集合E中选取权值最小的边(u,
v),其中u为集合Vnew中的元素,而v则不是(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);
将v加入集合Vnew中,将(u,
v)加入集合Enew中;
(4)输出:使用集合Vnew和Enew来描述所得到的最小生成树。
1.2 例示
1.3 普里姆算法实现
/* 邻接矩阵表示的图结构*/ #include <stdio.h> #include <stdlib.h> #include <curses.h> typedefchar VertexType; //顶点类型应由用户定义 typedefint EdgeType; //边上的权值类型应由用户定义 #define MAXVEX 100 //最大顶点数,应由用户定义 #define INFINITY 65535 //用65535来代表无穷大 #define DEBUG //邻接矩阵结构 typedefstruct { VertexType vexs[MAXVEX]; //顶点表 EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵,可看作边 intnumVertexes, numEdges; //图中当前的顶点数和边数 }Graph; //定位 intlocates(Graph *g, charch) { inti = 0; for(i = 0; i < g->numVertexes; i++) { if(g->vexs[i] == ch) { break; } } if(i >= g->numVertexes) { return-1; } returni; } //建立一个无向网图的邻接矩阵表示 voidCreateGraph(Graph *g) { inti, j, k, w; printf("输入顶点数和边数:\n"); scanf("%d,%d", &(g->numVertexes), &(g->numEdges)); #ifdef DEBUG printf("%d %d\n", g->numVertexes, g->numEdges); #endif for(i = 0; i < g->numVertexes; i++) { printf("请输入顶点%d:\n", i); g->vexs[i] = getchar(); while(g->vexs[i] == '\n') { g->vexs[i] = getchar(); } } #ifdef DEBUG for(i = 0; i < g->numVertexes; i++) { printf("%c ", g->vexs[i]); } printf("\n"); #endif for(i = 0; i < g->numEdges; i++) { for(j = 0; j < g->numEdges; j++) { g->arc[i][j] = INFINITY; //邻接矩阵初始化 } } for(k = 0; k < g->numEdges; k++) { charp, q; printf("输入边(vi,vj)上的下标i,下标j和权值:\n"); p = getchar(); while(p == '\n') { p = getchar(); } q = getchar(); while(q == '\n') { q = getchar(); } scanf("%d", &w); intm = -1; intn = -1; m = locates(g, p); n = locates(g, q); if(n == -1 || m == -1) { fprintf(stderr,"there is no this vertex.\n"); return; } //getchar(); g->arc[m][n] = w; g->arc[n][m] = g->arc[m][n]; //因为是无向图,矩阵对称 } } //打印图 voidprintGraph(Graph g) { inti, j; printf("构建的邻接矩阵如下所示.\n"); for(i = 0; i < g.numVertexes; i++) { for(j = 0; j < g.numVertexes; j++) { printf("%5d ", g.arc[i][j]); } printf("\n"); } } //prime算法最小生成树 voidMiniSpanTree_Prime(Graph g) { intmin, i, j, k; intadjvex[MAXVEX]; //保存相关顶点下标 intlowcost[MAXVEX]; //保存相关顶点间边的权值 lowcost[0] = 0; //初始化第一个权值为0,即v0加入生成树 adjvex[0] = 0; //初始化第一个顶点下标为0 for(i = 1; i < g.numVertexes; i++) { //循环除下标为0外的全部顶点 lowcost[i] = g.arc[0][i]; //将v0顶点与之有边的权值存入数组 adjvex[i] = 0; //初始化都为v0下标 } for(i = 1; i < g.numVertexes; i++) { min = INFINITY; //初始化最小权值为无穷大 j = 1; k = 0; while(j < g.numVertexes) //循环全部顶点 { //如果权值不为0,且权值小于min if(lowcost[j] != 0 && lowcost[j] < min) { min = lowcost[j]; //则让当前权值成为最小值 k = j; //将当前最小值的下标存入k } j++; } printf("(%d,%d)", adjvex[k], k); //打印当前顶点边中权值最小边 lowcost[k] = 0; //将当前顶点的权值设置为0,表示此顶点已经完成任务 for(j = 1; j < g.numVertexes; j++)//循环所有顶点 { if(lowcost[j] != 0 && g.arc[k][j] < lowcost[j]) { //若下标为k的顶点各边权值小于此前这些顶点未被加入的生成树权值 lowcost[j] = g.arc[k][j]; adjvex[j] = k; //将下标为k的顶点存入adjvex } } } printf("\n"); } intmain(intargc, char**argv) { Graph g; //邻接矩阵创建图 CreateGraph(&g); //打印网图 printGraph(g); //求最小生成树 MiniSpanTree_Prime(g); return0; }
由代码实现可知,邻接矩阵实现的普里姆算法的时间复杂度为O(n2)。
二、克鲁斯卡尔(Kruskal)算法
普力马算法是以某顶点为起点,逐步找各顶点上最小权值的边来构建最小生成树的。同样的思路,我们也可以直接就以边来构建生成树也是很自然的想法,只不过构建时要考虑是否会形成环路而已。此时,我们就用到了图的存储结构中的边集数组结构。以下是edge边集数组结构的定义代码:
1
2
3
4
5
6
7
|
//对边集数组Edge结构的定义 typedef struct { int begin; int end; int weight; }Edge; |
于是克鲁斯卡尔算法代码如下,左侧数字为行号。其中MAXEDGE为边数量的最大值,MAXVEX为顶点个数最大值。具体代码如下所示。
/* 邻接矩阵表示的图结构*/ #include <stdio.h> #include <stdlib.h> typedefchar VertexType; //顶点类型应由用户定义 typedefint EdgeType; //边上的权值类型应由用户定义 #define MAXVEX 100 //最大顶点数,应由用户定义 #define INFINITY 65535 //用65535来代表无穷大 #define DEBUG //邻接矩阵结构 typedefstruct { VertexType vexs[MAXVEX]; //顶点表 EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵,可看作边 intnumVertexes, numEdges; //图中当前的顶点数和边数 }Graph; //边集数组 #define MAXEDGE 100 typedefstruct { intbegin; intend; intweight; }Edge; //定位 intlocates(Graph *g, charch) { inti = 0; for(i = 0; i < g->numVertexes; i++) { if(g->vexs[i] == ch) { break; } } if(i >= g->numVertexes) { return-1; } returni; } //建立一个无向网图的邻接矩阵表示 voidCreateGraph(Graph *g) { inti, j, k, w; printf("输入顶点数和边数:\n"); scanf("%d,%d", &(g->numVertexes), &(g->numEdges)); #ifdef DEBUG printf("%d %d\n", g->numVertexes, g->numEdges); #endif for(i = 0; i < g->numVertexes; i++) { printf("请输入顶点%d:\n", i); g->vexs[i] = getchar(); while(g->vexs[i] == '\n') { g->vexs[i] = getchar(); } } #ifdef DEBUG for(i = 0; i < g->numVertexes; i++) { printf("%c ", g->vexs[i]); } printf("\n"); #endif for(i = 0; i < g->numEdges; i++) { for(j = 0; j < g->numEdges; j++) { g->arc[i][j] = INFINITY; //邻接矩阵初始化 } } for(k = 0; k < g->numEdges; k++) { charp, q; printf("输入边(vi,vj)上的下标i,下标j和权值:\n"); p = getchar(); while(p == '\n') { p = getchar(); } q = getchar(); while(q == '\n') { q = getchar(); } scanf("%d", &w); intm = -1; intn = -1; m = locates(g, p); n = locates(g, q); if(n == -1 || m == -1) { fprintf(stderr,"there is no this vertex.\n"); return; } //getchar(); g->arc[m][n] = w; g->arc[n][m] = g->arc[m][n]; //因为是无向图,矩阵对称 } } //打印图 voidprintGraph(Graph g) { inti, j; printf("构建的邻接矩阵如下所示.\n"); for(i = 0; i < g.numVertexes; i++) { for(j = 0; j < g.numVertexes; j++) { printf("%5d ", g.arc[i][j]); } printf("\n"); } } //prime算法最小生成树 voidMiniSpanTree_Prime(Graph g) { intmin, i, j, k; intadjvex[MAXVEX]; //保存相关顶点下标 intlowcost[MAXVEX]; //保存相关顶点间边的权值 lowcost[0] = 0; //初始化第一个权值为0,即v0加入生成树 adjvex[0] = 0; //初始化第一个顶点下标为0 for(i = 1; i < g.numVertexes; i++) { //循环除下标为0外的全部顶点 lowcost[i] = g.arc[0][i]; //将v0顶点与之有边的权值存入数组 adjvex[i] = 0; //初始化都为v0下标 } for(i = 1; i < g.numVertexes; i++) { min = INFINITY; //初始化最小权值为无穷大 j = 1; k = 0; while(j < g.numVertexes) //循环全部顶点 { //如果权值不为0,且权值小于min if(lowcost[j] != 0 && lowcost[j] < min) { min = lowcost[j]; //则让当前权值成为最小值 k = j; //将当前最小值的下标存入k } j++; } printf("(%d,%d)", adjvex[k], k); //打印当前顶点边中权值最小边 lowcost[k] = 0; //将当前顶点的权值设置为0,表示此顶点已经完成任务 for(j = 1; j < g.numVertexes; j++)//循环所有顶点 { if(lowcost[j] != 0 && g.arc[k][j] < lowcost[j]) { //若下标为k的顶点各边权值小于此前这些顶点未被加入的生成树权值 lowcost[j] = g.arc[k][j]; adjvex[j] = k; //将下标为k的顶点存入adjvex } } } printf("\n"); } //查找连线顶点的尾部 intFind(int*parent, intf) { while(parent[f] > 0) { f = parent[f]; } returnf; } //直接插入排序 voidInsertSort(Edge edges[], intk) { inti, j; Edge ss; for(i = 1; i <= k; i++) { if(edges[i].weight < edges[i - 1].weight) { ss = edges[i]; for(j = i - 1; edges[j].weight > ss.weight; j--) { edges[j + 1] = edges[j]; } edges[j + 1] = ss; } } } //将邻接矩阵转化为边集数组 voidConvert(Graph g, Edge edges[]) { inti; intj; intk; k = 0; for(i = 0; i < g.numVertexes; i++) { for(j = i; j < g.numVertexes; j++) { if(g.arc[i][j] < 65535) { edges[k].begin = i; edges[k].end = j; edges[k].weight = g.arc[i][j]; k++; } } } k--; #ifdef DEBUG printf("k = %d\n", k); printf("边集数组排序前,如下所示.\n"); printf("edges[] beign end weight\n"); for(i = 0; i < k; i++) { printf("%d", i); printf(" %d", edges[i].begin); printf(" %d", edges[i].end); printf(" %d", edges[i].weight); printf("\n"); } #endif //下面进行排序 InsertSort(edges, k); #ifdef DEBUG printf("边集数组排序后,如下所示.\n"); printf("edges[] beign end weight\n"); for(i = 0; i < k; i++) { printf("%d", i); printf(" %d", edges[i].begin); printf(" %d", edges[i].end); printf(" %d", edges[i].weight); printf("\n"); } #endif } //克鲁斯卡尔算法实现 voidMiniSpanTree_Kruskal(Graph g) { inti, n, m; Edge edges[MAXEDGE]; //定义边集数组 intparent[MAXVEX]; //定义一数组用来判断边与边是否形成环 //此处为将邻接矩阵转化为边集数组edges并按权值由小到大排序 Convert(g, edges); // for(i = 0; i < g.numVertexes; i++) { parent[i] = 0; //初始化数组值为0 } for(i = 0; i < g.numEdges; i++) //循环每一条边 { n = Find(parent, edges[i].begin); m = Find(parent, edges[i].end); if(n != m) //假如n与m不等,说明此边没有与现有生成树形成环路 { parent[n] = m; //将此边的结尾顶点放入下标为起点的parent中 //表示此顶点已经在生成树集合中 printf("(%d,%d) %d ", edges[i].begin, edges[i].end, edges[i].weight); } } printf("\n"); } intmain(intargc, char**argv) { Graph g; //邻接矩阵创建图 CreateGraph(&g); //打印网图 printGraph(g); //普里姆算法求最小生成树 MiniSpanTree_Prime(g); //克鲁斯卡尔算法求最小生成树 MiniSpanTree_Kruskal(g); return0; }
以下图为例,进行相应的测试。
运行结果如下所示。
上述运行过程是这样的:
(1)输入顶点数、边数;
(2)输入顶点,和边(依次为起点、终点、权值);
(3)建立邻接矩阵,用来表示该网图;
(4)进行普里姆算法进行求最小生成树;
(5)进行克鲁斯卡尔进行求最小生成树;
--根据已经建立的邻接矩阵求边集数组;
--然后进行求最小生成树;
克鲁斯卡尔算法的Find函数由边数e决定,时间复杂度为O(loge),而外面有一个for循环e次,所以克鲁斯卡尔算法的时间复杂度为O(eloge)。《此处不包括由邻接矩阵转为边集数组》
对比两个算法,克鲁斯尔算法主要是针对边来展开,边数少时效率会非常高,所以对于稀疏图有很大的优势;而普里姆算法对于稠密图,即边数非常多的情况会更好一些。
暂时弄懂了这两个算法,算是重新复习了一下,以后经常看看,不能再忘记了。
参考:《大话数据结构》、《维基百科》