一、先再次明確關(guān)于圖的幾個(gè)概念定義：

• 連通圖：在無(wú)向圖中，若任意兩個(gè)頂點(diǎn)vivi與vjvj都有路徑相通，則稱該無(wú)向圖為連通圖。
• 強(qiáng)連通圖：在有向圖中，若任意兩個(gè)頂點(diǎn)vivi與vjvj都有路徑相通，則稱該有向圖為強(qiáng)連通圖。
• 連通網(wǎng)：在連通圖中，若圖的邊具有一定的意義，每一條邊都對(duì)應(yīng)著一個(gè)數(shù)，稱為權(quán)；權(quán)代表著連接連個(gè)頂點(diǎn)的代價(jià)，稱這種連通圖叫做連通網(wǎng)。
• 生成樹：一個(gè)連通圖的生成樹是指一個(gè)連通子圖，它含有圖中全部n個(gè)頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-1條邊。一顆有n個(gè)頂點(diǎn)的生成樹有且僅有n-1條邊，如果生成樹中再添加一條邊，則必定成環(huán)。
• 最小生成樹：在連通網(wǎng)的所有生成樹中，所有邊的代價(jià)和最小的生成樹，稱為最小生成樹。
  

二、Kruskal算法

此算法可以稱為“加邊法”，初始最小生成樹邊數(shù)為0，每迭代一次就選擇一條滿足條件的最小代價(jià)邊，加入到最小生成樹的邊集合里。

把圖中的所有邊按代價(jià)從小到大排序；

把圖中的n個(gè)頂點(diǎn)看成獨(dú)立的n棵樹組成的森林；

按權(quán)值從小到大選擇邊，所選的邊連接的兩個(gè)頂點(diǎn)ui,viui,vi,應(yīng)屬于兩顆不同的樹，則成為最小生成樹的一條邊，并將這兩顆樹合并作為一顆樹。

重復(fù)(3),直到所有頂點(diǎn)都在一顆樹內(nèi)或者有n-1條邊為止。

示意圖：

動(dòng)態(tài)圖：

三、Prim算法

此算法可以稱為“加點(diǎn)法”，每次迭代選擇代價(jià)最小的邊對(duì)應(yīng)的點(diǎn)，加入到最小生成樹中。算法從某一個(gè)頂點(diǎn)s開(kāi)始，逐漸長(zhǎng)大覆蓋整個(gè)連通網(wǎng)的所有頂點(diǎn)。

1.圖的所有頂點(diǎn)集合為V；初始令集合u={s},v=V?u；
2.在兩個(gè)集合u,v能夠組成的邊中，選擇一條代價(jià)最小的邊(u0,v0)，加入到最小生成樹中，并把v0并入到集合u中。
3.重復(fù)上述步驟，直到最小生成樹有n-1條邊或者n個(gè)頂點(diǎn)為止。

示意圖：

動(dòng)態(tài)圖：

參考文章
參考視頻

總結(jié)

以上是生活随笔為你收集整理的最小生成树（Kruskal和Prim算法）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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