最小生成ツリー-kruskyal

kruskyal(クルースカル) アルゴリズムと前の primアルゴリズムは、最小の生成ツリーを求めるアルゴリズムであり、primは最適化されていない場合、時間の複雑さはO(n^2)kruskyalの時間複雑さは、使用する順序付けアルゴリズムと関連しています.二つの違いはもう一つあります.prm.
アルゴリズム ポイント単位で反復の思想を採用して、一番小さいツリーを段階的に生成します. セットの思想と操作を利用して最小のツリーを生成します.
      簡単にKruskyalアルゴリズムを紹介します.まず、すべての辺を並べ替えて(増分順)、最小の辺から始めます.この辺を最小の生成ツリーのセットに入れると、回路が発生しなくなります.n-1条の端に入れて終わります.
      特に注意が必要なのは最後に判断して、いくつかの連通集があるかを調べることです.一つ以上の場合、最小生成ツリーがないということです.
       実現コード:

//kruskal   
#include
#include
#include
#define MAXN 100
typedef struct{  //           
	int a;
	int b;
	int value;
}edge;

int pre[MAXN];  //   

int find(int a) //            
{
	if (pre[a] == a)
	return a;
	else return pre[a] = find(pre[a]); //    
}

void join(int a,int b){ //            
	int fa = find(a);
	int fb = find(b);
	if (fa == fb)
	return ;
	pre[fa] = fb;
}
void init() //      
{
	int i;
	for (i=0;ivalue;
	int vb = ((pedge)b)->value;
	return va - vb;
}
void kruskal (int n,int m){  //kruscal   
	int i, start, end, value, sum = 0,flag = 0; // i      ，start   end          ，value      ，sum              ，flag               ；
	edge edges[MAXN]; //          
	init(); //       
	for (i=0;i 1)
	printf("-1
");
	else
	printf("%d
",sum); 
	
}
int main (){
	int n, m;
	scanf("%d%d",&n,&m);
    kruskal(n,m);
}