|
主要代碼如下: #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++; } } } |
