主要代碼如下:? ? #include
? ? using　namespace　std;
? ? const　int　MAX_EDGE　=　100;
? ? const　int　MAX_NODE　=　100;
? ? /*
? ? 定義一條邊
? ? */
? ? typedef　struct{
? ? int　v;
? ? int　t;
? ? int　weight;
? ? bool　isMST;
? ? }Edge;
? ? /*
? ? 有關算法的一些變量
? ? */
? ? Edge　edges[MAX_EDGE];
? ? int　nodeSet[MAX_EDGE];
? ? const　int　MSTSetNum　=　-1;
? ? int　edgeNum;
? ? bool　nodeIsMST[MAX_NODE];
? ? int　Exchange(Edge　*a,Edge　*b)
? ? {
? ? Edge　t;
? ? t　=　*a;
? ? *a　=　*b;
? ? *b　=　t;
? ? return　0;
? ? }
? ? /*
? ? 實現快速排序算法quick_sort
? ? */
? ? int　partition(Edge*edges,int　p,int　r)
? ? {
? ? int　i　=　p-1,j　=　p;
? ? for(;j
? ? {
? ? if(edges[j].weight　<=　edges[r].weight)
? ? {
? ? i++;
? ? exchange(edges+i,edges+j);
? ? }
? ? }
? ? exchange(&edges[i+1],&edges[r]);
? ? return　i+1;
? ? }
? ? int　quick_sort(Edge　edges[],int　p,int　r)
? ? {
? ? if(p　<　r)
? ? {
? ? int　q　=　partition(edges,p,r);
? ? quick_sort(edges,p,q-1);
? ? quick_sort(edges,q+1,r);
? ? }
? ? return　0;
? ? }
? ? void　Initialize(int　nodeSet[],int　edgeNum);
? ? void　MST_Kruskal(int　n);
? ? void　test();
? ? int　main()
? ? {
? ? test();
? ? return　0;
? ? }
? ? void　Initialize(int　nodeSet[],int　n)
? ? {
? ? if(edgeNum　>　MAX_EDGE)
? ? {
? ? printf("The　total　num　of　edges　must　be　less　than　%d\n",MAX_EDGE);
? ? exit(EXIT_FAILURE);
? ? }
? ? else
? ? {
? ? int　i　=　0;
? ? edgeNum　=　n;
? ? for(;i
? ? {
? ? nodeSet[i]　=　i;
? ? }
? ? }
? ? }
? ? void　MST_Kruskal(int　n)
? ? {
? ? Initialize(nodeSet,n);
? ? quick_sort(edges,0,edgeNum-1);
? ? int　i;
? ? for(i　=　0;i
? ? {
? ? if(nodeSet[edges[i].v]!=nodeSet[edges[i].t])
? ? {
? ? edges[i].isMST　=　true;
? ? if(i==7)
? ? i　=　i;
? ? if(nodeIsMST[edges[i].v]　||　nodeIsMST[edges[i].t])
? ? {
? ? int　j;
? ? for(j　=　0;j<=i;j++)
? ? {
? ? if(edges[j].isMST)
? ? {
? ? if(edges[j].v　==　edges[i].v　||
? ? edges[j].t　==　edges[i].v||
? ? edges[j].v　==　edges[i].t||
? ? edges[j].t　==　edges[i].t)
? ? nodeSet[edges[j].v]　=　nodeSet[edges[j].t]　=　MSTSetNum;
? ? }
? ? }
? ? nodeIsMST[edges[i].v]　=　nodeIsMST[edges[i].t]　=　true;
? ? }
? ? else
? ? {
? ? nodeSet[edges[i].v]　=　nodeSet[edges[i].t];
? ? nodeIsMST[edges[i].v]　=　nodeIsMST[edges[i].t]　=　true;
? ? }
? ? }
? ? }
? ? }
? ? /*
? ? 測試函數
? ? */
? ? void　test()
? ? {
? ? edges[0].v　=　0,edges[0].t　=　1,edges[0].isMST　=　false,edges[0].weight　=　4;
? ? edges[1].v　=　0,edges[1].t　=　8,edges[1].isMST　=　false,edges[1].weight　=　8;
? ? edges[2].v　=　1,edges[2].t　=　2,edges[2].isMST　=　false,edges[2].weight　=　8;
? ? edges[3].v　=　1,edges[3].t　=　7,edges[3].isMST　=　false,edges[3].weight　=　11;
? ? edges[4].v　=　2,edges[4].t　=　8,edges[4].isMST　=　false,edges[4].weight　=　2;
? ? edges[5].v　=　2,edges[5].t　=　5,edges[5].isMST　=　false,edges[5].weight　=　4;
? ? edges[6].v　=　2,edges[6].t　=　3,edges[6].isMST　=　false,edges[6].weight　=　7;
? ? edges[7].v　=　3,edges[7].t　=　4,edges[7].isMST　=　false,edges[7].weight　=　9;
? ? edges[8].v　=　3,edges[8].t　=　5,edges[8].isMST　=　false,edges[8].weight　=　14;
? ? edges[9].v　=　4,edges[9].t　=　5,edges[9].isMST　=　false,edges[9].weight　=　10;
? ? edges[10].v　=　5,edges[10].t　=　6,edges[10].isMST　=　false,edges[10].weight　=　2;
? ? edges[11].v　=　6,edges[11].t　=　7,edges[11].isMST　=　false,edges[11].weight　=　1;
? ? edges[12].v　=　6,edges[12].t　=　8,edges[12].isMST　=　false,edges[12].weight　=　6;
? ? edges[13].v　=　7,edges[13].t　=　8,edges[13].isMST　=　false,edges[13].weight　=　7;
? ? MST_Kruskal(14);
? ? int　i,j;
? ? for(i　=　0,j　=　0;i<14;i++)
? ? {
? ? if(edges[i].isMST)
? ? {
? ? printf("%d.　(%d,%d)-------%d\n",j+1,edges[i].v,edges[i].t,edges[i].weight);
? ? j++;
? ? }
? ? }
? ? }