?

????? 在一個具有幾個頂點的連通圖G中，如果存在子圖G'包含G中所有頂點和一部分邊，且不形成回路，則稱G'為圖G的生成樹，代價最小生成樹則稱為最小生成樹。??????????

????? 許多應用問題都是一個求無向連通圖的最小生成樹問題。例如：要在n個城市之間鋪設光纜，主要目標是要使這 n 個城市的任意兩個之間都可以通信，但鋪設光纜的費用很高，且各個城市之間鋪設光纜的費用不同；另一個目標是要使鋪設光纜的總費用最低。這就需要找到帶權的最小生成樹。

????? 性質

• 最小生成樹的邊數必然是頂點數減一，|E| = |V| - 1。
• 最小生成樹不可以有循環。
• 最小生成樹不必是唯一的。

Prim算法與Kruskal算法是尋找最小生成樹的經典方法。

prim算法：

從單一頂點開始，普里姆算法按照以下步驟逐步擴大樹中所含頂點的數目，直到遍及連通圖的所有頂點。

輸入：一個加權連通圖，其中頂點集合為V，邊集合為E；

初始化：V_new = {x}，其中x為集合V中的任一節點（起始點），E_new = {}；

重復下列操作，直到V_new= V：

在集合E中選取權值最小的邊（u, v），其中u為集合V_new中的元素，而v則不是（如果存在有多條滿足前述條件即具有相同權值的邊，則可任意選取其中之一）；

將v加入集合V_new中，將（u, v）加入集合E_new中；

輸出：使用集合V_new和E_new來描述所得到的最小生成樹。

???? 為實現這個算法需要一個輔助數組closedge，來記錄V_new到V-V_new具有最小權值的邊。對于每個頂點v_i∈V-V_new，在輔助數組中存在一個分量closedge[i]，表示v_i到V_new的最小代價邊，closedge包括兩個域， adjvex表示這條邊的頂點，lowcost表示v_i到adjvex的權值。當選擇新的頂點到V_new,選擇新的邊到E_new時，要更新closedge

?無向加權圖：

Graph #include <iostream> #include <vector> #include <queue> #define MAXW 1000//定義最大權值 using namespace std; template<class T> class Graph//無向加權圖 { public:Graph();~Graph();void Create();//生成加權圖void DFSTraverse(void (*fun)(T));//深度優先遍歷void BFSTraverse(void (*fun)(T));//廣度優先遍歷int LocateVex(T vex);int GetVexnum(){return vexnum;}int GetArcnum(){return arcnum;}int** GetAdjMatrix(){return adjMatrix;}T GetVex(int i){return vexs[i];} private:vector<T> vexs;//頂點數組int** adjMatrix;//鄰接矩陣int arcnum;//弧數int vexnum;//頂點數bool *visited;int FirstAdjVex(int v);//v的第一個鄰接點int NextAdjVex(int v,int w);//從w開始找v的下個鄰接點void DFS(int i,void (*fun)(T)); };template<class T> Graph<T>::Graph() {adjMatrix=NULL;arcnum=0;visited=NULL; }template<class T> Graph<T>::~Graph() {for (int i=0;i<vexnum;i++){delete [] adjMatrix[i];}delete adjMatrix;adjMatrix=0;delete [] visited; }template<class T> void Graph<T>::Create() {cout<<"輸入頂點數，弧數（以空格隔開）：";cin>>vexnum;cin>>arcnum;adjMatrix=new int*[vexnum];for(int i=0;i<vexnum;i++)adjMatrix[i]=new int[vexnum];for (int i=0;i<vexnum;i++){for(int j=0;j<vexnum;j++)adjMatrix[i][j]=MAXW;//初始化鄰接矩陣 }visited=new bool[vexnum];cout<<"輸入頂點列，以空格隔開：";for (int i=0;i<vexnum;i++){T temp;cin>>temp;vexs.push_back(temp);//輸入頂點 }cout<<"輸入一條邊依附的頂點及權值（A B 1）:"<<endl;for (int i=0;i<arcnum;i++){T v1,v2;int w;cin>>v1;cin>>v2;cin>>w;int x=LocateVex(v1);int y=LocateVex(v2);adjMatrix[x][y]=w;adjMatrix[y][x]=w;//設置權值 } }template<class T> int Graph<T>::LocateVex(T vex) {for(int i=0;i<vexnum;i++){if (vexs[i]==vex){return i;}}return -1; }template<class T> int Graph<T>::FirstAdjVex(int v) {for (int i=0;i<vexnum;i++){if(adjMatrix[v][i]!=MAXW)return i;}return -1; }template<class T> int Graph<T>::NextAdjVex(int v,int w) {for (int i=w+1;i<vexnum;i++){if(adjMatrix[v][i]!=MAXW)return i;}return -1; }template<class T> void Graph<T>::DFS(int i,void (*fun)(T))//從第i個頂點深度優先遍歷 {visited[i]=true;fun(vexs[i]);for (int w=FirstAdjVex(i);w>=0;w=NextAdjVex(i,w)){if(!visited[w]) DFS(w,fun);}}template<class T> void Graph<T>::DFSTraverse(void (*fun)(T)) {for(int i=0;i<vexnum;i++)visited[i]=false;for (int i=0;i<vexnum;i++){if(!visited[i])DFS(i,fun);} }template<class T> void Graph<T>::BFSTraverse(void (*fun)(T)) {queue<int> Q;for(int i=0;i<vexnum;i++)visited[i]=false;visited[0]=true;fun(vexs[0]);Q.push(0);//頂點入隊while (!Q.empty()){//int v=Q.back();int v=Q.front();// 出隊 Q.pop();for(int w=FirstAdjVex(v);w>=0;w=NextAdjVex(v,w)){if(!visited[w]){visited[w]=true;fun(vexs[w]);Q.push(w);//訪問后頂點入隊 }}} }

?

prim算法：

template<class T> void MinSpanTree_PRIM(Graph<T> &G,T u) {//Prim算法，生成最小生成樹struct cell{T adjvex;//鄰接頂點int lowcost;//最小權值 };cell* closedge=new cell[G.GetVexnum()];//輔助數組int k=G.LocateVex(u);for (int i=0;i<G.GetVexnum();i++){if(i!=k){closedge[i].adjvex=u;closedge[i].lowcost=G.GetAdjMatrix()[k][i];}}closedge[k].lowcost=0;for (int i=1;i<G.GetVexnum();i++){int w=MAXW;for(int j=0;j<G.GetVexnum();j++){if(closedge[j].lowcost<w&&closedge[j].lowcost>0){w=closedge[j].lowcost;k=j;}}//輸出路徑cout<<endl;cout<<"找到路徑："<<closedge[k].adjvex<<"----"<<G.GetVex(k)<<"權值："<<w<<endl;closedge[k].lowcost=0;for(int j=0;j<G.GetVexnum();j++){//更新closedge[j]if (G.GetAdjMatrix()[k][j]<closedge[j].lowcost){closedge[j].adjvex=G.GetVex(k);closedge[j].lowcost=G.GetAdjMatrix()[k][j];}}}}

main：

void printfun(char ch) {cout<<ch<<" "; } int main() {Graph<char> G;G.Create();cout<<"深度優先遍歷:";G.DFSTraverse(printfun);cout<<endl<<"廣度優先遍歷：";G.BFSTraverse(printfun);MinSpanTree_PRIM(G,G.GetVex(0));return 1;}

?

?例子：

原圖：

運行結果：

?

轉載于:https://www.cnblogs.com/wonderKK/archive/2012/04/12/2444571.html

總結

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

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