14.7克魯斯卡爾算法
內(nèi)容來自尚硅谷Java數(shù)據(jù)結(jié)構(gòu)與java算法（Java數(shù)據(jù)結(jié)構(gòu)與算法）_嗶哩嗶哩_bilibili
寫在前面:本文內(nèi)容大致和原視頻內(nèi)老師的筆記內(nèi)容相同，會偶爾插入自己的注釋和理解，盡量會完成作業(yè)
這集看的我困的要命，從入門到放棄還真不是說著玩玩的...
14.7.1應用場景-公交站問題
看一個應用場景和問題
1)????? 某城市新增7個站點(A,B,C,D,E,F,G)，現(xiàn)在需要修路把7個站點連通
2)????? 各個站點的距離用邊線表示(權)，比如A-B距離12公里
3)????? 問:如何修路保證各個站點都能連通，并且總的修建公路總里程最短?
14.7.2克魯斯卡爾算法介紹
克魯斯卡爾(Kruskal)算法，是用來求加權連通圖的最小生成樹的算法。
基本思想:按照權值從小到大的順序選擇n-1條邊，并保證這n-1條邊不構(gòu)成回路
具體做法:首先構(gòu)造一個只含n個頂點的森林，然后依權值從小到大從連通網(wǎng)中選擇邊加入到森林中，并使森林中不產(chǎn)生回路，直至森林變成一棵樹為止
14.7.3克魯斯卡爾算法圖解說明
以城市公交站問題來圖解說明克魯斯卡爾算法的原理和步驟:
在含有n個頂點的連通圖中選擇n-1條邊，構(gòu)成一棵極小連通子圖，并使該連通子圖中n-1條邊上權值之和達到最小，則稱其為連通網(wǎng)的最小生成樹。
例如，對于如上圖G4所示的連通網(wǎng)可以有多棵權值總和不相同的生成樹。
克魯斯卡爾算法圖解
以上圖G4為例，來對克魯斯卡爾進行演示(假設，用數(shù)組R保存最小生成樹結(jié)果)。
第1步:將邊<E,F>加入R中。
邊<E,F>的權值最小，因此將它加入到最小生成樹結(jié)果R中。
第2步:將邊<C,D>加入R中。
上一步操作之后，邊<C,D>的權值最小，因此將它加入到最小生成樹結(jié)果R中。
第3步:將邊<D,E>加入R中。
上一步操作之后，邊<D,E>的權值最小，因此將它加入到最小生成樹結(jié)果R中。
第4步:將邊<B,F>加入R中。
上一步操作之后，邊<C,E>的權值最小，但<C,E>會和己有的邊構(gòu)成回路;因此，跳過邊<C,E>。同理，跳過邊<C,F>。將邊<B,F>加入到最小生成樹結(jié)果R中。
第5步:將邊<E,G>加入R中。
上一步操作之后，邊<E,G>的權值最小，因此將它加入到最小生成樹結(jié)果R中
此時，最小生成樹構(gòu)造完成!它包括的邊依次是:<E,F><C,D><D,E><B,F> <E,G> <A,B>。
克魯斯卡爾算法分析
根據(jù)前面介紹的克魯斯卡爾算法的基本思想和做法，我們能夠了解到，克魯斯卡爾算法重點需要解決的以下兩個問題:
問題一對圖的所有邊按照權值大小進行排序。
問題二將邊添加到最小生成樹中時，怎么樣判斷是否形成了回路。
問題一很好解決，采用排序算法進行排序即可。
問題二，處理方式是:記錄頂點在"最小生成樹"中的終點，頂點的終點是"在最小生成樹中與它連通的最大頂點"。然后每次需要將一條邊添加到最小生存樹時，判斷該邊的兩個頂點的終點是否重合，重合的話則會構(gòu)成回路。
如何判斷是否構(gòu)成回路–舉例說明（如圖)
在將<E,F><C,D><D,E>加入到最小生成樹R中之后，這幾條邊的頂點就都有了終點:
(01)C的終點是F。
(02)D的終點是F。
(03)E的終點是F。
(04)F的終點是F。
?
關于終點的說明:
1)就是將所有頂點按照從小到大的順序排列好(A-B-C-C-D-E-F-G)之后;某個頂點的終點就是"與它連通的最大頂點"。
比如上圖中C-D-E-F,F在排序中是最靠后的，所以是最大的，所以，在CDEF這條線的任意節(jié)點上出發(fā)，最終都會走到F,所以F是終點
2)因此，接下來，雖然<C,E>是權值最小的邊。但是C和E的終點都是F，即它們的終點相同，因此，將<C,E>加入最小生成樹的話，會形成回路。這就是判斷回路的方式。也就是說，我們加入的邊的兩個頂點不能都指向同一個終點，否則將構(gòu)成回路?！竞竺嬗写a說明】
14.7.4克魯斯卡爾最佳實踐-公交站問題
看一個公交站問題:
1)????? 有北京有新增7個站點(A,B,C, D, E,F,G)，現(xiàn)在需要修路把7個站點連通
2)????? 各個站點的距離用邊線表示(權)，比如A - B距離12公里
3)????? 問:如何修路保證各個站點都能連通，并且總的修建公路總里程最短?
4)????? 代碼實現(xiàn)
還以為不能給文字換顏色呢，原來可以，我果然還是太菜了
