Prim算法

Prim算法用于構(gòu)造最小生成樹，且適用于稠密圖。

---

基本思想 : 歸并頂點

設(shè)連通網(wǎng)絡(luò) N = { V, E }

從某頂點 u0 出發(fā)，
選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(u0, v)，
將其頂點加入到生成樹的頂點集合U中

每一步從U中挑選一個頂點u，而另一個頂點不在U中的各個頂點中選擇權(quán)值最小的邊(u, v),把它的頂點加入到U中

直到所有頂點都加入到生成樹頂點集合U中為止

舉例

Kruskal算法

Krusklal算法用于構(gòu)造最小生成樹，且適用于稀疏圖。

---

基本思想 : 歸并邊

設(shè)連通網(wǎng)絡(luò) N = { V, E }

構(gòu)造一個只有 n 個頂點，沒有邊的非連通圖 T = { V, $?$}, 每個頂點自成一個連通分量

在 E 中選最小權(quán)值的邊,若該邊的兩個頂點落在不同的連通分量上，則加入 T 中；否則舍去，重新選擇

重復(fù)下去，直到所有頂點在同一連通分量上為止

舉例

總結(jié)

以上是生活随笔為你收集整理的一文带你弄懂普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。