內(nèi)容來(lái)自:尚硅谷Java數(shù)據(jù)結(jié)構(gòu)與java算法（Java數(shù)據(jù)結(jié)構(gòu)與算法）_嗶哩嗶哩_bilibili

寫在前面:本文內(nèi)容大致和原視頻內(nèi)老師的筆記內(nèi)容相同，會(huì)偶爾插入自己的注釋和理解，盡量會(huì)完成作業(yè)

14.6普利姆算法

14.6.1應(yīng)用場(chǎng)景-修路問(wèn)題

看一個(gè)應(yīng)用場(chǎng)景和問(wèn)題

有勝利鄉(xiāng)有7個(gè)村莊(A,B,C,D,E,F,G)，現(xiàn)在需要修路把7個(gè)村莊連通各個(gè)村莊的距離用邊線表示(權(quán))，比如A-B距離5公里

問(wèn):如何修路保證各個(gè)村莊都能連通，并且總的修建公路總里程最短?

思路:將10條邊,連接即可，但是總的里程數(shù)不是最小

正確的思路，就是盡可能的選擇少的路線，并且每條路線最小，保證總里程數(shù)最少.

?

14.6.2最小生成樹(shù)

修路問(wèn)題本質(zhì)就是最小生成樹(shù)問(wèn)題，先介紹一下最小生成樹(shù)(Minimum Cost Spanning Tree)，簡(jiǎn)稱MST.

1)????? 給定一個(gè)帶權(quán)的無(wú)向連通圖,如何選取一棵生成樹(shù),使樹(shù)上所有邊上權(quán)的總和為最小,這叫最小生成樹(shù)

2)????? N個(gè)頂點(diǎn)，一定有N-1條邊

3)????? 包含全部頂點(diǎn)

4)????? N-1條邊都在圖中

5)????? 舉例說(shuō)明(如圖:)

6)????? 求最小生成樹(shù)的算法主要是普里姆算法和克魯斯卡爾算法

14.6.3普利姆算法的介紹

前排提示：這段話不要看，看不懂的

普利姆(Prim)算法求最小生成樹(shù)，也就是在包含n個(gè)頂點(diǎn)的連通圖中，找出只有(n-1)條邊包含所有n個(gè)頂點(diǎn)的連通子圖，也就是所謂的極小連通子圖

普利姆的算法如下:

1)????? 設(shè)G=(V,E)是連通網(wǎng)，T=(U,D)是最小生成樹(shù)，V,U是頂點(diǎn)集合，E,D是邊的集合

2)????? 若從頂點(diǎn)u開(kāi)始構(gòu)造最小生成樹(shù)，則從集合V中取出頂點(diǎn)u放入集合U中，標(biāo)記頂點(diǎn)v的visited[u]=1

3)????? 若集合U中頂點(diǎn)ui與集合V-U中的頂點(diǎn)vj之間存在邊，則尋找這些邊中權(quán)值最小的邊，但不能構(gòu)成回路，將頂點(diǎn)vj加入集合U中，將邊(ui,vj)加入集合D中，標(biāo)記visited[vj]=1

4)????? 重復(fù)步驟②，直到U與V相等，即所有頂點(diǎn)都被標(biāo)記為訪問(wèn)過(guò)，此時(shí)D中有n-1條邊

5)????? 提示:單獨(dú)看步驟很難理解，我們通過(guò)代碼來(lái)講解，比較好理解.

圖解

//看這個(gè)圖解配合和視頻，有點(diǎn)反向貪心算法的感覺(jué)

14.6.4普里姆算法最佳實(shí)踐(修路問(wèn)題)

1)????? 有勝利鄉(xiāng)有7個(gè)村莊(A,B,C, D,E, F,G)，現(xiàn)在需要修路把7個(gè)村莊連通

2)????? 各個(gè)村莊的距離用邊線表示(權(quán))，比如A-B距離5公里

3)????? 問(wèn):如何修路保證各個(gè)村莊都能連通，并且總的修建公路總里程最短?

4)????? 看老師思路分析+代碼演示:

學(xué)就完事了，加油！奧里給！