算法研究：图解最小生成树之克鲁斯卡尔算法

算法研究：图解最小生成树之克鲁斯卡尔算法2013-08-21 csdn Simba888888我们在前面讲过的《克里姆算法》是以某个顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树的。同样的思路，我们也可以直接就以边为目标去构建，因为权值为边上，直接找最小权值的边来构建生成树也是很自然的想法，只不过构建时要考虑是否会形成环而已，此时我们就用到了图的存储结构中的边集数组结构，如图7-6-7

假设现在我们已经通过邻接矩阵得到了边集数组edges并按权值从小到大排列如上图。

下面我们对着程序和每一步循环的图示来看：

算法代码：

typedef struct{int begin;int end;int weight;} Edge;/* 查找连线顶点的尾部下标 */int Find（int *parent, int f）{while （parent[f] > 0）f = parent[f];return f;}/* 生成最小生成树 */void MiniSpanTree_Kruskal（MGraph G）{int i, j, n , m;int k = 0;int parent[MAXVEX];/* 定义一数组用来判断边与边是否形成环路 */Edge edges[MAXEDGE];/* 定义边集数组,edge的结构为begin,end,weight,均为整型 *//* 此处省略将邻接矩阵G转换为边集数组edges并按权由小到大排列的代码*/for （i = 0; i < G.numVertexes; i++）parent[i] = 0;cout << "打印最小生成树：" << endl;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中。 *//* 表示此顶点已经在生成树集合中 */cout << "（" << edges[i].begin << ", " << edges[i].end << "） " << edges[i].weight << endl;}}}