最小生成樹-Prim算法詳解(含全部代碼)

程序員社區 2022-01-07 08:09:33 阅读数:508

最小 小生 生成 prim 算法

目錄

適用條件

測試所用圖

算法詳解

Prim算法代碼

全部代碼

實驗結果


適用條件

加權連通

測試所用圖

所用原圖及生成過程

其中,(a) 為原圖,圓圈裏面是節點的名稱,邊上的數字是邊的權值。由實線連接的點就是集合U,即生成樹在生成過程中加入的點。由虛線連接的點中不包含在集合U中的就是集合V-U,即待加入到生成樹的點。虛線的變化就是在每次有節點加入集合U時,V-U中的點更新到集合U的最小權值,也是貪心算法的精髓之處。

算法詳解

Prim算法又稱為加邊法,即每次選擇最小權值的邊加入到生成樹中,然後再更新權值,如此反複,保證每次最優來達到最優解。

所用數據結構

typedef struct closedge{ int adjvex; //最小邊在集合U(最小邊在當前子樹頂點集合中的那個頂點的下標) int lowcost; //最小邊上的權值};

注:算法中所提到的集合U與集合V-U,可以通過lowcost是否為0進行區分,沒必要浪費空間。

初始化

頂點數組下標i 0 1 2 3 4 5
adjvex 0 0 0 0 0 0
lowcost 0 6 1 5
集合U 0

添加第一條邊

頂點數組下標i 0 1 2 3 4 5
adjvex 0 2 2 0 2 2
lowcost 0 5 0 5 6 4
集合U 0,2

可以看到,初始化後,頂點2與集合U(頂點0)之間的距離是最小的。所以,添加頂點2至集合U;接下來進行更新,發現原節點1與集合U(頂點0)之間的距離6>現在節點1與集合U(頂點0、2)之間的距離5,所以進行更新。將adjvex更新為節點1與集合U最小距離時的集合U中頂點,lowcost就是選擇的邊的權值。

以上的話請讀者再仔細閱讀一遍,並結合測試所用圖來考慮標紅的其他部分。下面的錶不再贅述。

添加第二條邊

頂點數組下標i 0 1 2 3 4 5
adjvex 0 2 2 5 2 5
lowcost 0 5 0 2 6 0
集合U 0,2,5

添加第三條邊

頂點數組下標i 0 1 2 3 4 5
adjvex 0 2 2 3 2 5
lowcost 0 5 0 0 6 0
集合U 0,2,5,3

添加第四條邊

頂點數組下標i 0 1 2 3 4 5
adjvex 0 1 2 3 1 5
lowcost 0 0 0 0 3 0
集合U 0,2,3,5,1

添加第五條邊

頂點數組下標i 0 1 2 3 4 5
adjvex 0 1 2 3 4 5
lowcost 0 0 0 0 0 0
集合U 0,2,3,5,1,4

Prim算法代碼

//最小生成樹-Prim算法 參數:圖Gvoid Prim(Graph G){ int v=0;//初始節點 closedge C[MaxVerNum]; int mincost = 0; //記錄最小生成樹的各邊權值之和 //初始化 for (int i = 0; i < G.vexnum; i++) { C[i].adjvex = v; C[i].lowcost = G.Edge[v][i]; } cout << "最小生成樹的所有邊:"<< endl; //初始化完畢,開始G.vexnum-1次循環 for (int i = 1; i < G.vexnum; i++) { int k; int min = INF; //求出與集合U權值最小的點 權值為0的代錶在集合U中 for (int j = 0; j<G.vexnum; j++) { if (C[j].lowcost != 0 && C[j].lowcost<min) { min = C[j].lowcost; k = j; } } //輸出選擇的邊並累計權值 cout << "(" << G.Vex[k] << "," << G.Vex[C[k].adjvex]<<") "; mincost += C[k].lowcost; //更新最小邊 for (int j = 0; j<G.vexnum; j++) { if (C[j].lowcost != 0 && G.Edge[k][j]<C[j].lowcost) { C[j].adjvex = k; C[j].lowcost= G.Edge[k][j]; } } } cout << "最小生成樹權值之和:" << mincost << endl;}

全部代碼

/*Project: 圖-最小生成樹-Prim算法Date: 2019/11/10Author: Frank Yu基本操作函數:InitGraph(Graph &G) 初始化函數 參數:圖G 作用:初始化圖的頂點錶,鄰接矩陣等InsertNode(Graph &G,VexType v) 插入點函數 參數:圖G,頂點v 作用:在圖G中插入頂點v,即改變頂點錶InsertEdge(Graph &G,VexType v,VexType w) 插入邊函數 參數:圖G,某邊兩端點v和w 作用:在圖G兩點v,w之間加入邊,即改變鄰接矩陣Adjancent(Graph G,VexType v,VexType w) 判斷是否存在邊(v,w)函數 參數:圖G,某邊兩端點v和w 作用:判斷是否存在邊(v,w)BFS(Graph G, int start) 廣度遍曆函數 參數:圖G,開始結點下標start 作用:寬度遍曆DFS(Graph G, int start) 深度遍曆函數(遞歸形式)參數:圖G,開始結點下標start 作用:深度遍曆Dijkstra(Graph G, int v) 最短路徑 - Dijkstra算法 參數:圖G、源點v功能實現函數:CreateGraph(Graph &G) 創建圖功能實現函數 參數:圖G InsertNode 作用:創建圖BFSTraverse(Graph G) 廣度遍曆功能實現函數 參數:圖G 作用:寬度遍曆DFSTraverse(Graph G) 深度遍曆功能實現函數 參數:圖G 作用:深度遍曆Shortest_Dijkstra(Graph &G) 調用最短路徑-Dijkstra算法 參數:圖G、源點vPrim(Graph G) 最小生成樹-Prim算法 參數:圖G*/#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<string>#include<set>#include<list>#include<queue>#include<vector>#include<map>#include<iterator>#include<algorithm>#include<iostream>#define MaxVerNum 100 //頂點最大數目值#define VexType char //頂點數據類型#define EdgeType int //邊數據類型,無向圖時鄰接矩陣對稱,有權值時錶示權值,沒有時1連0不連#define INF 0x3f3f3f3f//作為最大值using namespace std;//圖的數據結構typedef struct Graph{ VexType Vex[MaxVerNum];//頂點錶 EdgeType Edge[MaxVerNum][MaxVerNum];//邊錶 int vexnum, arcnum;//頂點數、邊數}Graph;//迪傑斯特拉算法全局變量bool S[MaxVerNum]; //頂點集int D[MaxVerNum]; //到各個頂點的最短路徑int Pr[MaxVerNum]; //記錄前驅//Prim算法所用數據結構typedef struct closedge{ int adjvex; //最小邊在集合U(最小邊在當前子樹頂點集合中的那個頂點的下標) int lowcost; //最小邊上的權值};//*********************************************基本操作函數*****************************************////初始化函數 參數:圖G 作用:初始化圖的頂點錶,鄰接矩陣等void InitGraph(Graph &G){ memset(G.Vex, '#', sizeof(G.Vex));//初始化頂點錶 //初始化邊錶 for (int i = 0; i < MaxVerNum; i++) for (int j = 0; j < MaxVerNum; j++) { G.Edge[i][j] = INF; if (i == j)G.Edge[i][j] = 0;//在最小生成樹時,考慮無環簡單圖,故自己到自己設置為0 } G.arcnum = G.vexnum = 0; //初始化頂點數、邊數}//插入點函數 參數:圖G,頂點v 作用:在圖G中插入頂點v,即改變頂點錶bool InsertNode(Graph &G, VexType v){ if (G.vexnum < MaxVerNum) { G.Vex[G.vexnum++] = v; return true; } return false;}//插入邊函數 參數:圖G,某邊兩端點v和w 作用:在圖G兩點v,w之間加入邊,即改變鄰接矩陣bool InsertEdge(Graph &G, VexType v, VexType w, int weight){ int p1, p2;//v,w兩點下標 p1 = p2 = -1;//初始化 for (int i = 0; i<G.vexnum; i++)//尋找頂點下標 { if (G.Vex[i] == v)p1 = i; if (G.Vex[i] == w)p2 = i; } if (-1 != p1&&-1 != p2)//兩點均可在圖中找到 { G.Edge[p1][p2] = G.Edge[p2][p1] = weight;//無向圖鄰接矩陣對稱 G.arcnum++; return true; } return false;}//判斷是否存在邊(v,w)函數 參數:圖G,某邊兩端點v和w 作用:判斷是否存在邊(v,w) bool Adjancent(Graph G, VexType v, VexType w){ int p1, p2;//v,w兩點下標 p1 = p2 = -1;//初始化 for (int i = 0; i<G.vexnum; i++)//尋找頂點下標 { if (G.Vex[i] == v)p1 = i; if (G.Vex[i] == w)p2 = i; } if (-1 != p1&&-1 != p2)//兩點均可在圖中找到 { if (G.Edge[p1][p2] == 1)//存在邊 { return true; } return false; } return false;}bool visited[MaxVerNum];//訪問標記數組,用於遍曆時的標記//廣度遍曆函數 參數:圖G,開始結點下標start 作用:寬度遍曆void BFS(Graph G, int start){ queue<int> Q;//輔助隊列 cout << G.Vex[start];//訪問結點 visited[start] = true; Q.push(start);//入隊 while (!Q.empty())//隊列非空 { int v = Q.front();//得到隊頭元素 Q.pop();//出隊 for (int j = 0; j<G.vexnum; j++)//鄰接點 { if (G.Edge[v][j] <INF && !visited[j])//是鄰接點且未訪問 { cout << "->"; cout << G.Vex[j];//訪問結點 visited[j] = true; Q.push(j);//入隊 } } }//while cout << endl;}//深度遍曆函數(遞歸形式)參數:圖G,開始結點下標start 作用:深度遍曆void DFS(Graph G, int start){ cout << G.Vex[start];//訪問 visited[start] = true; for (int j = 0; j < G.vexnum; j++) { if (G.Edge[start][j] < INF && !visited[j])//是鄰接點且未訪問 { cout << "->"; DFS(G, j);//遞歸深度遍曆 } }}//最短路徑 - Dijkstra算法 參數:圖G、源點vvoid Dijkstra(Graph G, int v){ //初始化 int n = G.vexnum;//n為圖的頂點個數 for (int i = 0; i < n; i++) { S[i] = false; D[i] = G.Edge[v][i]; if (D[i] < INF)Pr[i] = v; //v與i連接,v為前驅 else Pr[i] = -1; } S[v] = true; D[v] = 0; //初始化結束,求最短路徑,並加入S集 for (int i = 1; i < n; i++) { int min = INF; int temp; for (int w = 0; w < n; w++) if (!S[w] && D[w] < min) //某點temp未加入s集,且為當前最短路徑 { temp = w; min = D[w]; } S[temp] = true; //更新從源點出發至其餘點的最短路徑 通過temp for (int w = 0; w < n; w++) if (!S[w] && D[temp] + G.Edge[temp][w] < D[w]) { D[w] = D[temp] + G.Edge[temp][w]; Pr[w] = temp; } }}//輸出最短路徑void Path(Graph G, int v){ if (Pr[v] == -1) return; Path(G, Pr[v]); cout << G.Vex[Pr[v]] << "->";}//**********************************************功能實現函數*****************************************////打印圖的頂點錶void PrintVex(Graph G){ for (int i = 0; i < G.vexnum; i++) { cout << G.Vex[i] << " "; } cout << endl;}//打印圖的邊矩陣void PrintEdge(Graph G){ for (int i = 0; i < G.vexnum; i++) { for (int j = 0; j < G.vexnum; j++) { if (G.Edge[i][j] == INF)cout << "∞ "; else cout << G.Edge[i][j] << " "; } cout << endl; }}//創建圖功能實現函數 參數:圖G InsertNode 作用:創建圖void CreateGraph(Graph &G){ VexType v, w; int vn, an;//頂點數,邊數 cout << "請輸入頂點數目:" << endl; cin >> vn; cout << "請輸入邊數目:" << endl; cin >> an; cout << "請輸入所有頂點名稱:" << endl; for (int i = 0; i<vn; i++) { cin >> v; if (InsertNode(G, v)) continue;//插入點 else { cout << "輸入錯誤!" << endl; break; } } cout << "請輸入所有邊(每行輸入邊連接的兩個頂點及權值):" << endl; for (int j = 0; j<an; j++) { int weight; cin >> v >> w >> weight; if (InsertEdge(G, v, w, weight)) continue;//插入邊 else { cout << "輸入錯誤!" << endl; break; } } PrintVex(G); PrintEdge(G);}//廣度遍曆功能實現函數 參數:圖G 作用:寬度遍曆void BFSTraverse(Graph G){ for (int i = 0; i<MaxVerNum; i++)//初始化訪問標記數組 { visited[i] = false; } for (int i = 0; i < G.vexnum; i++)//對每個連通分量進行遍曆 { if (!visited[i])BFS(G, i); }}//深度遍曆功能實現函數 參數:圖G 作用:深度遍曆void DFSTraverse(Graph G){ for (int i = 0; i<MaxVerNum; i++)//初始化訪問標記數組 { visited[i] = false; } for (int i = 0; i < G.vexnum; i++)//對每個連通分量進行遍曆 { if (!visited[i]) { DFS(G, i); cout << endl; } }}//調用最短路徑-Dijkstra算法 參數:圖G、源點vvoid Shortest_Dijkstra(Graph &G){ char vname; int v = -1; cout << "請輸入源點名稱:" << endl; cin >> vname; for (int i = 0; i < G.vexnum; i++) if (G.Vex[i] == vname)v = i; if (v == -1) { cout << "沒有找到輸入點!" << endl; return; } Dijkstra(G, v); cout << "目標點" << "\t" << "最短路徑值" << "\t" << "最短路徑" << endl; for (int i = 0; i < G.vexnum; i++) { if (i != v) { cout << " " << G.Vex[i] << "\t" << " " << D[i] << "\t"; Path(G, i); cout << G.Vex[i] << endl; } }}//最小生成樹-Prim算法 參數:圖Gvoid Prim(Graph G){ int v=0;//初始節點 closedge C[MaxVerNum]; int mincost = 0; //記錄最小生成樹的各邊權值之和 //初始化 for (int i = 0; i < G.vexnum; i++) { C[i].adjvex = v; C[i].lowcost = G.Edge[v][i]; } cout << "最小生成樹的所有邊:"<< endl; //初始化完畢,開始G.vexnum-1次循環 for (int i = 1; i < G.vexnum; i++) { int k; int min = INF; //求出與集合U權值最小的點 權值為0的代錶在集合U中 for (int j = 0; j<G.vexnum; j++) { if (C[j].lowcost != 0 && C[j].lowcost<min) { min = C[j].lowcost; k = j; } } //輸出選擇的邊並累計權值 cout << "(" << G.Vex[k] << "," << G.Vex[C[k].adjvex]<<") "; mincost += C[k].lowcost; //更新最小邊 for (int j = 0; j<G.vexnum; j++) { if (C[j].lowcost != 0 && G.Edge[k][j]<C[j].lowcost) { C[j].adjvex = k; C[j].lowcost= G.Edge[k][j]; } } } cout << "最小生成樹權值之和:" << mincost << endl;}//菜單void menu(){ cout << "************1.創建圖 2.廣度遍曆******************" << endl; cout << "************3.深度遍曆 4.迪傑斯特拉****************" << endl; cout << "************5.最小生成樹(Prim) 6.退出 ****************" << endl;}//主函數int main(){ int choice = 0; Graph G; InitGraph(G); while (1) { menu(); printf("請輸入菜單序號:\n"); scanf("%d", &choice); if (6 == choice) break; switch (choice) { case 1:CreateGraph(G); break; case 2:BFSTraverse(G); break; case 3:DFSTraverse(G); break; case 4:Shortest_Dijkstra(G); break; case 5:Prim(G); break; default:printf("輸入錯誤!!!\n"); break; } } return 0;}

實驗結果

實驗結果截圖

與kruskal算法的對比在這篇文章中:最小生成樹-Kruskal算法詳解(含全部代碼)

版权声明:本文为[程序員社區]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201070809324851.html