/*
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;
}