求最小樹的Kruskal算法中無圈判斷的進一步思考

宋慧敏 孫薇 吳建良

【摘要】在實際應用中，我們常碰到實現(xiàn)最小連接的問題，這就歸結到最小樹問題.最小樹問題在運籌學、圖論、數(shù)據(jù)結構等課程都有涉及.解決最小樹問題的算法有Kruskal算法和Prim算法等.Kruskal算法的思想是在不構成圈的前提下盡可能選權最小的邊.其中考察邊和已選的邊集是否構成圈是影響算法復雜性的關鍵一步.本文先介紹實現(xiàn)無圈判斷的標號方法，分析其本質需求，進而引入根樹方法，并給出進一步改進的思路.本文從運籌學教學的角度闡述教學內容，有意識地引導學生進行深入思考，提升學生進行自主學習的意識和能力.

【關鍵詞】最小樹;Kruskal算法;并查集;根樹

【基金項目】山東大學（威海）重點教改項目《科研反哺教學的研究與實踐》：A201805;山東大學（威海）教研項目《經(jīng)管類探索性數(shù)學實驗案例教學研究》：B201816

在實際應用中，我們常碰到實現(xiàn)最小連接的問題，例如交通網(wǎng)、電力網(wǎng)、電話網(wǎng)、管道網(wǎng)等網(wǎng)絡設計，這些應用問題簡而言之，即如何用最小的成本將一些對象連接起來.若把這些需要連接的對象對應一個個點（稱為頂點），若兩個對象能夠直接建立聯(lián)系（比如架設電線），則在對應的兩點之間連一條線（稱為邊），兩者建立聯(lián)系的代價（比如架設電線成本）則為對應邊的權.這樣實際問題就以賦權圖（也稱網(wǎng)絡）的形式展現(xiàn)出來，實際需求也就變成在對應網(wǎng)絡里找最小權的連通所有頂點的子圖（稱為連通支撐子圖）.最小連接問題可以轉化為最小樹問題，該問題在大學的許多課程中都有涉及，如運籌學、圖論、組合優(yōu)化、數(shù)據(jù)結構等.最小樹問題在運籌學課程中屬于網(wǎng)絡優(yōu)化部分.用網(wǎng)絡分析的語言可以如下敘述該問題：給定一個賦權網(wǎng)絡，找一個最小權的連通支撐子圖.我們知道在所有邊權非負的情況下，一定有一個支撐樹，達到總權值最小.所以找最小權的連通支撐子圖就是找最小權的支撐樹（簡稱最小樹），最小連接問題就是最小樹問題.從算法復雜性的角度而言，最小樹問題是簡單問題，有多項式時間算法.現(xiàn)實中很多問題可以轉化為網(wǎng)絡優(yōu)化問題，對它們的求解常常要用到最小樹算法.最小樹算法因其理論和應用價值，教師對其算法進行研究以及對學生進行知識的傳授都是非常有意義的工作.

在大部分課程內容中，求解最小樹問題都是貪心算法，如Kruskal算法和Prim算法.這些貪心算法能在多項式時間內找到最小樹.Kruskal算法的時間復雜度為O（mlog n），Prim算法的時間復雜度為O（n2），其中m表示網(wǎng)絡中的邊數(shù)，n表示網(wǎng)絡的頂點數(shù).很顯然，在頂點數(shù)大、邊數(shù)相對較小的網(wǎng)絡（即稀疏網(wǎng)絡）中，Kruskal算法更勝一籌.本文就從運籌學教學的角度，介紹Kruskal算法，重點講述其無圈判斷的實現(xiàn)方法，通過算例演示使學生能較容易地掌握知識內容，又通過目的導向，引導學生深入思考，進而激發(fā)學生的研究興趣.

Kruskal算法是一種貪心算法，其思想很簡單，就是在所選邊不構成圈的前提下依次選擇權值最小的邊.設給定網(wǎng)絡G=（V，E;W），其中E和V分別是圖（即所給網(wǎng)絡）的邊集和點集，W是定義在邊集上的權值函數(shù).令m=|E|，n=|V|，下面算法中，用S存放依次選中的邊，|S|≤n-1.算法結束時，若|S|=n-1，則G[S]為最小樹;否則，G[S]為最小權支撐森林.

求最小樹的Kruskal算法的步驟如下.

第1步，把G中的邊按權由小到大排列為a1，a2，…，am，即w（a1）≤w（a2）≤…≤w（am）.令i：=0，j：=0，S：=Φ.

第2步，令j：=j+1.若j>m，則該網(wǎng)絡不連通，網(wǎng)絡的最小樹不存在，算法停止;否則，轉第3步.

第3步，考察邊aj.若G[S∪{aj}]不含圈，則令ei+1：=aj，S：=S∪{ei+1}，i：=i+1.若i=n-1，則G[S]即為所求，算法停止;否則，轉向第2步.

