上篇博客我們聊了圖的物理存儲(chǔ)結(jié)構(gòu)鄰接矩陣和鄰接鏈表，然后在此基礎(chǔ)上給出了圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。本篇博客就在上一篇博客的基礎(chǔ)上進(jìn)行延伸，也是關(guān)于圖的。今天博客中主要介紹兩種算法，都是關(guān)于最小生成樹(shù)的，一種是Prim算法，另一個(gè)是Kruskal算法。這兩種算法是很經(jīng)典的，也是圖中比較重要的算法了。
今天博客會(huì)先聊一聊Prim算法是如何生成最小生成樹(shù)的，然后給出具體步驟的示例圖，最后給出具體的代碼實(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)成的圖了，本篇博客就拿過(guò)來(lái)直接使用。
在本篇博客的開(kāi)頭呢，先簡(jiǎn)單的聊一下什么是最小生成樹(shù)。最小生成樹(shù)是原圖的最小連通子圖，也就是說(shuō)該子圖是連通的并且沒(méi)有多余的邊，更不會(huì)形成回路。最重要的是最小生成樹(shù)的所有邊的權(quán)值相加最小，這也是最小生成樹(shù)的來(lái)源。與現(xiàn)實(shí)生活中聯(lián)系起來(lái)那就是一些村莊要通電話線，如何讓每個(gè)村都可以通電話線并且最省材料。換句話說(shuō)，是每個(gè)村莊連通，并且總線路最短，如果線連接完畢后，其實(shí)就是我們本篇博客要聊的最小生成樹(shù)。
一、普利姆算法
接下來(lái)我們就來(lái)聊Prim算法。其實(shí)Prim算法創(chuàng)建最小生成樹(shù)的主要思路就是從候選節(jié)點(diǎn)中選擇最小的權(quán)值添加到最小生成樹(shù)中。下圖是我們之前創(chuàng)建的圖使用Prim算法創(chuàng)建最小生成樹(shù)的完整過(guò)程。紅色的邊就是每一步所對(duì)應(yīng)的候選節(jié)點(diǎn)做連的弧，從這些候選的邊中選出權(quán)值最小的邊添加到最小生成樹(shù)中，我們可以將其視為轉(zhuǎn)正的過(guò)程。
延伸閱讀
- ssh框架 2016-09-30
- 阿里移動(dòng)安全 [無(wú)線安全]玩轉(zhuǎn)無(wú)線電——不安全的藍(lán)牙鎖 2017-07-26
- 消息隊(duì)列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26
- Selective Search for Object Recognition 論文筆記【圖片目標(biāo)分割】 2017-07-26
- 詞向量-LRWE模型-更好地識(shí)別反義詞同義詞 2017-07-26
- 從棧不平衡問(wèn)題 理解 calling convention 2017-07-26
- php imagemagick 處理 圖片剪切、壓縮、合并、插入文本、背景色透明 2017-07-26
- Swift實(shí)現(xiàn)JSON轉(zhuǎn)Model - HandyJSON使用講解 2017-07-26
- 阿里移動(dòng)安全 Android端惡意鎖屏勒索應(yīng)用分析 2017-07-26
- 集合結(jié)合數(shù)據(jù)結(jié)構(gòu)來(lái)看看(二) 2017-07-26
學(xué)習(xí)是年輕人改變自己的最好方式