貪心Kruskal算法生成樹C實現代碼

    #include <iostream.h>


#define Max 100  

typedef struct{  
         int u;  
         int v;  
         int weight;  
}edge;  
edge edges[Max];  
int nodes[Max];  
void interchange(edge* m,edge* n)  
{  
    edge temp=*m;  
    *m=*n;  
    *n=temp;  

}  
int partition(edge array[],int p,int q)  
{  
    int i,j;  
    i=p;  
    j=q+1;  
    while(1)  
    {  
        do i++;  
        while((array[i].weight<array[p].weight)&&(i!=q));  
        do j--;  
        while((array[j].weight>array[p].weight)&&(j!=p));  
        if(i<j)  
            interchange(&array[i],&array[j]);  
        else  
            break;  
    }  
    interchange(&array[p],&array[j]);  
    return j;  

}  
void quicksort(edge array[],int p,int q)  
{  
    int j;  
    if (p<q)  
    {  
        j=partition(array,p,q);  
        quicksort(array,p,j-1);  
        quicksort(array,j+1,q);  
    }  
}  
void main()  
{  
        int i,j,m, n, nodenum, edgenum,safe,cost=0,flag=1 ;  
        int presult = 0;  

        cout<<"Input the number of nodes and edges:";  
        cin>>nodenum>>edgenum;  
        cout<<"請輸入每條邊的起點、終點及權值："<<endl;  
        for(i = 0; i < edgenum; i++)  
        {  
             cin>>edges[i].u>>edges[i].v>>edges[i].weight;  

        }  
        for(i=1;i<=nodenum;i++)  
            nodes[i]=0;  
        quicksort(edges,0,edgenum-1);  
        for(i = 0; i < edgenum ; i++)  
        {                 
                m = edges[i].u;  
                n = edges[i].v;  
                safe = 0;  
                if(nodes[m] == 0 &&nodes[n] == 0){  
                        nodes[m] = flag;  
                         nodes[n] =flag;  
                         flag++;  
                        safe = 1;//a safe edge  

                }  
                else  
                {  
                    if(nodes[m] == 0 ||nodes[n] == 0 )  
                    {  
                        if(nodes[m] == 0 )                          
                            nodes[m] = nodes[n];  
                        else nodes[n]=nodes[m];  

                        safe = 1;//a safe edge  
                    }  
                    else   
                        if(nodes[m] != nodes[n])  
                        {                     
                              for(j = 1; j <= nodenum; j++)  
                              {  
                                if((nodes[j] == nodes[m] || nodes[j] == nodes[n])&&(j!=m&&j!=n))  
                                {  
                                        nodes[j] = flag;  
                                }  
                              }    
                              nodes[m]=flag;  
                              nodes[n]=flag;  
                              flag++;                            
                              safe = 1;//a safe edge  

                        }  

                }  

                if(safe == 1){//reserve a safe edge  

                        edges[presult].u = m;  
                        edges[presult].v = n;  
                        edges[presult].weight = edges[i].weight;  
                        presult++;  
                }  

              if(presult == nodenum-1 ){//found mst  

                        break;  
                }   
        }  
        cout<<"Print the result:"<<endl;  
        cout<<"起點   終點   權值"<<endl;  
                for(i = 0; i < presult; i++)  
                {  
                    cost=cost+edges[i].weight;  
                    cout<<edges[i].u<<"       "<< edges[i].v<<"         "<< edges[i].weight<<endl;  
                }  
                cout<<"最小生成樹的權值為："<<cost<<endl;  

}  </pre>