令T記頂點集為V、邊集為S的圖，運算進程中，T一直是森林.算法開始，T中無邊為空圖.順次考察邊a1，a2，...，am，當考察到aj時，若aj與以前選中的邊不構成圈，即T+aj仍是森林，則選中aj，開始考察下一條邊，接下來T改變，變成T+aj;若aj與以前選中的邊構成圈，即T+aj不是森林，則拋棄aj開始考察下一條邊，接下來T不變.考察G[S∪{aj}]是否含圈，也就是判斷T+aj是不是森林，只需看aj的兩個端點是否包含在T的同一個分支.下面我們用一個簡單的例子說明該算法.

例1 用Kruskal算法求解圖1所示網(wǎng)絡的最小樹，其中每條邊上的數(shù)表示該邊的權值.

解 該圖頂點數(shù)n=5，邊數(shù)m=8.按照邊權排序為：a1=（1，2），a2=（1，3），a3=（2，3），a4=（4，5），a5=（2，5），a6=（2，4），a7=（3，4），a8=（3，5）.

先考慮a1，不構成圈，選中;再考慮a2，與已選中的a1不構成圈，選中;再考慮a3，與已選中的a1，a2構成圈，棄之.再考慮a4，與已選中的a1，a2不構成圈，選中.再考慮a5，與已選中的a1，a2，a4不構成圈，選中.至此，選中的邊集為S={a1，a2，a4，a5}，選中的邊數(shù)為|S|=m-1=4，得到最小樹.算法過程如圖2所示，圖2中最后的圖就是最小樹，權和為8.

從該例可看出算法很簡單，手算很容易.但是由于大型網(wǎng)絡，用手算不現(xiàn)實，必須用計算機程序實現(xiàn).如何實現(xiàn)每一步驟，就是編程面臨的問題.不同的實現(xiàn)方式導致算法的復雜性不同，網(wǎng)絡規(guī)模越大，越能顯示出效率不同.算法第1步要對m條邊根據(jù)邊權從小到大排序，常用的冒泡排序法的時間復雜度為O（mlog m）.第2步?jīng)]有技術含量.第3步就是我們考慮的重點了.第3步在考察邊aj時，要判斷G[S∪{aj}]是否含圈，只需檢查aj的兩個端點是否包含T的同一個分支.換句話說，就是檢查aj的兩個端點在T中是否連通（即檢查連通性）.接下來，若選中aj，T改變，aj的兩個端點所在的兩個分支要合二為一（即合并連通點）.

第3步要實現(xiàn)合并連通點（簡稱“并”）和查詢連通性（簡稱“查”）兩個功能.這兩個功能對應數(shù)據(jù)結構課程中的并查集概念.并查集可以高效解決動態(tài)連通性.下面就先從標號方法開始介紹，然后是根樹方法，最后介紹根樹方法的改進思路，由淺入深地介紹并查集的幾種實現(xiàn)方式.

標號方法顧名思義是利用頂點標號來實現(xiàn)“并”和“查”兩個功能.標號方法需要用一個數(shù)組B[1：n]記錄每一個頂點的標號，兩頂點標號相同當且僅當兩頂點在同一分支.初始狀態(tài)T是空圖，每個頂點自成一個分支（或稱子樹），所以頂點的初始標號可以等于它的編號，即B[i]：=i.當算法第3步考察到aj時，會出現(xiàn)兩種情況.情況一，aj兩端點標號相同（即兩端點在T中連通），則aj不被選擇.算法轉第2步，考察邊計數(shù)變量j加1，再轉向算法第3步，即相當于考察下一條邊aj+1.情況二，aj兩端點的標號不相同（即兩端點在T中不連通），則表示aj連接T中不同子樹，T+aj自然不含圈，則aj被選中，選中邊計數(shù)變量i加1，即ei+1=aj.這就完成了“查”的功能.

算法第3步aj被選中后，T改變（置換成T+aj），連通性發(fā)生了改變.準確地說，aj的兩個端點（不妨設為u，v）在原來T中不連通，分別在兩個不同的分支，不妨設u所在分支為Tu，v所在分支為Tv.在T+aj中，Tu和Tv因aj連接為一個分支.標號方法要求同分支頂點標號相同，所以要在下一次“查”操作之前實現(xiàn)“并”功能.很自然的一種想法就是把一個分支的所有頂點標號全換成另一個分支頂點的標號.顯然B[u]≠B[v]，不妨設B[u]>B[v].搜索Tu，識別Tu中的所有頂點，將它的標號都修改為B[v].這個工作可以通過在原來的圖T（邊數(shù)小于n）中用DFS或BFS找出與u連通的頂點來實現(xiàn)，該步驟的時間復雜度為O（n），至多重復m次.這樣整個算法的時間復雜度為O（mlog m）+O（mn）=O（mn）.

我們在圖3中給出例1的標號過程，圖中頂點上的數(shù)字為對應頂點的標號.

