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