最小生成樹

在含有n個頂點的連通圖中選擇n-1條邊，構(gòu)成一棵極小連通子圖，并使該連通子圖中n-1條邊上權值之和達到最小，則稱其為連通網(wǎng)的最小生成樹。

例如，對于如上圖G4所示的連通網(wǎng)可以有多棵權值總和不相同的生成樹。

克魯斯卡爾算法介紹

克魯斯卡爾(Kruskal)算法，是用來求加權連通圖的最小生成樹的算法。

基本思想：按照權值從小到大的順序選擇n-1條邊，并保證這n-1條邊不構(gòu)成回路。

具體做法：首先構(gòu)造一個只含n個頂點的森林，然后依權值從小到大從連通網(wǎng)中選擇邊加入到森林中，并使森林中不產(chǎn)生回路，直至森林變成一棵樹為止。

克魯斯卡爾算法圖解

以上圖G4為例，來對克魯斯卡爾進行演示(假設，用數(shù)組R保存最小生成樹結(jié)果)。

第1步：將邊加入R中。

邊的權值最小，因此將它加入到最小生成樹結(jié)果R中。

第2步：將邊加入R中。

上一步操作之后，邊的權值最小，因此將它加入到最小生成樹結(jié)果R中。

第3步：將邊加入R中。

上一步操作之后，邊的權值最小，因此將它加入到最小生成樹結(jié)果R中。

第4步：將邊加入R中。

上一步操作之后，邊的權值最小，但會和已有的邊構(gòu)成回路；因此，跳過邊。同理，跳過邊。將邊加入到最小生成樹結(jié)果R中。

第5步：將邊加入R中。

上一步操作之后，邊的權值最小，因此將它加入到最小生成樹結(jié)果R中。

第6步：將邊加入R中。

上一步操作之后，邊的權值最小，但會和已有的邊構(gòu)成回路；因此，跳過邊。同理，跳過邊。將邊加入到最小生成樹結(jié)果R中。

此時，最小生成樹構(gòu)造完成！它包括的邊依次是： 。

克魯斯卡爾算法分析

根據(jù)前面介紹的克魯斯卡爾算法的基本思想和做法，我們能夠了解到，克魯斯卡爾算法重點需要解決的以下兩個問題：

問題一 對圖的所有邊按照權值大小進行排序。

問題二 將邊添加到最小生成樹中時，怎么樣判斷是否形成了回路。

問題一很好解決，采用排序算法進行排序即可。

問題二，處理方式是：記錄頂點在'最小生成樹'中的終點，頂點的終點是'在最小生成樹中與它連通的最大頂點'(關于這一點，后面會通過圖片給出說明)。然后每次需要將一條邊添加到最小生存樹時，判斷該邊的兩個頂點的終點是否重合，重合的話則會構(gòu)成回路。 以下圖來進行說明：

在將 加入到最小生成樹R中之后，這幾條邊的頂點就都有了終點：

(01) C的終點是F。

(02) D的終點是F。

(03) E的終點是F。

(04) F的終點是F。

關于終點，就是將所有頂點按照從小到大的順序排列好之后；某個頂點的終點就是'與它連通的最大頂點'。 因此，接下來，雖然是權值最小的邊。但是C和E的重點都是F，即它們的終點相同，因此，將加入最小生成樹的話，會形成回路。這就是判斷回路的方式。