實現(xiàn)“并”“查”兩種功能的方法不同，則會導致算法的時間復雜性不同.上述標號方法的本質是把每一分支的所有頂點都標號為該分支頂點的最小編號.當G連通時，最后所有頂點的標號都為1.如果我們把每一分支的標號等于編號的頂點看成該子樹的根，則每個頂點的標號就是其所在子樹的根（稱為頂點的根）的編號.從這個角度來看，標號方法的“查”操作就是通過比較考察邊兩端點的根是否相同來實現(xiàn)的，“并”操作也可以看成考察邊一個端點所在分支的所有頂點都成了另一個端點的子孫，從而使合并后的分支擁有同一個根.我們還發(fā)現(xiàn)，只要這些分支（子樹）的頂點集合確定，子樹內部的不同連接方式不會影響“并”“查”操作的結果.基于這些思考，我們保證每一分支頂點集合不變，且保持樹的特性，將分支對應的頂點集合換一種方式連接，看是否能夠降低“并”“查”操作的時間復雜度.根據(jù)這個思路將標號算法修改，可得到根樹算法.

根樹算法是用帶根子樹族B中的每棵帶根子樹來對應T=（V，S）中的每個分支，這里B的每棵子樹和T=（V，S）對應的分支頂點集合相同，但邊集不一定相同.T=（V，S）和B的連通分支有一一對應關系，所以可以用B替代T=（V，S）來實現(xiàn)“并”“查”操作.可以用數(shù)組Father[1：n]來記錄每個頂點的父親，一開始可以把每個頂點i的父親記為i，即Father[i]：=i，也就是每個頂點都是一棵子樹，該頂點的根就是它自身.當我們考察aj=（u，v）時，分別找u，v的根ru，rv，這項工作可以通過在B中往上順序追尋節(jié)點的父親得到.若令h（r）為B中根為r的子樹中r到其子孫的最長路長，則該步驟的時間復雜度分別為O（h（ru）），O（h（rv））.若ru=rv，則表示u，v在T的同一個分支，aj不被選擇.若ru≠rv，則表示u，v不在同一個分支，則選擇aj.這樣完成了“查”的功能.若h（ru）≤h（rv），令Father（ru）：=rv.文獻[2]中用數(shù)學歸納法證明了根為r的子樹中至少含有2h（r）個頂點，所以h（r）≤log n.任一r的子孫找到r只需h（r）步，這樣用根樹算法處理Kruskal算法的第3步需要的時間復雜度是O（mlog n），所以Kruskal算法的時間復雜度就是O（mlog m）+O（mlog n）=O（mlog n）.

圖4給出例1對應的根樹序列，每個分支里只作為出發(fā)點的節(jié)點是對應根樹的根，可以看出根樹和對應子樹連接方式不同.拿最后一次迭代中支撐樹和根樹進行比較，支撐樹中的最大路長是4，而對應根樹的最大有向路長是2，所以根樹方法比標號方法在搜索方面更快捷.

從上面的分析可以看出，根樹方法的時間復雜度取決于樹的高度.要想降低時間復雜度，就要想辦法壓縮樹高.改變根樹連接方式，壓縮樹高的方法是不唯一的.下面我們給出其中的幾種嘗試方向.在算法第3步考查aj=（u，v）時，我們要找u，v的根ru，rv，也就是分別在u，v所在的根樹里向上追溯祖先.一種方法，在搜索過程中分別記錄（u，ru）-路和（v，rv）-路的中間節(jié)點，令它們的父親都為它們對應的根節(jié)點.這樣操作有很大可能使根樹的樹高不超過2，是壓縮樹高的一種有效方式.在找到根節(jié)點之前，路上的中間節(jié)點都需要存儲，而存儲空間變大，是會增加空間復雜度的.空間復雜度是對算法評價的另一個指標，這在實際算法設計和編程中也是需要考慮的一種因素.另一種方法，在尋根過程中每遍歷到一個節(jié)點，就把該節(jié)點變成它爺爺節(jié)點的孩子，也就是和它的父節(jié)點在一層了.這樣通過頻繁的查詢會導致樹的“扁平化”程度更徹底.用這種方式壓縮樹高沒有上一種方式力度那么大，但優(yōu)點在于存儲空間可以有效利用.通過這些大小樹合并和樹壓縮的技巧，“并”“查”兩種操作的時間復雜性會非常趨近O（1）.這樣，Kruskal算法第3步的時間復雜性幾乎是線性的.

在數(shù)據(jù)結構等課程教學中也常涉及最小樹的算法實現(xiàn)，其中也有利用Fibonacci堆的處理方法，這里就不一一介紹了.作為教師，我們應意識到即使課程中的簡單問題也有值得深入挖掘之處，對教學的投入能夠促進科研方面的發(fā)展.深入研究教學資料，充分備課，在教學過程中有意識地引導學生深入思考，能夠提升學生自主學習的意識和能力.作為高校教師，要教學科研兩不誤，努力為國家培養(yǎng)高素質創(chuàng)新型人才.

【參考文獻】

[1]刁在筠，劉桂真，戎曉霞，等.運籌學：第四版[M].北京：高等教育出版社，2016.

[2] Bernhard Korte，Jens Vygen.Combinatorial Optimization： Theory and Algorithms：Fifth Edition[M].Springer，2011.

[3]Tarjan R E，Data Structures and Network Algorithms[J].SIAM，Philadelphia，1983.

[4]Tarjan R E，Effificiency of a good but not linear set union algorithm[J].Journal of the ACM，1975（22）：215-225.