数据结构之最小生成树

    一个连通图的生成树是一个极小的连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。那么我们把构造连通网的最小代价生成树称为最小生成树。    找连通网的最小生成树，经典的有两种算法，普里姆算法和克鲁斯卡尔算法。下面分别介绍两种算法。一、普里姆（Prim）算法    普里姆算法，图论中的一种算法，可在加权连通图里搜索最小生成树。意即此算法搜索到的边子集所构成的树中，不但包括连通图里的所有顶点，且其所有边的权值之和亦为最小。1.1 算法描述    从单一顶点开始，普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。    （1）输入：一个加权连通图，其中顶点集合为V，边集合为E；    （2）初始化：V = {x}，其中x为集合V中的任一节点（起始点），E = {}；    （3）重复下列操作，直到V = V：            在集合E中选取权值最小的边（u, v），其中u为集合V中的元素，而v则不是（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；            将v加入集合V中，将（u, v）加入集合E中；    （4）输出：使用集合V和E来描述所得到的最小生成树。1.2 例示            1.3 普里姆算法实现/* 邻接矩阵表示的图结构*/#include#include#includetypedef char VertexType;//顶点类型应由用户定义typedef int EdgeType;//边上的权值类型应由用户定义#define MAXVEX100//最大顶点数，应由用户定义#define INFINITY65535//用65535来代表无穷大#define DEBUG//邻接矩阵结构typedef struct{VertexType vexs[MAXVEX];//顶点表EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵，可看作边int numVertexes, numEdges;//图中当前的顶点数和边数}Graph;//定位int locates(Graph *g, char ch){int i = 0;for(i = 0; i numVertexes; i++){if(g->vexs[i] == ch){break;}}if(i >= g->numVertexes){return -1;}return i;}//建立一个无向网图的邻接矩阵表示void CreateGraph(Graph *g){int i, j, k, w;printf("输入顶点数和边数:\n");scanf("%d,%d", &(g->numVertexes), &(g->numEdges));#ifdef DEBUGprintf("%d %d\n", g->numVertexes, g->numEdges);#endiffor(i = 0; i numVertexes; i++){printf("请输入顶点%d:\n", i);g->vexs[i] = getchar();while(g->vexs[i] == '\n'){g->vexs[i] = getchar();}}#ifdef DEBUGfor(i = 0; i numVertexes; i++){printf("%c ", g->vexs[i]);}printf("\n");#endiffor(i = 0; i numEdges; i++){for(j = 0; j numEdges; j++){g->arc[i][j] = INFINITY;//邻接矩阵初始化}}for(k = 0; k numEdges; k++){char p, q;printf("输入边(vi,vj)上的下标i，下标j和权值:\n");p = getchar();while(p == '\n'){p = getchar();}q = getchar();while(q == '\n'){q = getchar();}scanf("%d", &w);int m = -1;int n = -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];//因为是无向图，矩阵对称}}//打印图void printGraph(Graph g){int i, j;printf("构建的邻接矩阵如下所示.\n");for(i = 0; i     运行结果如下：                由代码实现可知，邻接矩阵实现的普里姆算法的时间复杂度为O(n2)。二、克鲁斯卡尔（Kruskal）算法    普力马算法是以某顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树的。同样的思路，我们也可以直接就以边来构建生成树也是很自然的想法，只不过构建时要考虑是否会形成环路而已。此时，我们就用到了图的存储结构中的边集数组结构。以下是edge边集数组结构的定义代码： //对边集数组Edge结构的定义 typedef struct { int begin; int end; int weight; }Edge;     我们可以通过程序将邻接矩阵通过程序转化为边集数组，并且对它们的按权值从小到大排序。如下图所示。        于是克鲁斯卡尔算法代码如下，左侧数字为行号。其中MAXEDGE为边数量的最大值，MAXVEX为顶点个数最大值。具体代码如下所示。/* 邻接矩阵表示的图结构*/#include#includetypedef char VertexType;//顶点类型应由用户定义typedef int EdgeType;//边上的权值类型应由用户定义#define MAXVEX100//最大顶点数，应由用户定义#define INFINITY65535//用65535来代表无穷大#define DEBUG//邻接矩阵结构typedef struct{VertexType vexs[MAXVEX];//顶点表EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵，可看作边int numVertexes, numEdges;//图中当前的顶点数和边数}Graph;//边集数组#define MAXEDGE 100typedef struct{int begin;int end;int weight;}Edge;//定位int locates(Graph *g, char ch){int i = 0;for(i = 0; i numVertexes; i++){if(g->vexs[i] == ch){break;}}if(i >= g->numVertexes){return -1;}return i;}//建立一个无向网图的邻接矩阵表示void CreateGraph(Graph *g){int i, j, k, w;printf("输入顶点数和边数:\n");scanf("%d,%d", &(g->numVertexes), &(g->numEdges));#ifdef DEBUGprintf("%d %d\n", g->numVertexes, g->numEdges);#endiffor(i = 0; i numVertexes; i++){printf("请输入顶点%d:\n", i);g->vexs[i] = getchar();while(g->vexs[i] == '\n'){g->vexs[i] = getchar();}}#ifdef DEBUGfor(i = 0; i numVertexes; i++){printf("%c ", g->vexs[i]);}printf("\n");#endiffor(i = 0; i numEdges; i++){for(j = 0; j numEdges; j++){g->arc[i][j] = INFINITY;//邻接矩阵初始化}}for(k = 0; k numEdges; k++){char p, q;printf("输入边(vi,vj)上的下标i，下标j和权值:\n");p = getchar();while(p == '\n'){p = getchar();}q = getchar();while(q == '\n'){q = getchar();}scanf("%d", &w);int m = -1;int n = -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];//因为是无向图，矩阵对称}}//打印图void printGraph(Graph g){int i, j;printf("构建的邻接矩阵如下所示.\n");for(i = 0; i 0){f = parent[f];}return f;}//直接插入排序void InsertSort(Edge edges[], int k){int i, j;Edge ss;for(i = 1; i ss.weight; j--){edges[j + 1] = edges[j];}edges[j + 1] = ss;}}}//将邻接矩阵转化为边集数组void Convert(Graph g, Edge edges[]){int i;int j;int k;k = 0;for(i = 0; i     以下图为例，进行相应的测试。        运行结果如下所示。                        上述运行过程是这样的：    （1）输入顶点数、边数；    （2）输入顶点，和边（依次为起点、终点、权值）；    （3）建立邻接矩阵，用来表示该网图；    （4）进行普里姆算法进行求最小生成树；    （5）进行克鲁斯卡尔进行求最小生成树；            --根据已经建立的邻接矩阵求边集数组；            --然后进行求最小生成树；            克鲁斯卡尔算法的Find函数由边数e决定，时间复杂度为O(loge)，而外面有一个for循环e次，所以克鲁斯卡尔算法的时间复杂度为O(eloge)。《此处不包括由邻接矩阵转为边集数组》        对比两个算法，克鲁斯尔算法主要是针对边来展开，边数少时效率会非常高，所以对于稀疏图有很大的优势；而普里姆算法对于稠密图，即边数非常多的情况会更好一些。        暂时弄懂了这两个算法，算是重新复习了一下，以后经常看看，不能再忘记了。    参考：《大话数据结构》、《维基百科》                                                                                                  梦醒潇湘love                                                                                                         2013-01-29 22:43