正文之前
在介紹最小生成樹(shù)之前嵌灰，需要先介紹一下生成樹(shù)的概念：
一棵樹(shù) T问词，如果包含一個(gè)連通無(wú)向圖G中的所有頂點(diǎn)，則稱(chēng) T 為圖G的生成樹(shù)恨豁，一般情況下咐鹤，圖G的生成樹(shù)不止一棵。
本節(jié)將介紹以下內(nèi)容：
尋找生成樹(shù)（廣度/深度優(yōu)先搜索）
尋找最小生成樹(shù)（Prim/Kruskal算法）
正文
尋找生成樹(shù)(Spanning Trees)
1. 廣度優(yōu)先搜索(Breadth-First-Search)
- 思想：首先處理在同一層次的所有結(jié)點(diǎn)圣絮，然后再處理下一層次的結(jié)點(diǎn)
舉例
我們先給結(jié)點(diǎn)排序：a,b,c,d,e,f,g,h
設(shè) a 為根結(jié)點(diǎn)，T只包含a
給T添加邊(a, x)
添加(a,b)
在結(jié)點(diǎn) b 的基礎(chǔ)上執(zhí)行第3步雕旨，添加(b, f), (b, c), (b, e)
在結(jié)點(diǎn) f, c, e 的基礎(chǔ)上扮匠，執(zhí)行第3步，添加(f, g), (c, d), (e, i)
在結(jié)點(diǎn) g, d, i 的基礎(chǔ)上凡涩，執(zhí)行第3步棒搜，添加(d, h)
在結(jié)點(diǎn) h 的基礎(chǔ)，沒(méi)有邊可添加活箕，過(guò)程結(jié)束力麸，生成樹(shù)已找到
2. 深度優(yōu)先搜索(Depth-First-Search)
- 思想：盡可能深入地搜索，到達(dá)盡頭后，沿著每條邊回到初始選定的結(jié)點(diǎn)克蚂，直到發(fā)現(xiàn)所有的結(jié)點(diǎn)闺鲸，又稱(chēng)為回溯法(backtracking)
還是以上圖為例：
我們先給結(jié)點(diǎn)排序：a,b,c,d,e,f,g,h
設(shè) a 為根結(jié)點(diǎn)，T只包含a
按照順序埃叭，增加邊(a, b), (b, c), (c, d), (d, e), (e, i), (i, h)
以結(jié)點(diǎn) h 為基礎(chǔ)摸恍，不能再增加邊，所以開(kāi)始回溯
回溯到結(jié)點(diǎn) c 赤屋，增加邊(c, g), (g, f)
以結(jié)點(diǎn) f 為基礎(chǔ)立镶，不能再增加邊，又開(kāi)始回溯
-
回溯到根結(jié)點(diǎn) a 类早，過(guò)程結(jié)束媚媒，生成樹(shù)已找到
算法的不同，就會(huì)導(dǎo)致尋找到的生成樹(shù)不同涩僻，所以缭召，如果一個(gè)圖含有生成樹(shù)，一般情況下不止一棵
尋找最小生成樹(shù)
在一個(gè)圖的所有生成樹(shù)中令哟，權(quán)值最小的樹(shù)被稱(chēng)為最小生成樹(shù)
打個(gè)比方恼琼，一個(gè)圖表示一個(gè)省，在省內(nèi)的各個(gè)市之間需要修建公路屏富，圖中的每條邊的權(quán)值表示修建這條公路的費(fèi)用晴竞，如何修建一條連貫各示且費(fèi)用最低的公路？狠半？
1. Prim算法
- 思想：樹(shù)的構(gòu)造從一個(gè)結(jié)點(diǎn)開(kāi)始噩死，不斷給樹(shù)加入邊，直到形成最小生成樹(shù)
根據(jù)這個(gè)圖神年，我們開(kāi)始演算：
我們假設(shè)初始結(jié)點(diǎn)為 a 已维，在樹(shù) T 中加入結(jié)點(diǎn) a
選擇與結(jié)點(diǎn) a 相關(guān)聯(lián)的權(quán)值最小的邊：(a, c)，將其加入 T
選擇與結(jié)點(diǎn) a 或結(jié)點(diǎn) c 相關(guān)聯(lián)的權(quán)值最小的邊：(c, b)已日，將其加入 T 垛耳，與結(jié)點(diǎn) a 有關(guān)聯(lián)的邊都已被選擇，所以不再考慮結(jié)點(diǎn) a
選擇與結(jié)點(diǎn) c 或結(jié)點(diǎn) b 相關(guān)聯(lián)的權(quán)值最小的邊：(b, g)飘千，將其加入 T
選擇與結(jié)點(diǎn) c 或結(jié)點(diǎn) b 或結(jié)點(diǎn) g 相關(guān)聯(lián)的權(quán)值最小的邊：(g, h)堂鲜，將其加入 T
選擇與結(jié)點(diǎn) c 或結(jié)點(diǎn) b 或結(jié)點(diǎn) g 或結(jié)點(diǎn) h 相關(guān)聯(lián)的權(quán)值最小的邊：(c, d)，將其加入 T 护奈，與結(jié)點(diǎn) b, c 有關(guān)聯(lián)的邊都已被選擇缔莲，所以不再考慮結(jié)點(diǎn) b, c
選擇與結(jié)點(diǎn) d 或結(jié)點(diǎn) g 或結(jié)點(diǎn) h 相關(guān)聯(lián)的權(quán)值最小的邊：(d, e)，將其加入 T
選擇與結(jié)點(diǎn) d 或結(jié)點(diǎn) g 或結(jié)點(diǎn) h 或結(jié)點(diǎn) e 相關(guān)聯(lián)的權(quán)值最小的邊：(e, f)霉旗，將其加入 T
所有結(jié)點(diǎn)已都在樹(shù)中痴奏，最小生成樹(shù)已找到蛀骇，權(quán)值為20，過(guò)程結(jié)束
2. Kruskal算法
- 思想：將圖中所有的邊按權(quán)值升序排列读拆，不斷選擇權(quán)值最小的邊加入樹(shù)中擅憔，直至所有結(jié)點(diǎn)都已在同一連通分量中
還是以這張圖為例：
將所有邊排序建椰，具體結(jié)果就不展示了
首先選擇邊(g, h)雕欺，權(quán)值為1，加入樹(shù) T
選擇邊(g, b)棉姐，權(quán)值為2屠列，加入 T
依次選擇邊(a, c), (c, b), (e, f), (d, e), (c, d)
所有的結(jié)點(diǎn)都已在同一連通分量中，最小生成樹(shù)已找到伞矩，權(quán)值為20笛洛，過(guò)程結(jié)束
重點(diǎn)
在選擇權(quán)值為4的邊時(shí)，如果選擇邊(a, b)乃坤，就會(huì)導(dǎo)致形成回路苛让，尋找失敗
在選擇權(quán)值為5的邊時(shí)，如果選擇邊(d, f)湿诊，就會(huì)導(dǎo)致形成回路狱杰，尋找失敗
這兩種方法找到了結(jié)構(gòu)相同的最小生成樹(shù)，證明此圖只有唯一的最小生成樹(shù)
關(guān)于最小生成樹(shù)的介紹就到此為止了厅须，謝謝仿畸！
