MST_Kruskal

  2009-03-30 16:54

#include<iostream>
#include<fstream>
using namespace std;
const int MAX = 100;
struct {
       int n;
       int adjvex[MAX];
       int weight[MAX];
}Edge[MAX];
struct Ed{
       int st,ed,key;
};
int father[MAX];
Ed Tree[MAX];
bool operator>=(Ed a,Ed b){
     return a.key>=b.key;
}
int partition(Ed array[],int i,int j){
    Ed k = array[i];
   
    do{
        while((i<j)&&array[j]>=k) j--;
        if(i<j){ array[i] = array[j]; i++;}
       
        while((i<j)&&k>=array[i]) i++;
        if(i<j){ array[j] = array[i]; j--;}
    }while(i!=j);
    array[i] = k;
   
    return i;
}
void quicksort(Ed array[],int i,int j){
     if(i>=j) return;
     int m = partition(array,i,j);
     quicksort(array,i,m-1);
     quicksort(array,m+1,j);
}
void Kruskal(int n);
int main(void){
    int n,e,v,a,b;
    int i,j;
    ifstream in("data.in");
    ofstream out("data.out");
   
    in>>n>>e;
    for(i=1;i<=n;i++)
        Edge[i].n = 0;
   
    for(i=0;i<e;i++){
        in>>a>>b>>v;
        Edge[a].adjvex[ Edge[a].n ] = b;
        Edge[b].adjvex[ Edge[b].n ] = a;
        Edge[a].weight[ Edge[a].n++ ] = Edge[b].weight[ Edge[b].n++ ] = v;
    }
   
    Kruskal(n);
   
    for(i=0;i<n-1;i++)
        out<<Tree[i].st<<" "<<Tree[i].ed<<" "<<Tree[i].key<<endl;
       
    system("pause");
    return 0;
}
void Kruskal(int n){
     Ed List[MAX];
     int Tag[MAX];
     int e,t,i,j,u,v;
    
     e = 0;
     for(i=1;i<=n;i++)
         for(j=0;j<Edge[i].n;j++){
             u = Edge[i].adjvex[j];
             if(u>i){
                List[e].st = i;
                List[e].ed = u;
                List[e++].key = Edge[i].weight[j];
             }
         }
        
     quicksort(List,0,e-1);
    
     memset(father,0,sizeof(father) );
     for(i=1;i<=n;i++)
         Tag[i] = i;
     t = 0;
     for(i=0;i<e;i++){
         u = List[i].st;
         v = List[i].ed;
         if(Tag[u]!=Tag[v]){
            for(j=v;j;j=father[j])
                Tag[j] = Tag[u];
            Tree[t].st = u;
            Tree[t].ed = v;
            Tree[t++].key = List[i].key;
         }
     }
}