Prim算法求最小生成樹

《Prim算法求最小生成樹》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、算法分析與設計實驗報告第次實驗實驗名稱貪心法求最小生成樹實驗目的通過上機實驗，掌握貪心算法的思想，利用Prim算法求解最小生成樹并實現(xiàn)。使用貪心法設計連通帶權(quán)圖最小生成樹。實驗原理(1)一無向連通帶權(quán)圖，用visited[]數(shù)組標記該頂點是否被訪問，用map[][]數(shù)組表示邊的權(quán)值，low[]存儲最小權(quán)值,result計算最終的權(quán)值之和即最小花費；(2)首先置S=1，選取滿足：i屬于S，k屬于V-S，且map[i][k]最小的邊，將頂點k添加到S中去，直到S=V為止。(3)設置數(shù)組closest[i]表示與頂點i之間權(quán)值最小的頂點，便于輸出最小生成樹。實驗步驟(1)

2、首先，用二維數(shù)組記錄點和權(quán)值;(2)選取一個點作為起始點，選擇與它鄰近的權(quán)值最小的點，用low數(shù)組更新最小權(quán)值。比較得到最小權(quán)值，用visited[]標記為1；無法到達的點用maxInt表示。(3)再在延伸的點繼續(xù)找與它鄰近的兩者權(quán)值最小的點，將頂點依次加入S集合中，更新low[]和closest[]的值，累加更新最小權(quán)值之和result.(4)所有點連通后，即得到最小生成樹。關(guān)鍵代碼intprim(){inti;intmin=MaxInt,result=0;memset(visited,0,sizeof(visited));visited[1]=1;//從某點開始

3、，分別標記和記錄該點for(i=2;i<=n;i++){low[i]=map[1][i];//給low數(shù)組賦值closest[i]=1;visited[i]=0;}for(i=1;ilow[j]){min=low[j];k=j;cout<

4、tj=2;j<=n;j++)//更新權(quán)值if(visited[j]==0&&low[j]>map[k][j]){low[j]=map[k][j];closest[j]=k;}}returnresult;}測試結(jié)果最小生成樹N=4:最小生成樹N=5:最小生成樹N=6:實驗心得通過本次實驗明白了最小生成樹貪心算法的設計思路，掌握了prim算法選邊的原理，我將課本上的算法加以改進，同時輸出最小生成樹和最小花費，完善了代碼。在課本上了解了另外一種經(jīng)典算法Kruskal算法，它按權(quán)的遞增順序查看邊的序列可以看做一個優(yōu)先隊列，優(yōu)先級為邊的權(quán)，也了解了并查集這種抽象的數(shù)據(jù)類型。P

5、rim算法十分經(jīng)典，在設計通信網(wǎng)絡中常用于解決城市之間通信線路所需費用的問題，感覺十分經(jīng)濟實用。附錄：完整代碼#include#include#include#include#include#defineMaxInt0x3f3f3f3f#defineN110usingnamespacestd;//創(chuàng)建map二維數(shù)組儲存圖表，low數(shù)組記錄每2個點間最小權(quán)值，visited數(shù)組標記某點是否已訪問intmap[N][N],low[N],closest[N],visited[N];

6、intn;intprim(){inti;intmin=MaxInt,result=0;memset(visited,0,sizeof(visited));visited[1]=1;//從某點開始，分別標記和記錄該點for(i=2;i<=n;i++){low[i]=map[1][i];//給low數(shù)組賦值closest[i]=1;visited[i]=0;}for(i=1;ilow[j]){m

7、in=low[j];k=j;cout<map[k][j]){low[j]=map[k][j];closest[j]=k;}}returnresult;}intmain(){inti,p=0;doublek=0.0;clock_tstart,end,over;start=clock();end=clock();over=e