1)克鲁斯卡尔算法
普里姆算法是以某顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树。
克鲁斯卡尔算法是直接以边为目标去构建。
因为权值是在边上，直接去找最小权值的边来构建生成树也是很自然的想法，只不过构建时要考虑是否会形成环路而已。
此时我们用到了图的存储结构中的边集数组结构。
以下是边集数组结构的定义代码：
1 typedef struct 2 { 3 int begin; //边的起点的下标 4 int end; //边的终点的下标 5 int weight; //边的权值 6 }Edge;
本算法所用同普里姆算法的实例，我们直接创建图的边集数组。
并对边的权值从小到大排序后如下图:
重点分析:
克鲁斯卡尔算法主要针对边展开，边数少时效率会很高，所以对于稀疏图有优势
而普利姆算法对于稠密图，即边数非常多的情况会好些。
代码实现如下:
1 #include "stdafx.h" 2 #include<iostream> 3 #include<string> 4 using namespace std; 5 typedef struct MGraph 6 { 7 string vexs[60]; //存放顶点 8 int arcs[100][100]; //存放邻接矩阵矩阵 9 int vexnum, arcum; //总顶点数以及总边数 10 }MGraph; 11 typedef struct 12 { 13 int begin; //边的起点的下标 14 int end; //边的终点的下标 15 int weight; //边的权值 16 }Edge; 17 18 int locateVex(MGraph G, string u) //找到则返回i，否则返回-1 19 { 20 for (int i = 0; i < G.vexnum; i++) 21 if (G.vexs[i] == u) 22 return i; 23 return -1; 24 } 25 26 void CreateGraphUDG(MGraph &G) //构造无向图 27 { 28 string v1, v2; //两个顶点信息 29 int w; //两顶点间边的权值 30 int i, j, k; 31 cout << "请输入顶点数和边数:"; 32 cin >> G.vexnum >> G.arcum; 33 34 cout << "请输入顶点:"; 35 for (i = 0; i < G.vexnum; i++) 36 cin >> G.vexs[i]; 37 38 for (i = 0; i < G.vexnum; i++) //先将邻接矩阵中所有元素都设为无穷大，这里默认10000为无穷大 39 for (j = 0; j < G.vexnum; j++) 40 G.arcs[i][j] = 10000; 41 42 cout << "请输入边和权值:" << endl; 43 for (k = 0; k < G.arcum; k++) 44 { 45 cin >> v1 >> v2 >> w; 46 i = locateVex(G, v1); 47 j = locateVex(G, v2); 48 G.arcs[i][j] = G.arcs[j][i] = w;//关于主对角线对称的元素是相等的 49 } 50 51 } 52 53 int cmp(const void* a, const void* b) 54 { 55 return (*(Edge*)a).weight - (*(Edge*)b).weight; 56 } 57 58 int Find(int *parent, int f) //查找连接顶点的尾部下标 59 { 60 while (parent[f] > 0) 61 f = parent[f]; 62 return f; 63 } 64 65 void MiniSpanTree_Kruskal(MGraph G) 66 { 67 int i, j, n, m; 68 int k = 0; 69 int parent[100]; //用于寻找根节点的数组 70 Edge edges[100]; //定义边集数组,edge的结构为begin,end,weight,均为整型 71 for (i = 0; i < G.vexnum - 1; i++) // 用来构建边集数组并排序(将邻接矩阵的对角线右边的部分存入边集数组中) 72 { 73 for (j = i + 1; j < G.vexnum; j++) 74 { 75 if (G.arcs[i][j] < 10000) 76 { 77 edges[k].begin = i; //编号较小的结点为首 78 edges[k].end = j; //编号较大的结点为尾 79 edges[k].weight = G.arcs[i][j]; 80 k++; 81 } 82 } 83 } 84 qsort(edges, G.arcum, sizeof(Edge), cmp);//为边集数组Edge排序 85 86 for (i = 0; i < G.vexnum; i++) 87 parent[i] = 0; 88 89 cout << "打印最小生成树:" << endl; 90 for (i = 0; i < G.arcum; i++) 91 { 92 n = Find(parent, edges[i].begin); //寻找边edge[i]的“首节点”所在树的树根 93 m = Find(parent, edges[i].end); //寻找边edge[i]的“尾节点”所在树的树根 94 if (n != m) //假如n与m不等，说明两个顶点不在一棵树内，因此这条边的加入不会使已经选择的边集产生回路 95 { 96 parent[n] = m; //将此边的结尾顶点放入下标为起点的parent中，表示此顶点已经在生成树集合中 97 cout << G.vexs[edges[i].begin] << "-" <<G.vexs[ edges[i].end] << " " << edges[i].weight << endl; 98 } 99 } 100 } 101 102 int main() 103 { 104 MGraph G; 105 CreateGraphUDG(G); 106 MiniSpanTree_Kruskal(G); 107 cout << endl; 108 return 0; 109 }
输出结果:
