資料結構 最小生成樹(三) prim演算法

2022-11-24 17:41:16 字數 1499 閱讀 2037

上一期介紹到了kruskal演算法,這個演算法誕生於1956年,重難點就是如何判斷是否形成迴路,此處要用到並查集,不會用當然會覺得難,今天介紹的prim演算法在kruskal演算法之後一年(即1957年)誕生,長江後浪推前浪,前浪死在沙灘上,既然後發明,那一定有很多優點吧?具體又如何用**實現?比kruskal演算法好在**?不用擔心,小編會一一解答。

prim演算法的思想:

prim演算法的主要思想就是讓一棵小樹不斷得到新的樹邊,直到長成所有節點都在樹集合中的大樹。具體做法如下:首先先得來思考,最初的小樹是什麼樣子的?當然是初始化成一個根節點。那麼這棵小樹又如何長大?此時所有的節點就只有兩種情況—要麼已經在集合中,要麼還等待選擇。無論是kruskal演算法,還是prim演算法,都用到了貪心演算法,既然是最小生成樹,那就要選擇最小的邊,prim演算法不太一樣,它所選擇的是已經在集合中的節點的連向未選節點所形成的邊中最小權重的邊,將其未選節點新增進樹邊集合中。明確了這兩個問題,就可以想出以下步驟:

1)構造最初的待選邊表:這個表包含三種元素分別是已選節點,未選節點和相連邊的權值,在最初只有一個根節點,在程式實現上,多把0節點作為根節點,所以每一個已選節點賦初值為0,那麼未選節點分別為1,2,3,4…,n-1,n,假設儲存圖的矩陣的是二維陣列map,那麼權值部分則是map[0][1],map[0][2],map[0][3]…map[0][n]。

2)不斷迴圈,直到未選節點只剩最後一個:從待選邊表找到一條最短邊,並加入樹邊集合;然後修改待選邊表,在樹邊集合中不停找出新的節點和當前的未選節點形成連邊,如果這條邊比原有最小值少就修改這條邊。

這樣最小生成樹就構建完成了,接著我們來說一說**實現方法。

**實現:

#include#include

using

namespace

std;

int n,map[1000][1000

],k;

struct tree;

void

prim()

for(int i=0;i<=n-2;i++)//

不斷找到樹邊 }}

for(int i=1;i<=n;i++)

}int

main()

正常樣例圖示:

//此圖是從mooc上copy來的

一般情況下待選邊表長這樣。

prim演算法的優點:

比起kruskal演算法來講,prim演算法可以不用判斷是否產生迴路,因為在待選邊表中不停計算的過程中,可以有效避免產生迴路的情況,可以不學並查集(有時還要學習堆),快速惡補,並且適用於稠密圖,其時間複雜度只與節點數量有關,在特定情況下可以更快的執行完程式。

prim演算法 的缺點:

prim演算法適用於稠密圖,但是稀疏圖還是kruskal演算法更勝一籌,並且prim演算法更難理解,小編現在還有點懵,寫兩道題就好了,下棋將會帶來最小生成樹例題題解。

欲知後事如何,且聽下回分解……

專欄:

Prim演算法 最小生成樹

1 define crt secure no warnings2 37 10 40 1 5 50 2 2 61 2 4 71 3 2 82 3 6 92 4 10 103 5 1 114 5 3 124 6 5 135 6 9 14 15 include 16 include 17 include ...

最小生成樹 Prim演算法

定義 設g v,e 是一個無向連通圖。如果g的生成子圖t v,e 是一棵樹,則稱t是g的一棵生成樹 spanning tree 應用生成樹可以得到關於一個電網的一組獨立的迴路方程。第一步是要得到這個電網的一棵生成樹。設b是那些不在生成樹中的電網的邊的集合,從b中取出一條邊新增到這生成樹上就生成一個環...

最小生成樹 prim演算法

在無向加權圖中,n個頂點的最小生成樹有n 1條邊,這些邊使得n個頂點之間可達,且總的代價最小。prim演算法是一種貪心演算法,將全部的頂點劃分為2個集合,每次總在2個集合之間中找最小的一條邊,區域性最優最終達到全域性最優,這正是貪心的思想。具體的描述參見相關書籍 從單一頂點開始,普里姆演算法按照以下...