主要代碼如下: #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 %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;
}
}
}
}
/*
測試函數
*/
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)-------%dn",j+1,edges[i].v,edges[i].t,edges[i].weight);
j++;
}
}
}
