數(shù)據(jù)結(jié)構(gòu)(五) 普利姆與克魯斯卡爾的最小生成樹（Swift面向?qū)ο蟀妫?/a>

上篇博客我們聊了圖的物理存儲(chǔ)結(jié)構(gòu)鄰接矩陣和鄰接鏈表，然后在此基礎(chǔ)上給出了圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。本篇博客就在上一篇博客的基礎(chǔ)上進(jìn)行延伸，也是關(guān)于圖的。今天博客中主要介紹兩種算法，都是關(guān)于最小生成樹的，一種是Prim算法，另一個(gè)是Kruskal算法。這兩種算法是很經(jīng)典的，也是圖中比較重要的算法了。

今天博客會(huì)先聊一聊Prim算法是如何生成最小生成樹的，然后給出具體步驟的示例圖，最后給出具體的代碼實(shí)現(xiàn)，并進(jìn)行測(cè)試。當(dāng)然Kruskal算法也是會(huì)給出具體的示例圖，然后給出具體的代碼和測(cè)試用例。當(dāng)然本篇博客中的Demo是在上篇博客的基礎(chǔ)上進(jìn)行實(shí)現(xiàn)的。因?yàn)樵谏掀┛椭形覀円呀?jīng)創(chuàng)建好了現(xiàn)成的圖了，本篇博客就拿過來直接使用。

在本篇博客的開頭呢，先簡(jiǎn)單的聊一下什么是最小生成樹。最小生成樹是原圖的最小連通子圖，也就是說該子圖是連通的并且沒有多余的邊，更不會(huì)形成回路。最重要的是最小生成樹的所有邊的權(quán)值相加最小，這也是最小生成樹的來源。與現(xiàn)實(shí)生活中聯(lián)系起來那就是一些村莊要通電話線，如何讓每個(gè)村都可以通電話線并且最省材料。換句話說，是每個(gè)村莊連通，并且總線路最短，如果線連接完畢后，其實(shí)就是我們本篇博客要聊的最小生成樹。

 

一、普利姆算法

接下來我們就來聊Prim算法。其實(shí)Prim算法創(chuàng)建最小生成樹的主要思路就是從候選節(jié)點(diǎn)中選擇最小的權(quán)值添加到最小生成樹中。下圖是我們之前創(chuàng)建的圖使用Prim算法創(chuàng)建最小生成樹的完整過程。紅色的邊就是每一步所對(duì)應(yīng)的候選節(jié)點(diǎn)做連的弧，從這些候選的邊中選出權(quán)值最小的邊添加到最小生成樹中，我們可以將其視為轉(zhuǎn)正的過程。

一個(gè)節(jié)點(diǎn)轉(zhuǎn)正后，將其轉(zhuǎn)正節(jié)點(diǎn)所連的弧度視為候選弧度，當(dāng)然這些候選弧度所連的節(jié)點(diǎn)必須是最小生成樹上以外的點(diǎn)。如果候選弧度所連的點(diǎn)位于最小生成樹上，那么將該候選節(jié)點(diǎn)拋棄。直到無候選弧度時(shí)，最小生成樹的創(chuàng)建就完成了。

下圖就很好的表述了這個(gè)過程，每一步候選節(jié)點(diǎn)間的連接使用紅色標(biāo)記，而轉(zhuǎn)正的節(jié)點(diǎn)間的弧度使用黑色表示。按照下方這個(gè)思路，最終就會(huì)生成我們需要的最小生成樹。

1.Prim算法示意圖解析

 

  • （0）：就是我們上篇博客所創(chuàng)建的圖的結(jié)構(gòu)，并且每條弧度都有權(quán)值。