主要代碼如下: #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;
/*
有關(guān)算法的一些變量
*/
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;
}
/*
實(shí)現(xiàn)快速排序算法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　%dn,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;
}
}
}
}
/*
測(cè)試函數(shù)
*/
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;i14;i++)
{
if(edges[i].isMST)
{
printf(%d.　(%d,%d)-------%dn,j+1,edges[i].v,edges[i].t,edges[i].weight);
j++;
}
}
}

c++相關(guān)文章:c++教程