bingchaji_kruskal.txt

基于并查集的求最小生成树的Kruskal算法的实现

#include <cstdlib>
#include <iostream>

using namespace std;
#define MAXN 1000
#define NUM 1000*1000
#define inf 1<<30  //31 is overflowing
int P[MAXN];
int rank[MAXN];
void Make_set(int x)
{
    P[x] = x;
    rank[x] = 0; //合并两集合的一个启发函数值 
}
int Find_set(int x)
{
    if(x != P[x]) P[x] = Find_set(P[x]);
    return P[x];
}
void Link_set(int x,int y)
{
    if(rank[x] > rank[y]) P[y] = x;
    else P[x] = y;
    if(rank[x] == rank[y]) rank[y]++;
         
}
void Union_set(int x,int y)
{
   Link_set(Find_set(x),Find_set(y));     
}

/////基于并查集的求最小生成树的Kruskal算法的实现
////if (u,v) is not exist,G[u][v] = inf
////if u has been added in set of the smallest tree,then G[u][u] = 1;
int e[MAXN][MAXN]; 
struct Tree{
       int u;
       int v;
       int value;
       };
Tree tree[NUM];
int count_n = 0;
void st_Kruskal(int n)
{
   int i = 0,j = 0;
   for(i = 0;i < n;i++)
   {
        Make_set(i);        
   }
   int u = 0,v = 0;
   count_n = 0;
   while(1)
   {
       int min = inf;
       for(i = 0;i < n;i++)
       {
          for(j = 0;j < n;j++)
          {
              if(i != j && e[i][j] < min) 
              {
                  min = e[i][j]; 
                  u = i,v = j;        
              }     
          }      
       } 
       if(min == inf) break;
       if(Find_set(u) != Find_set(v)) 
       {
           tree[count_n].u = u;
           tree[count_n].v  = v;
           tree[count_n].value = e[u][v];
           Union_set(u,v);   
           e[u][u] = e[v][v] = 1;    
           count_n++;       
       }  
       e[u][v] = inf;     
   }
   
   
}
int main()
{
   int n = 0,i = 0,j = 0;
   while(cin>>n)
   {
       for(i = 0;i < n;i++)
       {
           for(j = 0;j < n;j++)   
            { 
                cin>>e[i][j];
                if(e[i][j] == -1) e[i][j] = inf;
            }          
       }
       st_Kruskal(n); 
       for(i = 0;i < count_n;i++) 
       {
                cout<<tree[i].u<<"   "<<tree[i].v<<"   "<<tree[i].value<<endl;      
       } 
   }
   return 0;    
}


test:
6
0 6 2 -1 -1 -1
6 0 1 11 -1 -1
2 1 0 9 13 -1
-1 11 9 0 3 4
-1 -1 13 3 0 4
-1 -1 -1 4 4 0
result:
1   2   1
0   2   2
3   4   3
3   5   4
2   3   9