《大话数据结构》最小生成树——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;
}