普裡姆算法介紹 普裡姆(Prim)算法，是用來求加權連通圖的最小生成樹的算法。 基本思想 對於圖G而言，V是所有頂點的集合；現在，設置兩個新的集合U和T，其中U用於存放G的最小生成樹中的頂點，T存放G的最小生成樹中的邊。 從所有uЄU，vЄ(V-U) (V-U表示出去U的所有頂點)的邊中選取權值最小的邊(u, v)，將頂點v加入集合U中，將邊(u, v)加入集合T中，如此不斷重復，直到U=V為止，最小生成樹構造完畢，這時集合T中包含了最小生成樹中的所有邊。 普裡姆算法圖解 以上圖G4為例，來對普裡姆進行演示(從第一個頂點A開始通過普裡姆算法生成最小生成樹)。 初始狀態：V是所有頂點的集合，即V={A,B,C,D,E,F,G}；U和T都是空！ 第1步：將頂點A加入到U中。 此時，U={A}。 第2步：將頂點B加入到U中。 上一步操作之後，U={A}, V-U={B,C,D,E,F,G}；因此，邊(A,B)的權值最小。將頂點B添加到U中；此時，U={A,B}。 第3步：將頂點F加入到U中。 上一步操作之後，U={A,B}, V-U={C,D,E,F,G}；因此，邊(B,F)的權值最小。將頂點F添加到U中；此時，U={A,B,F}。 第4步：將頂點E加入到U中。 上一步操作之後，U={A,B,F}, V-U={C,D,E,G}；因此，邊(F,E)的權值最小。將頂點E添加到U中；此時，U={A,B,F,E}。 第5步：將頂點D加入到U中。 上一步操作之後，U={A,B,F,E}, V-U={C,D,G}；因此，邊(E,D)的權值最小。將頂點D添加到U中；此時，U={A,B,F,E,D}。 第6步：將頂點C加入到U中。 上一步操作之後，U={A,B,F,E,D}, V-U={C,G}；因此，邊(D,C)的權值最小。將頂點C添加到U中；此時，U={A,B,F,E,D,C}。 第7步：將頂點G加入到U中。 上一步操作之後，U={A,B,F,E,D,C}, V-U={G}；因此，邊(F,G)的權值最小。將頂點G添加到U中；此時，U=V。 此時，最小生成樹構造完成！它包括的頂點依次是：A B F E D C G。 普裡姆算法的代碼說明 以"鄰接矩陣"為例對普裡姆算法進行說明，對於"鄰接表"實現的圖在後面會給出相應的源碼。 1. 基本定義 復制代碼 class MatrixUDG { #define MAX 100 #define INF (~(0x1<<31)) // 無窮大(即0X7FFFFFFF) private: char mVexs[MAX]; // 頂點集合 int mVexNum; // 頂點數 int mEdgNum; // 邊數 int mMatrix[MAX][MAX]; // 鄰接矩陣 public: // 創建圖(自己輸入數據) MatrixUDG(); // 創建圖(用已提供的矩陣) //MatrixUDG(char vexs[], int vlen, char edges[][2], int elen); MatrixUDG(char vexs[], int vlen, int matrix[][9]); ~MatrixUDG(); // 深度優先搜索遍歷圖 void DFS(); // 廣度優先搜索（類似於樹的層次遍歷） void BFS(); // prim最小生成樹(從start開始生成最小生成樹) void prim(int start); // 打印矩陣隊列圖 void print(); private: // 讀取一個輸入字符 char readChar(); // 返回ch在mMatrix矩陣中的位置 int getPosition(char ch); // 返回頂點v的第一個鄰接頂點的索引，失敗則返回-1 int firstVertex(int v); // 返回頂點v相對於w的下一個鄰接頂點的索引，失敗則返回-1 int nextVertex(int v, int w); // 深度優先搜索遍歷圖的遞歸實現 void DFS(int i, int *visited); }; 復制代碼 MatrixUDG是鄰接矩陣對應的結構體。 mVexs用於保存頂點，mVexNum是頂點數，mEdgNum是邊數；mMatrix則是用於保存矩陣信息的二維數組。例如，mMatrix[i][j]=1，則表示"頂點i(即mVexs[i])"和"頂點j(即mVexs[j])"是鄰接點；mMatrix[i][j]=0，則表示它們不是鄰接點。 2. 普裡姆算法 復制代碼 /* * prim最小生成樹 * * 參數說明： * start -- 從圖中的第start個元素開始，生成最小樹 */ void MatrixUDG::prim(int start) { int min,i,j,k,m,n,sum; int index=0; // prim最小樹的索引，即prims數組的索引 char prims[MAX]; // prim最小樹的結果數組 int weights[MAX]; // 頂點間邊的權值 // prim最小生成樹中第一個數是"圖中第start個頂點"，因為是從start開始的。 prims[index++] = mVexs[start]; // 初始化"頂點的權值數組"， // 將每個頂點的權值初始化為"第start個頂點"到"該頂點"的權值。 for (i = 0; i < mVexNum; i++ ) weights[i] = mMatrix[start][i]; // 將第start個頂點的權值初始化為0。 // 可以理解為"第start個頂點到它自身的距離為0"。 weights[start] = 0; for (i = 0; i < mVexNum; i++) { // 由於從start開始的，因此不需要再對第start個頂點進行處理。 if(start == i) continue; j = 0; k = 0; min = INF; // 在未被加入到最小生成樹的頂點中，找出權值最小的頂點。 while (j < mVexNum) { // 若weights[j]=0，意味著"第j個節點已經被排序過"(或者說已經加入了最小生成樹中)。 if (weights[j] != 0 && weights[j] < min) { min = weights[j]; k = j; } j++; } // 經過上面的處理後，在未被加入到最小生成樹的頂點中，權值最小的頂點是第k個頂點。 // 將第k個頂點加入到最小生成樹的結果數組中 prims[index++] = mVexs[k]; // 將"第k個頂點的權值"標記為0，意味著第k個頂點已經排序過了(或者說已經加入了最小樹結果中)。 weights[k] = 0; // 當第k個頂點被加入到最小生成樹的結果數組中之後，更新其它頂點的權值。 for (j = 0 ; j < mVexNum; j++) { // 當第j個節點沒有被處理，並且需要更新時才被更新。 if (weights[j] != 0 && mMatrix[k][j] < weights[j]) weights[j] = mMatrix[k][j]; } } // 計算最小生成樹的權值 sum = 0; for (i = 1; i < index; i++) { min = INF; // 獲取prims[i]在mMatrix中的位置 n = getPosition(prims[i]); // 在vexs[0...i]中，找出到j的權值最小的頂點。 for (j = 0; j < i; j++) { m = getPosition(prims[j]); if (mMatrix[m][n]<min) min = mMatrix[m][n]; } sum += min; } // 打印最小生成樹 cout << "PRIM(" << mVexs[start] << ")=" << sum << ": "; for (i = 0; i < index; i++) cout << prims[i] << " "; cout << endl; }
