本文主要是介绍《大话数据结构》最小生成树——Kruskal算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*2014-6-24思想：n个节点的图中，只需要找到权值最小且不与现有边集合构成环的（n-1）条边，必成最小生成树。方案：将边的权值进行筛选，每次找到权值最小的边，补充道边集合中即可。难点：如何确保这些边不构成环——对每个边，让其起始节点是祖先，通过洄游寻根，如果祖先相同说明两个节点是“近亲”，会构成闭环：A-B-C-A三角形中：1. A-B边中确定B的祖先和父亲都是A；2. B-C边中，确定C的父亲是B，而B的父亲是A，故C的祖先也是A。3. A-C边中，C的祖先是A，A的祖先是A，故此时就能构成闭环。
*/
#include <iostream>
#include <queue>
using namespace std;typedef struct EdgeType{int begin;int end;int weight;
}EdgeType;EdgeType edges[15]={{4,7,7}, {2,8,8}, {0,1,10}, {0,5,11}, {1,8,12},{3,7,16}, {1,6,16}, {5,6,17}, {1,2,18}, {6,7,19},{3,4,20}, {3,8,21}, {2,3,22}, {3,6,24}, {4,5,26}
};int parent[9]={ /*初始化祖先，每个节点开始时刻均无祖先*/-1,-1,-1,-1,-1,-1,-1,-1,-1
};int Find(int parent[],int father){while( parent[father]!=-1 ) /*只要双亲存在，就持续洄游，直到找到祖先*/father=parent[father];return father;}int num=1 ;void Kruskal()
{int i,n,m;for(i=0;i<10;++i){m=Find(parent,edges[i].begin);n=Find(parent,edges[i].end);if(m!=n){parent[n]=m; printf("%d: (%d,%d) %d\n",num++,edges[i].begin,edges[i].end,edges[i].weight);}}}int main(void)
{ cout<<"hello"<<endl;Kruskal();cout<<endl;return 0;
}
这篇关于《大话数据结构》最小生成树——Kruskal算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
