#include "stdafx.h" #include <iostream> #include <stdio.h> #define INF 10000000 using namespace std; //一個undirected graph的adjacency matrix int adjMatrix[8][8] = { {0, 300, 1000, INF, INF, INF, INF, 1700}, {300, 0, 800, INF, INF, INF, INF, INF}, {1000, 800, 0, 1200, INF, INF, INF, INF}, {INF, INF, 1200, 0, 1500, 1000, INF, INF}, {INF, INF, INF, 1500, 0, 250, INF, INF}, {INF, INF, INF, 1000, 250, 0, 900, 1400}, {INF, INF, INF, INF, INF, 900, 0, 1000}, {1700, INF, INF, INF, INF, 1400, 1000, 0}, }; int addedVertices[8] = {0}; int addedVerticesNum = 1; //紀錄成為spanning tree的各邊中其中一點的數目數目。第一個點為0 bool isAdded(int v) { //檢驗這個點是不是已被加入spanning tree的邊中其中一個點 for (int i = 0 ; i < addedVerticesNum; i ++) { if (addedVertices[i] == v) return true; } return false; } //紀錄會成為spanning tree的7條邊。若頂點數目是n則是n-1條邊 struct Edge { int node1; int node2; } edge[7]; int main(int argc, char* argv[]) { int p1, p2; //紀錄被檢驗的邊的兩點 int lowestWeight; //在下面的三層迴圈中,暫存與已被加入spanning tree的邊相連的邊中,weight最低的 int thep1, thep2; //紀錄這一次要被加入minimum cost spanning tree的邊的兩個頂點 for (int i = 0 ; i < 8 ; i ++) { lowestWeight = INF; for (int count = 0; count < addedVerticesNum; count++) { //從幾個已被加的點開始找 p1 = addedVertices[count]; for (p2 = 0; p2 < 8 ; p2++) { if ( p2 != p1 && adjMatrix[p1][p2] < lowestWeight && !isAdded(p2) ) { //這個要被加入spanninf tree的邊的兩個點不同,所以 p2 != p1 //兩個點之間須有邊相連,所以 adjMatrix[p1][p2] < INF。 //adjMatrix[p1][p2] < lowestWeight則是為了找出權重最低的邊 //在加一條新的邊時,依prim的演算法必須一點是已被加入spanning tree的邊中的其中一點,另一點不是。 //而p1 = addedVertices[count] 和 !isAdded(p2)代表p1是其中一點,p2不是 lowestWeight = adjMatrix[p1][p2]; thep1 = p1; thep2 = p2; } } } if (lowestWeight < INF) { edge[addedVerticesNum - 1].node1 = thep1; edge[addedVerticesNum - 1].node2 = thep2; //thep1是新加入spanning tree的邊中,已和其中一條被加入spanning tree的邊相連的點, //thep2則是尚未與被加入spanning tree的邊相連的另一點 addedVertices[addedVerticesNum] = thep2; addedVerticesNum++; } else //若lowestWeight = INF,表示p1未與其他任何點相連,所以整個圖必定沒有spanning tree break; } if (addedVerticesNum < 8 ) cout << "No spanning tree\n"; else { cout << "The edges of the spanning tree are:\n"; for (int i = 0 ; i < 7; i++ ) cout << "edge " << edge[i].node1 << edge[i].node2 << endl; } //以文章最上面的圖為例,就會輸出 //the edges of the spanning tree are: //edge 01 //edge 12 //edge 23 //edge 35 //edge 54 //edge 56 //edge 67 system("PAUSE"); return 0; }
This blog contains posts regarding my practice in programming. The posts are about questions in Yahoo Knowledge or some program design ideas or implementation of algorithms.
Sunday, January 8, 2012
以Prim's Algorithm來求最小成本擴張樹
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment