// algo7-5.cpp 克魯斯卡爾算法求無向連通網(wǎng)的最小生成樹的程序
 #include"c1.h"
 #include"func7-1.cpp" // 包括頂點(diǎn)信息類型的定義及對它的操作
 #include"func7-2.cpp" // 包括弧(邊)的相關(guān)信息類型的定義及對它的操作
 #include"c7-1.h" // 圖的數(shù)組(鄰接矩陣)存儲(chǔ)結(jié)構(gòu)
 #include"bo7-1.cpp" // 圖的數(shù)組(鄰接矩陣)存儲(chǔ)結(jié)構(gòu)的基本操作
 struct side // 圖的邊信息存儲(chǔ)結(jié)構(gòu)
 { int a,b; // 邊的2頂點(diǎn)的序號(hào)
   VRType weight; // 邊的權(quán)值
 };
 void Kruskal(MGraph G)
 { // 克魯斯卡爾算法求無向連通網(wǎng)G的最小生成樹
   int set[MAX_VERTEX_NUM],senumber=0,sb,i,j,k;
   side se[MAX_VERTEX_NUM*(MAX_VERTEX_NUM-1)/2]; // 存儲(chǔ)邊信息的一維數(shù)組
   for(i=0;i<G.vexnum;++i) // 查找所有的邊，并根據(jù)權(quán)值升序插到se中
     for(j=i+1;j<G.vexnum;++j) // 無向網(wǎng)，只在上三角查找
       if(G.arcs[i][j].adj<INFINITY) // 頂點(diǎn)[i][j]之間有邊
       { k=senumber-1; // k指向se的最后一條邊
         while(k>=0) // k仍指向se的邊
           if(se[k].weight>G.arcs[i][j].adj)
           { // k所指邊的權(quán)值大于剛找到的邊的權(quán)值
             se[k+1]=se[k]; // k所指的邊向后移
             k--; // k指向前一條邊
           }
           else // k所指邊的權(quán)值不大于剛找到的邊的權(quán)值
             break; // 跳出while循環(huán)
         se[k+1].a=i; // 將剛找到的邊的信息按權(quán)值升序插入se
         se[k+1].b=j;
         se[k+1].weight=G.arcs[i][j].adj;
         senumber++; // se的邊數(shù)+1
       }
   printf("i se[i].a se[i].b se[i].weight\n");
   for(i=0;i<senumber;i++)
     printf("%d %4d %7d %9d\n",i,se[i].a,se[i].b,se[i].weight);
   for(i=0;i<G.vexnum;i++) // 對于所有頂點(diǎn)
     set[i]=i; // 設(shè)置初態(tài)，各頂點(diǎn)分別屬于各個(gè)集合
   printf("最小代價(jià)生成樹的各條邊為\n");
   j=0; // j指示se當(dāng)前要并入最小生成樹的邊的序號(hào)，初值為0
   k=0; // k指示當(dāng)前構(gòu)成最小生成樹的邊數(shù)
   while(k<G.vexnum-1) // 最小生成樹應(yīng)有G.vexnum-1條邊
   { if(set[se[j].a]!=set[se[j].b]) // j所指邊的2頂點(diǎn)不屬于同一個(gè)集合
     { printf("(%s-%s)\n",G.vexs[se[j].a].name,G.vexs[se[j].b].name); // 輸出該邊
       sb=set[se[j].b]; // 將該邊的頂點(diǎn)se[j].b當(dāng)前所在的集合賦給sb
       for(i=0;i<G.vexnum;i++) // 對于所有頂點(diǎn)
         if(set[i]==sb) // 與頂點(diǎn)se[j].b在同一個(gè)集合中
           set[i]=set[se[j].a]; // 將此頂點(diǎn)并入頂點(diǎn)se[j].a所在的集合中
       k++; // 當(dāng)前構(gòu)成最小生成樹的邊數(shù)+1
     }
     j++; // j指示se下一條要并入最小生成樹的邊的序號(hào)
   }
 }

 void main()
 {
   MGraph g;
   char filename[13]; // 存儲(chǔ)數(shù)據(jù)文件名(包括路徑)
   printf("請輸入數(shù)據(jù)文件名：");
   scanf("%s",filename);
   CreateFromFile(g,filename,0); // 創(chuàng)建無相關(guān)信息的網(wǎng)
   Display(g); // 輸出無向網(wǎng)g
   Kruskal(g); // 用克魯斯卡爾算法輸出g的最小生成樹的各條邊
 }