Kruskalアルゴリズムシミュレーションの説明

Kruskalアルゴリズムは最小生成ツリーを求めるアルゴリズムであり,すなわち最小のオーバーヘッドを求めるなどである.
アルゴリズムは、最小生成ツリーを要求すると、n個のノードはn−1個のエッジしか含まない
だから私たちはこの最も短いn-1辺を探すことに変換すべきで、そのため、まずすべての
小さいものから大きいものまで並べ替えながら、1本ずつ取り出して試してみて、リングになるかどうか見てみましょう.
リングを構成しなければ、最短の経路に違いない.毎回最小をとるからだ.
のエッジを探して、最終的に最小の生成ツリーの代価とを求めることができます.
 

/*

	Filename:kruskal.cpp

	Author: xiaobing

	E-mail: [email protected]

	Date: 2013-08-31

*/

#include<iostream>

#include<string>

#include<string.h>

#include<algorithm>

#include<cstdlib>

#include<list>

#include<set>

#include<vector>

#define N 100

#define INF 1000000

using namespace std;



/*

 Kruskal               ，        

       ，        ，  n       n-1  

                n-1  ，  ，       

          ，            ，      ，

       ，           ，         

      ，               。

	       ：

		struct edge      ，          

		edge graph[N]    N      

		int father[N]              

	  ：              ，    ，     

	 ，                   ，      

	    ，               ，       

	 ，  ，        father[N],   ，    -1, 

	           (           )，     

	  ，          ，              

	    ， x > y   father[x] = y,           ，

	     ， -1,         ，        ，  

	   ，   ，             ，       

	  。

   

 */



//     

struct edge{

	int u;		//   

	int v;		//   

	int cost;	//       

};



//                    

bool cmp(const edge &a, const edge &b){

	return a.cost < b.cost;

}



//          

int findFather(int father[], int x){

	//         -1,     ，        

	if(father[x] != -1){

		//                 

		return father[x] = findFather(father, father[x]);

	}



	//  -1,      

	return x;

}



//     

bool unionEdge(int father[], int x, int y){

	//              

	x = findFather(father, x);

	y = findFather(father, y);



	//     ，       ，     

	//      ，    ，  fasle

	if(x == y){

		return false;

	}



	//   ，               

	if(x > y)	father[x] = y;

	if(x < y)	father[y] = x;



	//      ，  true

	return true;

}



int main(){

	edge graph[N];		//       N    

	int father[N];		//       N       

	int i,j, n;	//n     

	cin>>n;

	//     

	memset(graph, 0, sizeof(graph));

	//    -1           ，         

	memset(father, -1, sizeof(father));



	int k = 0, cost, temp;



	//    

	for(i = 0;i < n;i++)

		for(j = 0;j < n;j++){

			if(i > j){

				graph[k].u = i;

				graph[k].v = j;

				cin>>cost;

				//    0  ，     ，        INF

				if(cost < 0){

					graph[k].cost = INF;

				} else {

					graph[k].cost = cost;

				}

				k++;

				continue;

			}

			//      ，    ，    

			cin>>temp;

		}



	//          

	sort(graph, graph + k, cmp);



	//       

	for(i = 0;i < k;i++){

		cout<<i<<" "<<graph[i].u<<"->"<<graph[i].v<<": "<<graph[i].cost<<endl;

	}



	//count          ， n-1   

	//sum          

	int count = 0, sum = 0;



	//      k  

	for(i = 0; i < k;i++){

		//         

		if(unionEdge(father, graph[i].u, graph[i].v)){

			count++;

			sum += graph[i].cost;

		}



		//   n-1   ，      ，   

		if(count == n - 1)	break;

	}





	cout<<"        sum : "<<sum<<endl;



    return 0;

}

テスト例:
 
 

7

0 5 -1 -1 -1 11 2

5 0 10 8 -1 -1 13

-1 10 0 7 -1 -1 -1

-1 8 7 0 12 9 4

-1 -1 -1 12 0 10 -1

11 -1 -1 9 10 0 3

2 13 -1 4 -1 3 0

結果:
 
 

0 6->0: 2

1 6->5: 3

2 6->3: 4

3 1->0: 5

4 3->2: 7

5 3->1: 8

6 5->3: 9

7 2->1: 10

8 5->4: 10

9 5->0: 11

10 4->3: 12

11 6->1: 13

12 2->0: 1000000

13 6->4: 1000000

14 6->2: 1000000

15 3->0: 1000000

16 5->2: 1000000

17 5->1: 1000000

18 4->2: 1000000

19 4->1: 1000000

20 4->0: 1000000

        sum : 31