Prim(普里姆)算法求最小生成樹的思想及C語言實(shí)例講解
Prim 算法思想:
從任意一頂點(diǎn) v0 開始選擇其最近頂點(diǎn) v1 構(gòu)成樹 T1,再連接與 T1 最近頂點(diǎn) v2 構(gòu)成樹 T2, 如此重復(fù)直到所有頂點(diǎn)均在所構(gòu)成樹中為止。
最小生成樹(MST):權(quán)值最小的生成樹。
生成樹和最小生成樹的應(yīng)用:要連通n個(gè)城市需要n-1條邊線路??梢园堰吷系臋?quán)值解釋為線路的造價(jià)。則最小生成樹表示使其造價(jià)最小的生成樹。
構(gòu)造網(wǎng)的最小生成樹必須解決下面兩個(gè)問題:
1、盡可能選取權(quán)值小的邊,但不能構(gòu)成回路;
2、選取n-1條恰當(dāng)?shù)倪呉赃B通n個(gè)頂點(diǎn);
MST性質(zhì):假設(shè)G=(V,E)是一個(gè)連通網(wǎng),U是頂點(diǎn)V的一個(gè)非空子集。若(u,v)是一條具有最小權(quán)值的邊,其中u∈U,v∈V-U,則必存在一棵包含邊(u,v)的最小生成樹。
prim算法假設(shè)G=(V,E)是連通的,TE是G上最小生成樹中邊的集合。算法從U={u0}(u0∈V)、TE={}開始。重復(fù)執(zhí)行下列操作:
在所有u∈U,v∈V-U的邊(u,v)∈E中找一條權(quán)值最小的邊(u0,v0)并入集合TE中,同時(shí)v0并入U(xiǎn),直到V=U為止。
此時(shí),TE中必有n-1條邊,T=(V,TE)為G的最小生成樹。
Prim算法的核心:始終保持TE中的邊集構(gòu)成一棵生成樹。
注意:prim算法適合稠密圖,其時(shí)間復(fù)雜度為O(n^2),其時(shí)間復(fù)雜度與邊得數(shù)目無關(guān),而kruskal算法的時(shí)間復(fù)雜度為O(eloge)跟邊的數(shù)目有關(guān),適合稀疏圖。
舉個(gè)簡單的例子來說明具體的實(shí)現(xiàn)方法:
G:圖,用鄰接矩陣表示
vcount:表示圖的頂點(diǎn)個(gè)數(shù)
max_vertexes:圖最大節(jié)點(diǎn)數(shù)
infinity:為無窮大
數(shù)組存儲(chǔ)從0開始
由于最小生成樹包含每個(gè)頂點(diǎn),那么頂點(diǎn)的選中與否就可以直接用一個(gè)數(shù)組來標(biāo)記used[max_vertexes];(我們這里直接使用程序代碼中的變量定義,這樣也易于理解);當(dāng)選中一個(gè)數(shù)組的時(shí)候那么就標(biāo)記,現(xiàn)在就有一個(gè)問題,怎么來選擇最小權(quán)值邊,注意這里最小權(quán)值邊是有限制的,邊的一個(gè)頂點(diǎn)一定在已選頂點(diǎn)中,另一個(gè)頂點(diǎn)當(dāng)然就是在未選頂點(diǎn)集合中了。我最初的一個(gè)想法就是窮搜了,就是在一個(gè)集合中選擇一個(gè)頂點(diǎn),來查找到另一個(gè)集合中的最小值,這樣雖然很易于理解,但是很明顯效率不是很高,在嚴(yán)蔚敏的《數(shù)據(jù)結(jié)構(gòu)》上提供了一種比較好的方法來解決:設(shè)置兩個(gè)輔助數(shù)組lowcost[max_vertexes]和closeset[max_vertexes],lowcost[max_vertexes]數(shù)組記錄從U到V-U具有最小代價(jià)的邊。對于每個(gè)頂點(diǎn)v∈V-U,closedge[v], closeset[max_vertexes]記錄了該邊依附的在U中的頂點(diǎn)。
Prim 算法步驟:
T0 存放生成樹的邊,初值為空
輸入加權(quán)圖的帶權(quán)鄰接矩陣 C = (Cij)n×n (兩點(diǎn)間無邊相連則其大小為無窮)
為每個(gè)頂點(diǎn) v 添加一屬性 L(v) :表 v 到 T0 的最小直接距離
(1) T0←∅, V1={v0}, C(T0)=0
(2) 對任意v ∈ V,L(v)←C(v, v0)
(3) If V==V1 then stop else goto next.
(4) 在 V-V1 中找點(diǎn) u 使 L(u) =min{ L(v) | v ∈ (V − V1 )},記 V1 中與 u 相鄰點(diǎn)為 w.
(5) T0←T0∪{(u, w)}, C(T0) ←C(T0)+C(u, w), V1←V1∪{u}
(6) 對任意v ∈ (V − V1 ) if C(v, u)<L(v) then L(v) = C(v, u) else L(v)不變。
(7) Go to 3.
C++實(shí)現(xiàn)示例
prim.txt中的內(nèi)容:
1 2 6 1 3 1 1 4 5 2 3 5 2 5 3 3 4 5 3 5 6 3 6 4 5 6 6 4 6 2
程序代碼:
#include<stdo.h> #include<string.h> #include <stdlib.h> #define infinity 1000000 // 定義兩個(gè)不直接相鄰一步到達(dá)頂點(diǎn)的距離 #define max_vertexes 6 // 定義圖形中頂點(diǎn)的個(gè)數(shù) typedef int Graph[max_vertexes][max_vertexes];// 邊上的權(quán)值 void prim(Graph G,int vcount,int father[]) { int i,j,k; int lowcost[max_vertexes];//最小代價(jià)邊上的權(quán)值 int closeset[max_vertexes],used[max_vertexes];//依附在U中的頂點(diǎn);標(biāo)記是否已被選中 int min; int result=0;//記錄最短距離權(quán)值的和 for (i=0;i<vcoun;k++) //初始化所有數(shù)組,把最短距離初始化為其他頂點(diǎn)到1結(jié)點(diǎn)的距離 { lowcost[i]=G[0][i]; closeset[i]=0; used[i]=0; father[i]=-1; } used[0]=1; for (i=1;i<=vcount-1;i++) { j=0; min = infinity; for (k=1;k<count;k++) //for循環(huán)得到離結(jié)點(diǎn)最近的頂點(diǎn)j if ((!used[k])&&(lowcost[k] { min = lowcost[k]; j=k; } father[j]=closeset[j]; printf("%d %d\n",j+1,father[j]+1);//輸出當(dāng)前找到的結(jié)點(diǎn),該頂點(diǎn)依附的上一個(gè)結(jié)點(diǎn) result=result+G[j][closeset[j]]; used[j]=1;;//把第j個(gè)頂點(diǎn)并入了U中 for (k=1;k if (!used[k]&&(G[j][k]保留到k的最短路徑 { lowcost[k]=G[j][k]; closeset[k]=j; } } printf("%d",result); } int main() { FILE *fr; int i,j,weight; Graph G; int fatheer[max_vertexes]; for(i=0; i<max_vertexes;i++) for(j=0; j<max_vertexer;i++) G[i][j] = infinity; fr = fopen("prim.txt","r"); if(!fr) { printf("fopen failed\n"); exit(1); } while(fscanf(fr,"%d%d%d", &i, &j, &weight) != EOF) { G[i-1][j-1] = weight; G[j-1][i-1] = weight; } prim(G,max_vertexes,fatheer); return 0; }
測試的結(jié)果如下:
相關(guān)文章
C語言多維數(shù)組數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)詳解
對于數(shù)組想必大家都不陌生首先得要知道的是對于數(shù)組元素在內(nèi)存存儲(chǔ)是連續(xù)性的,下面這篇文章主要給大家介紹了關(guān)于C語言多維數(shù)組數(shù)據(jù)結(jié)構(gòu)的相關(guān)資料,需要的朋友可以參考下2021-12-12C++實(shí)現(xiàn)LeetCode(62.不同的路徑)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(62.不同的路徑),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07