データ構造−グラフ構造−最小生成木問題−道路村村通(PrimeアルゴリズムとKruskalアルゴリズム)

テーマ:既存の集落間道路の統計データ表には、標準道路に建設される可能性のあるいくつかの道路のコストがリストされており、各集落に道路を連通させるために必要な最低コストが求められている.
入力フォーマット:入力データは都市数の正の整数N(≦1000)と候補道路数M(≦3 N)を含む.その後のM行はM道路に対応し、各行には3つの正の整数が与えられ、それぞれこの道路が直接連通する2つの都市の番号とこの道路の改修の予算コストである.簡単にするために、町は1からN番までです.
出力フォーマット:村村通に必要な最低コストを出力します.入力データが十分でない場合は−1を出力し,より多くの道路を建設する必要があることを示した.
サンプルを入力:

6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3

出力サンプル:

12

この問題は主に最小生成ツリーアルゴリズム(PrimeアルゴリズムとKruskalアルゴリズム)

を考査する.
解決コード

#include
#include
#define MAXN 1001  // 1  
#define INF 100000
int Map[MAXN][MAXN],Cost[MAXN],N,M;
int parent[MAXN];  //           
typedef struct Edge  //   
{
   int V;
   int W;
   int Cost;
}Edge;
Edge *E;
void CreateGraph(int n, int e)  //      
{
   int v,w,i;
   for(v=1;v<=n;v++)
   {
       Cost[v]=0;    //              （  ）
       for(w=1;w<=n;w++) 
       {
           if(v==w)
              Map[v][w]=0;  //        
           else 
              Map[v][w]=INF;
       }
   }
   E=(Edge*)malloc(sizeof(struct Edge)*e);  //         
   for(i=0;i<e;i++)
   {
       scanf("%d %d %d",&E[i].V,&E[i].W,&E[i].Cost); //   
       Map[E[i].V][E[i].W]=E[i].Cost;  //        
       Map[E[i].W][E[i].V]=E[i].Cost;
   }
}
/*************************************Prime  ******************************************/
int FindMinCost()  //     
{
    int i,MinCost,MinCostPosition;
    MinCost=INF;
    MinCostPosition=0;
    for(i=1;i<=N;i++)
    {
       if(Cost[i] && Cost[i]<MinCost)  //       0，   
       {
           MinCost=Cost[i];
           MinCostPosition=i;
       }
    }
    return MinCostPosition;
}
int Prime()
{
    int i,GrossCost=0,MinCost,Count=0;
    for(i=1;i<=N;i++)Cost[i]=Map[1][i];   //  1          
    while(1)
    {
        MinCost=FindMinCost();
        if(MinCost==0)break;      //        
        else  //      ，       
        {
            GrossCost+=Cost[MinCost];  //     
            Count++;  //     
            Cost[MinCost]=0;
        for(i=2;i<=N;i++)
        {
            if(Cost[i] && Cost[i]>Map[MinCost][i])  //       0，                      
            {
               Cost[i]=Map[MinCost][i];  //      
            }
        }
        }
    }
    if(Count<N-1)return -1;
    else return GrossCost;
}
/*************************************Kruskal  ******************************************/
void Shell_Sort()  //    
{
    int Si, D, P, i;
    Edge Tmp;
    int Sedgewick[] = {3905,2161,929, 505, 209, 109, 41, 19, 5, 1, 0};
    for ( Si=0; Sedgewick[Si]>=M; Si++ ) ; 
    for ( D=Sedgewick[Si]; D>0; D=Sedgewick[++Si] )
        for ( P=D; P<M; P++ )  //    
        {
            Tmp = E[P];
            for ( i=P; i>=D && E[i-D].Cost >Tmp.Cost ; i-=D )
                E[i] = E[i-D] ;
            E[i] = Tmp;
        }
}
int FindParent(int v)  //    
{
    if(parent[v]==v) return v;
    else return FindParent(parent[v]);
}
int Associate(int v,int w)  //    
{
    int root1,root2;
    root1=FindParent(v);  //    
    root2=FindParent(w);  //    
    if(root1!=root2)  //       
    {
       parent[root2]=root1;  //      
       return 1;
    }
    return 0;
}
int Kruskal()
{
    int i,GrossCost=0,Count=0;
    Shell_Sort();  //      
    for(i=1;i<=N;i++)parent[i]=i;   //                
    for(i=0;i<M;i++)
    {
       if(Associate(FindParent(E[i].V ),FindParent(E[i].W )))
       {
           Count++;  //  +1
           GrossCost+=E[i].Cost;  //     
       }
       if(Count==N-1)break;  // N-1     
 }
    if(Count<N-1) return -1;  //    
    else return GrossCost;
}
int main()
{
    scanf("%d%d",&N,&M);
    CreateGraph(N,M);
    //printf("%d
",Prime());
    printf("%d
",Kruskal());
    return 0;
}