Prim算法是用來尋找一個聯通圖的最小生成樹的算法，是數據結構中一個十分經典的算法，與他齊名的還有了克魯斯卡爾算法，將會在下一篇
中提到。
Prim算法思想（歸并頂點）：
首先給定一個起始點，例如我們以A為起始點，選擇與它關聯的具有最小權值的邊，將其加入到生成樹的集合頂點U中去（這里我們用visited[i] = true 來實現）；
然后我們進行N - 1次循環從U中 及 非U中選擇兩個聯通的且具有最小權值的頂點，把非U的頂點加入U中，直到所有頂點都加入到U中為止。
實例圖：

這個圖較為清晰直觀的分析了Prim算法的思想。
代碼如下：
1.數據及結構的定義：

#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm>#define N 100 #define INITFITE 1000000 using namespace std;struct Node{char data;int lowcost; }closedge[N];typedef struct NNode{int vernum,arcnum;//頂點數，邊數；char ver[N];int martrix[N][N]; }Graph;int locate (Graph G,char ch) //找到對應字符的下標; {int i;for (i = 0;i < G.vernum;i++){if (G.ver[i] == ch)return i;} }

2.建立鄰接矩陣：

void create_Graph (Graph &G) {char v1,v2;int weight; //權值；cout<<"please key in the vernum & arcnum"<<endl;cin>>G.vernum>>G.arcnum;cout<<"please key in all the vertexs"<<endl;for (int i = 0;i < G.vernum;i++)cin>>G.ver[i];cout<<"please key in the v1 & v2 & weight"<<endl;for (int ii = 0; ii < G.vernum;ii++)for (int jj = 0; jj < G.vernum;jj++)G.martrix[ii][jj] = INITFITE; //初始化矩陣的時候將矩陣的值賦成無窮大。for (int ii = 0;ii < G.arcnum;ii++){cin>>v1>>v2>>weight;int i = locate(G,v1);int j = locate(G,v2);//cout<<i<<" "<<j<<endl;G.martrix[i][j] = weight;G.martrix[j][i] = weight;} }

3.Prim算法：

bool visited[N];void Prim(Graph &G,char ch) {int v,w;v = locate(G,ch);visited[v] = true;int min = 1000000;for (int i = 0;i < G.vernum;i++)//為第一個頂點找到鄰接點{if (!visited[i]) { closedge[i].data = G.ver[v]; //將第i的點的上一個鄰接點暫時賦成G.ver[v]；closedge[i].lowcost = G.martrix[v][i];if (closedge[i].lowcost < min) //判斷并找到最小的權值{min = closedge[i].lowcost;w = i; //記錄最小權值的下標}}}cout<<closedge[w].data<<" "<<G.ver[w]<<" "<<closedge[v].lowcost; //輸出！！cout<<endl;//visited[w] = true;for (int i = 0;i < G.vernum - 2;i++)//n-1次循環找到剩余的n-1個點{visited[w] = true;//將G.ver[w]加入U；v = w;min = 1000000;for (int j = 0;j < G.vernum;j++){if (!visited[j]){if (G.martrix[v][j] < closedge[j].lowcost) //關鍵（核心思想）：看G.ver[w]的引入是否改變了到達其他頂點的最小值，如果改變了就從新賦值，否則不變。{closedge[j].data = G.ver[v];closedge[j].lowcost = G.martrix[v][j];}if (closedge[j].lowcost < min){min = closedge[j].lowcost;w = j;}} }cout<<closedge[w].data<<" "<<G.ver[w]<<" "<<closedge[v].lowcost;cout<<endl; } }

4.主函數

int main(){Graph G;create_Graph(G);for (int i = 0; i < G.vernum;i++){for (int j = 0; j < G.vernum;j++)printf("%8d",G.martrix[i][j]);cout<<endl;}Prim(G,'A');return 0; }

Prim 算法在考研中占有相當大的比重，要求熟練掌握編碼！！

總結

以上是生活随笔為你收集整理的Prim算法详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。