個(gè)人覺(jué)得這個(gè)博客把這個(gè)算法說(shuō)的比較詳細(xì)了，直接搬過(guò)來(lái)吧，我再闡述一遍的話沒(méi)有人家說(shuō)的好，還容易說(shuō)錯(cuò)。
==========================分割線之下摘自Sasuke_SCUT的blog==================================================
最小樹(shù)形圖，就是給有向帶權(quán)圖中指定一個(gè)特殊的點(diǎn)root，求一棵以root為根的有向生成樹(shù)T，并且T中所有邊的總權(quán)值最小。最小樹(shù)形圖的第一個(gè)算法是1965年朱永津和劉振宏提出的復(fù)雜度為O(VE)的算法。
判斷是否存在樹(shù)形圖的方法很簡(jiǎn)單，只需要以v為根作一次圖的遍歷就可以了，所以下面的算法中不再考慮樹(shù)形圖不存在的情況。
在所有操作開(kāi)始之前，我們需要把圖中所有的自環(huán)全都清除。很明顯，自環(huán)是不可能在任何一個(gè)樹(shù)形圖上的。只有進(jìn)行了這步操作，總算法復(fù)雜度才真正能保證是O(VE)。
首先為除根之外的每個(gè)點(diǎn)選定一條入邊，這條入邊一定要是所有入邊中最小的。現(xiàn)在所有的最小入邊都選擇出來(lái)了，如果這個(gè)入邊集不存在有向環(huán)的話，我們可以證明這個(gè)集合就是該圖的最小樹(shù)形圖。這個(gè)證明并不是很難。如果存在有向環(huán)的話，我們就要將這個(gè)有向環(huán)所稱(chēng)一個(gè)人工頂點(diǎn)，同時(shí)改變圖中邊的權(quán)。假設(shè)某點(diǎn)u在該環(huán)上，并設(shè)這個(gè)環(huán)中指向u的邊權(quán)是in[u]，那么對(duì)于每條從u出發(fā)的邊(u, i, w)，在新圖中連接(new, i, w)的邊，其中new為新加的人工頂點(diǎn); 對(duì)于每條進(jìn)入u的邊(i, u, w)，在新圖中建立邊(i, new, w-in[u])的邊。為什么入邊的權(quán)要減去in[u]，這個(gè)后面會(huì)解釋?zhuān)谶@里先給出算法的步驟。然后可以證明，新圖中最小樹(shù)形圖的權(quán)加上舊圖中被收縮的那個(gè)環(huán)的權(quán)和，就是原圖中最小樹(shù)形圖的權(quán)。
上面結(jié)論也不做證明了。現(xiàn)在依據(jù)上面的結(jié)論，說(shuō)明一下為什么出邊的權(quán)不變，入邊的權(quán)要減去in [u]。對(duì)于新圖中的最小樹(shù)形圖T，設(shè)指向人工節(jié)點(diǎn)的邊為e。將人工節(jié)點(diǎn)展開(kāi)以后，e指向了一個(gè)環(huán)。假設(shè)原先e是指向u的，這個(gè)時(shí)候我們將環(huán)上指向u的邊 in[u]刪除，這樣就得到了原圖中的一個(gè)樹(shù)形圖。我們會(huì)發(fā)現(xiàn)，如果新圖中e的權(quán)w'(e)是原圖中e的權(quán)w(e)減去in[u]權(quán)的話，那么在我們刪除掉in[u]，并且將e恢復(fù)為原圖狀態(tài)的時(shí)候，這個(gè)樹(shù)形圖的權(quán)仍然是新圖樹(shù)形圖的權(quán)加環(huán)的權(quán)，而這個(gè)權(quán)值正是最小樹(shù)形圖的權(quán)值。所以在展開(kāi)節(jié)點(diǎn)之后，我們得到的仍然是最小樹(shù)形圖。逐步展開(kāi)所有的人工節(jié)點(diǎn)，就會(huì)得到初始圖的最小樹(shù)形圖了。
如果實(shí)現(xiàn)得很聰明的話，可以達(dá)到找最小入邊O(E)，找環(huán) O(V)，收縮O(E)，其中在找環(huán)O(V)這里需要一點(diǎn)技巧。這樣每次收縮的復(fù)雜度是O(E)，然后最多會(huì)收縮幾次呢？由于我們一開(kāi)始已經(jīng)拿掉了所有的自環(huán)，我門(mén)可以知道每個(gè)環(huán)至少包含2個(gè)點(diǎn)，收縮成1個(gè)點(diǎn)之后，總點(diǎn)數(shù)減少了至少1。當(dāng)整個(gè)圖收縮到只有1個(gè)點(diǎn)的時(shí)候，最小樹(shù)形圖就不不用求了。所以我們最多只會(huì)進(jìn)行V-1次的收縮，所以總得復(fù)雜度自然是O(VE)了。由此可見(jiàn)，如果一開(kāi)始不除去自環(huán)的話，理論復(fù)雜度會(huì)和自環(huán)的數(shù)目有關(guān)。
========================分割線之上摘自Sasuke_SCUT的blog=====================================================

下面是朱劉算法的構(gòu)造圖


下面是POJ 3164的代碼