贪心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;  
                     
    }  

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。