本節書摘來自華章計算機《程式設計解題政策》一書中的第1章，第1.2節,作者：吳永輝 王建德 更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。
設g=(v，e，ω)是連通的有權無向圖(節點集為v，邊集為e，邊權集為ω)，連通圖g中包含所有節點，且隻有v-1條邊的連通子圖即為g的生成樹。邊權值和最小的生成樹稱為最小生成樹。在現實生活中，最小生成樹的原理和算法有着廣泛的應用。程式設計競賽中與最小生成樹有關的試題一般有兩類：
1) 建構最小生成樹。
2) 應用最小生成樹原理優化算法。
本節除了深入研讨最小生成樹的性質和求解方法外，還給出了三種特殊類型生成樹：
1) 最優比率生成樹。
2) 最小k度限制生成樹。
3) 次小生成樹的解法。
1.2.1 最小生成樹的思想和應用
我們先來探讨最小生成樹的解法。設：
a是一棵最小生成樹的子集，如果邊(u，v)不屬于a且a∪{(u，v)}仍然是某一棵最小生成樹的子集，就稱(u，v)為集合a的安全邊。由此引出計算最小生成樹的一般思想：
（1） prim算法
從任一節點出發，通過不斷加入邊權最小的安全邊擴充最小生成樹，直至連接配接了所有節點為止。圖1.2-2列舉了運用prim算法計算最小生成樹的過程。
https://yqfile.alicdn.com/b81e9720703be5615cf549bcfb89b5ceaf162e42.png" >
顯然，prim算法采取了在一棵樹上擴充的計算方式。如果用相鄰矩陣w［］［］存儲圖、用一維數組key［］存儲每個樹外節點到樹中節點的邊所具有的最小權值(簡稱最短距離值)，用π［］記錄生成樹中每個節點的父親，用隊列q存儲樹外節點，則可得到如下算法流程：
如果隊列q采用一維數組存儲，每次從q中取出key值最小的節點，需要運作時間為o(v)；存在v次這樣的操作，是以從q中取key值最小節點的全部運作時間為o(v2)。對每個key值最小的節點來說，與之相鄰的每個節點都要考察一次，是以考察次數為o(v)。而每确定一個節點進入生成樹後，需要花費o(1)的時間更新與之相連的樹外節點的key值，累計整個算法的運作時間為o(v2)；如果隊列q采用小根堆組存儲，則算法的運作時間可降為o(v*log2v)。由此看出，prim算法的時間複雜度取決于節點數v，而與邊數e無關，是以一般适用于稠密圖。
（2） kruskal算法
按照權值從小到大的順序排列邊。初始時，每個節點單獨組成了一棵生成樹。然後按照權值遞增順序擴充安全邊。每拓展一條安全邊，将其中兩棵生成樹合并成一棵，直至構造出連接配接所有節點的一棵最小生成樹為止。圖1.2-3列舉了運用kruskal算法計算最小生成樹的過程。
https://yqfile.alicdn.com/697aab8769321576a4addb111baff4561acf04aa.png" >
下面給出kruskal算法的基本流程。
顯然，kruskal算法采取了合并生成樹的計算方式:初始化需占用時間o(v)，邊按照邊權遞增順序排序需要的運作時間為o(elog2e)；對分離集的森林要進行o(e)次操作，每次操作需要時間o(log2e)，是以kruskal算法的全部運作時間為o(elog2e)。由于kruskal算法的時間複雜度取決于邊數e，而與節點數v無關，是以一般适用于稀疏圖。
在競賽中有不少建構最小生成樹的試題，我們需要從無向圖的具體結構和最小生成樹的性質出發，運用各種算法在圖中尋找屬于最小生成樹的邊。這些題有些屬于顯性的最小生成樹問題，有些雖不直接以最小生成樹面貌出現，但可以借助最小生成樹的原理化繁為簡，化未知為已知。
【1.2.1 arctic network】
【問題描述】
國防部(the department of national defence，dnd)要通過無線網絡同幾個北方的哨所進行通信。兩種不同的通信技術将被用于建立網絡：每個哨所擁有一台無線電收發報機以及其中一些哨所還擁有一個衛星頻道。
任何兩個擁有衛星頻道的哨所，無論它們的位置在哪裡，都可以通過衛星進行通信。否則，這兩個哨所由于收發報機的功率，隻有在它們之間的距離不超過d的情況下，通過無線電進行聯絡。d的值越高，就要用功率更高的收發報機，但這樣成本非常高。出于采購和維修方面的考慮，哨所使用的收發報機必須是相同的；也就是說，對每一對哨所，d的值必須是相同的。
請你确定收發報機的最小d值。在每對哨所之間，必須至少有一條(直接或間接的)通信路徑。
輸入：
輸入的第一行給出n，表示測試用例的個數。每個測試用例的第一行給出s和p，其中s表示衛星頻道的數量，1≤s≤100；p表示哨所的數量，s＜p≤500。接下來給出p行，每行給出一個哨所的(x，y)坐标，以公裡為機關(坐标是在0和10000之間的整數)。
輸出：
對每個測試用例，輸出一行，給出要連接配接網絡的最小的d值，精确到小數點後2位。
試題來源：waterloo local 2002.09.28
線上測試位址：poj 2349，zoj 1914，uva 10369
試題解析
簡述題意：有兩種不同的通信技術:衛星通信和無線電通信，衛星通信可在任兩個哨所間任意聯絡；但采用無線電通信的哨所隻能和距離不超過d的哨所聯系。無線電的能力越高(即傳輸距離d越大)，花費就越大。已知無線電數目m，計算最小的d使得每對哨所之間至少有一條(直接或間接的)通信路徑。
我們将哨所作為節點，把所有可以互相通信的哨所連接配接起來，邊權設為相連的兩個哨所的距離，則可構造出一個完全無向圖。要在這個完全無向圖中劃分出s個連通分支，每個連通分支内節點間的邊權不大于d，即位于同一連通分支内的哨所間采用無線電收發機通信，每個連通分支配置設定一台衛星裝置，用于不同連通分支間的通信。顯然衛星裝置的台數就是圖的連通分支數，目标是求連通分支内邊長的上限d(即最小收發距離)。解題有兩種政策：
1) 正向思考：在已知連通分支數s的基礎上求連通分支内邊長的上限d。
2) 逆向思維：在已知連通分支内邊長上限d的基礎上求連通分支數s。
顯然，正向思考的政策似乎難以施展，因為p個哨所可構成由p*(p-1)2」條邊組成的完全圖。要在這張圖中找到連通分支内邊長上限d，使得删去大于d的邊後連通分支數正好為s是相當困難的。而逆向思維的政策相對簡單，在正向思考受阻的情況下，應該“正難則反”，逆向考慮問題。于是問題轉化為：找到一個最小的d，使得把所有權值大于d的邊去掉之後，連通分支數小于等于s。由此引出一個定理：
【定理1.2-1】 如果去掉所有權值大于d的邊後，最小生成樹被分割成為s個連通分支，圖也被分割成為s個連通分支。
證明：用反證法。假設最小生成樹被分割成為s個連通支，原圖被分割成s′(s′≠s)個連通支，由于最小生成樹是原圖的一個子圖，是以s′有了這個定理，很容易得到一個構造性算法：最小生成樹的第s長的邊就是問題的解。
證明：首先，d取最小生成樹中第s長的邊是可行的。如果d取第s長的邊，我們将去掉最小生成樹中前s-1長的邊，最小生成樹将被分割成為s部分。由定理1.2-1，原圖也将分割成為s部分(可行性)。其次，如果d比最小生成樹中第s長的邊小的話，最小生成樹至少被分割成為s+1部分，原圖也至少被分割成為s+1部分。與題意不符(最優性)。
綜上所述，最小生成樹中第s長的邊是使得連通分支個數≤s的最小的d，即問題的解。(證畢)
由于通信圖的節點數不多(p≤500)，對應完全圖的邊數不是太多，是以我們在計算最小生成樹上采用了kruskal算法。
程式清單
一道看似毫無頭緒的試題被最小生成樹的算法破解了，顯示出最小生成樹的魅力。在解題過程中，一個對最小生成樹本質特征的揭示在最小生成樹和圖的連通分支之間搭起了一座橋梁，正是這座橋梁引領我們順利到達了勝利的彼岸。
在程式設計競賽中，有些看似與最小生成樹風馬牛不相幹的幾何計算題，也可以經過分析轉化為圖論模型，并采用最小生成樹去解決。我們不妨來看下面兩個範例。
【1.2.2 robot】
在不久的将來，機器人要給參加巴爾幹半島奧林匹克資訊學競賽(balkan olympiad in informatics)的選手運送食品。機器人将所有的食品放置在一個單一的方形托盤中。不幸的是，在廚房和選手廳之間的路徑上充滿了各種障礙，是以，機器人不能帶任意大小的托盤。請你編寫一個程式zad1.exe，确定可用于餐飲的最大可能的托盤的尺寸。
機器人要行走的路徑是平行牆壁包夾的走廊，走廊隻能有90°轉角。走廊在x軸正方向開始。障礙是一些立柱，被表示為點，它們都是在包夾走廊的牆壁之間。為了使機器人能夠走過這段路徑，托盤不能撞到立柱或牆壁——它可能隻是邊與邊“觸摸”。機器人和它的托盤隻能在x或y軸方向上轉換移動。 假定機器人的尺寸小于托盤的尺寸，機器人完全在托盤之下(見圖1.2-4)。
https://yqfile.alicdn.com/b8247c07d2a305af923be4f37c1f60e75f99ebcd.png" >
在檔案zad1.dat的第一行是一個整數m(1≤m≤30)，表示直線牆的線段的數量。接下來的m+1行是所有轉彎點(包括端點)的“上部分”牆體的x和y坐标，相似地，接下來的m+1行是所有轉彎點(包括端點)的“下部分”牆體的x和y坐标。然後的一行給出整數n(0≤n≤100)，表示障礙物的數量，接下來n行是障礙物的x和y坐标。所有坐标是絕對值小于32001的整數。
試題來源：balkan olympiad in informatics 2002
線上測試位址：hdoj 4840
簡述題意：m條含上下部分的直線牆互相連接配接、以90°轉角組成一條走廊，走廊牆壁之間有部分障礙物。機器人舉托盤沿走廊行走，托盤不能撞到障礙物或牆壁。問托盤的邊長最大為多少時機器人才能走過走廊。
設li為穿行第i條走廊時盤子的最大邊長。顯然，機器人要順利穿行n條走廊，則盤子的最大邊長為min1≤i≤n{li}。顯然問題的關鍵是，在已知第i條走廊的“上部”牆線段和“下部”牆線段的情況下如何計算li？下面，我們就來讨論這個問題。
解法1：通過二分+模拟的算法查找能夠通過走廊的盤子的最大尺寸。
這是一種比較容易想到的方法。為了提高查找效率，我們做了如下優化。
首先，對機器人和障礙物作一個“換位”思考：
根據題意，機器人是正方形，障礙物是點(見圖1.2-5a)；如果把機器人的尺寸移植到障礙物上，那麼機器人就成了一個點，而障礙物就是正方形了(見圖1.2-5b)。顯然這兩個問題是等價的。
https://yqfile.alicdn.com/f9e0a1797f99d450a42fc69c78648405a7afa90d.png" >
要讓一個點通不過，唯一辦法就是用障礙物把走廊堵住。這裡的“堵住”，就是說障礙物将在走廊的兩堵牆之間形成一條通路。于是，這道題就被轉化成一個圖論問題：
把障礙物和牆壁看作圖中的點，點p1(x1，y1)和點p2(x2，y2)之間的距離max{x1-x2，y1-y2}為邊的權值，按照這一公式定義障礙點間的距離；障礙物與牆壁的距離就是障礙點與牆壁上所有點的距離的最小值；兩堵牆之間的距離就是走廊的最小寬度(見圖1.2-6)。
把牆壁看作起點和終點。例如圖1.2-7a中的兩堵牆之間有兩個障礙物，在圖1.2-7b中兩個障礙物被分别設為頂點x和y，兩堵牆被分别設為起點u和終點v。牆與牆之間、障礙物與障礙物之間、障礙物與牆之間連邊，邊長為對應的距離。問題就轉化為：從起點u到終點v的所有路徑中最長邊的最小值是多少？因為當邊長達到一條路徑上的最長邊時，這條路徑就“通”了，走廊也就被堵住了。
顯然，這個問題可以在對邊權進行二分計算的基礎上求解，即采用“二分+寬度優先搜尋”的方法解決，時間複雜度是o(n2*log2(邊權上限))。這個算法效率并不理想，還有沒有其他更好的算法呢？有的。
解法2：通過計算圖的最小生成樹得出問題的解。
先求出這個圖的最小生成樹，那麼從起點到終點的路徑就是我們所要找的路徑，這條路徑上的最長邊就是問題的答案。這樣，時間複雜度就降為o(n2)了。
可是怎麼證明其正确性呢？用反證法。
證明：設起點為u，終點為v，最小生成樹上從u到v的路徑為舊路徑，舊路徑上的最長邊為m。假設從u到v存在一條新路徑且上面的最長邊短于m。
如果新路徑包含m，則新路徑上的最長邊不可能短于m。與假設不符。
如果新路徑不包含m，則新路徑一定“跨”過m。如圖1.2-8，x→…→a1→a2→…ak→y是舊路徑上的一段，x→b1→b2→…→bp→y是“跨”過去的一段。
如果把m去掉，最小生成樹将被分割成兩棵子樹，顯然x和y分屬于不同的子樹(否則最小生成樹包含一個環)。是以在x→b1→b2→…→bp→y上，一定存在一條邊m′，它的端點分屬于不同的子樹。因為最小生成樹中隻有m的端點分屬于不同的子樹，是以m′不屬于最小生成樹。是以m′和m一樣是連接配接兩棵子樹的邊。因為新路徑的最長邊短于m且m′屬于新路徑，是以w(m′)
綜上所述，不可能存在另一條從u到v的路徑，使得它的最長邊短于m。最小生成樹上從u到v的路徑就是最長邊最短的路徑，該路徑上的最長邊就是問題的解。(證畢)
由于圖的節點數較少(≤100)，是以，采用prim算法計算最小生成樹為宜。
【1.2.3 qin shi huangs national road system】
在中國古代的戰國時期(公元前476年至公元前221年)，中國分成7個國家——齊、楚、燕、韓、趙、魏、秦。嬴政是秦國的國王。經曆了9年的戰争，嬴政終于在公元前221年征服了其他六個國家，成為統一中國的第一個皇帝。這就是秦朝——中國的第一個王朝(清朝是中國的最後一個王朝)。是以嬴政自稱“秦始皇”，因為“始皇”在中文中的意思是“第一個皇帝”。
秦始皇主持了許多巨大的工程項目，其中就包括中國長城的第一個版本、著名的秦始皇兵馬俑以及一個巨大的國家道路系統。下面是一個關于道路系統的故事：
在中國有n座城市，秦始皇希望用n-1條道路把這些城市全部連接配接起來，以便他能從首都鹹陽到每一個城市。雖然秦始皇是一個暴君，但他希望所有道路的總長度最小，使道路系統不必花太多的人力。道士徐福告訴秦始皇，他可以用魔法修建一條道路，而且用魔法修建的道路不用花錢，也不用使用勞動力。但徐福隻能為秦始皇修建一條魔法道路，是以秦始皇要決定在哪裡修建魔法道路。秦始皇希望所有不用魔法修建的道路的總長度盡可能小，但徐福則希望魔法道路要有利于盡可能多的人——是以秦始皇決定，a/b的值(a與b的比率)必須最大，其中a是兩座用魔法道路連接配接的城市的總人口，而b是沒有用魔法修建的道路的總長度。
您能幫助秦始皇嗎？
每座城市被視為一個點，一條道路被視為連接配接兩個點的一條直線。
第一行給出一個整數t，表示t個測試用例(t≤10)。
對每個測試用例：
第一行給出一個整數n，表示有n座城市(2接下來給出n行，每行給出3個整數x、y和p(0≤x，y≤1000，0
本題設定，每座城市的位置是不同的。
對每個測試用例，按上述要求輸出一行，給出最大比率a/b。結果精确到小數點後兩位。
簡述題意：給出n個城市的二維坐标以及每個城市的價值(人口)，現在有人免費幫助秦始皇修理任意一條公路。如果把城市看作節點，任一對節點間連邊，邊權為城市間的歐氏距離，則組成了一個帶權的完全無向圖。按照秦始皇的旨意(連接配接用n-1條道路所有城市，以便他能從首都鹹陽到每一個城市)，需要建構這張圖的一棵生成樹，使得比率a/b最大，其中a表示這條公路兩端城市的價值和，b表示生成樹的邊權和，但不包括這條公路的長度。
顯然，想要比率a/b最大，是以a要盡可能大、b要盡可能小。要使b盡可能小的話，可以先求得最小生成樹t，其邊權和為total。然後枚舉最小生成樹上的每條邊(i，j)∈t，在删除該邊後得到的兩個點集中分别找到最大價值的節點i′和j′，兩個節點的價值分别為ai′和aj′，添加邊(i′，j′)，得到的依然是一棵生成樹，更新a/b比率。顯然，最大比率a/b=max(i,j)∈tai′+aj′total-(i,j)的邊長。
由于公路圖為一個節點數不超過1000的完全圖，是以不妨使用prim算法計算最小生成樹，并通過dfs找兩個集合中的點。計算時間複雜度為o(n2)。
當然，［1.2.2 robot］和［1.2.3 qin shi huangs national road system］還有其他解法，譬如dfs搜尋等。既然如此，為什麼偏要選擇計算最小生成樹的方法呢？不僅因為它效率高、程式設計複雜度低，最重要的是因為它構思巧妙，頗有啟發性。把兩道貌似計算幾何的問題轉化為最小生成樹模型就已經頗有新意了，再用最小生成樹去解決轉化後的圖論問題，就更顯其奧妙無窮。實際上這個思維過程是深入思考的結果。例如［1.2.2 robot］中，我們面臨的問題是如何從u到v的衆多路徑中選擇最佳路徑。如果你在u和v之間畫了兩條路徑，并标上最長邊，準備考慮如何比較它們優劣的話，會出現一個環，而且環上還有一條最長邊。這時便初顯出最小生成樹的端倪。再如［1.2.3 qin shi huangs national road system］中，我們面臨的問題是，如果删除任意一條邊(i，j)，則會形成兩個連通分量，在每個連通分量中各選一個價值最大的節點連邊，則生成樹性質保持不變，但相對(i，j)來說，a是最大的。我們按照上述思路嘗試最小生成樹的n-1條邊，自然可得出a/b的最大比率。顯然，在問題初顯出最小生成樹端倪的基礎上，經過反複修正、嚴謹證明，算法會逐漸成熟起來。是以，最小生成樹的應用并不是想象的那麼簡單，它需要敏銳的洞察力、紮實的圖論基礎和積極創新的思維。
1.2.2 最優比率生成樹的思想和應用
前面所講的最小生成樹，指的是連通圖中邊權和最小的生成樹，即圖中每條邊隻有邊權一個參數。
現在給出一個完全圖，圖中每條邊設兩個參數(bi和ci)，要求計算一棵生成樹，使得∑(xici)∑(xibi)最小，其中xi當第i條邊包含在生成樹中時為1，否則為0。這樣的生成樹稱為最優比率生成樹。
最優比率生成樹的計算有3種方法。
方法1：01整數規劃
設xi等于1或0，表示邊ei是否屬于生成樹。則所求比率r=∑(xici)∑(xidi)，0≤i≤n2(n-1)-1。為了使r最大，設計一個子問題：
讓z=∑(dixi)-l∑(cixi)=∑(tixi)最大(其中ti=di-l*ci)，并記為z(l)，即把z(l)看做以ti為邊權的最小生成樹的總權值。
顯然，01整數規劃屬于一種蠻力搜尋，計算效率低。但是，我們可以從上述分析中找到z的兩種性質：
【性質1.2-1】 z單調遞減。
證明：因為c為正數，是以z随l的減小而增大。
【性質1.2-2】 z(max(l))=0。
證明：若z(max(l))<0，∑(dixi)-max(l)∑(ci*xi)<0，可化為1r由上面的分析，我們就将問題轉化為求解比率rate使z(rate)==0，由此引出方法2和方法3。
方法2：二分法
步驟1：找出比率rate的最小值l和最大值r并設定精度範圍。
步驟2：求mid=(l+r)/2。
步驟3：用di-mid*ci重新構圖。
步驟4：求出新圖的最小生成樹權值和。
步驟5：如果權值和等于0，mid就是我們要求的比率，成功傳回。如果權值和>0，l=mid；如果權值<0，rear=mid，跳回步驟2繼續循環。
二分法一定能夠在經過log2(r-l)次搜尋之後找到所求比率。
方法3：疊代法
生成樹的比率為∑生成樹邊ci參數∑生成樹邊bi參數。設：prerate為上次計算出的生成樹的比率；rate為目前生成樹的比率；sumc=∑生成樹邊ci參數；sumb=∑生成樹邊bi參數。
疊代過程如下：
計算連通圖中每條邊的參數ci和bi；
【1.2.4 desert king】
偉大的david剛剛成為一個沙漠國家的國王。為了赢得人民的尊敬，他決定在他的國家内建立遍布的通水管道，實作村村通水，即和首都連通的村莊都将通水。作為國家的統治者和國家智慧的象征，他需要一個最優方式建立通水管道。
經過幾天的研究，他終于完成了他的計劃。他希望通水管道每英裡的平均成本最小化。也就是說，通水管道總成本與總長度的比例必須最小化。他隻需要修建将水通到所有村莊的必要通道就可以了，這意味着，連接配接每個村莊到首都隻有一種方式。
他的工程師調查了國家，并記錄了每個村的位置。所有在兩座村莊之間的通水管道都是走直線。由于任何兩個村莊的海拔高度都不同，是以工程師得出的結論是，每兩個村之間的通水管道都需要安裝一個垂直傳輸水的升降機，可以将水向上打，或讓水流下來。通水管道的長度是兩村之間的水準距離，通水管道的成本是升降高度。您要注意每個村所在的不同的海拔高度，而且不同的通水管道不能共享一個升降機。通水管道能安全地相交，不會有三座村莊在同一條直線上。
作為david國王的首席科學家和程式員，請你找出建立通水管道的最佳解決方案。
存在若幹測試用例。每個測試用例開始的第一行給出整數n(2≤n≤1000)，表示村莊的數目。接下來的n行每行給出3個整數x、y和z(0≤x，y<10000，0≤z<10000000)。(x，y)是村莊的位置，z是海拔高度。第一個村莊是首都。以n=0結束輸入，程式不用處理。
對于每個測試用例，輸出一行，給出一個十進制數，表示通水管道總成本與總長度的最小比值。這個數字精确到小數點後的三位。
https://yqfile.alicdn.com/a022b63b4b00575e69cc7171e0e6e6fb91af4418.png" >
簡述題意：已知n個村莊的坐标和海拔高度。任兩個村莊之間存在高度差和歐氏距離兩個資料。要求把任兩個村莊直接或者間接連通，且所有連通邊的高度差之和除以距離和值最小。
将村莊作為節點，任兩個村莊間互通，則構成了一個完全圖。通水管道的成本取決于相鄰兩個村莊高度差的絕對值，長度是兩村之間的水準距離。是以每條邊有兩個參數：兩個端點高度差的絕對值bi；兩個端點間的歐氏距離ci。由于需要實作村村通水且通水管道的總成本與總長度的比例必須最小化，是以可看出此題就是一個典型的最優比率生成樹問題。
下面，分别給出二分法和疊代法的程式範例。由于圖的節點數較少(≤1000)，是以采用prim算法計算最小生成樹。
1.2.3 最小k度限制生成樹的思想和應用
對于一個權重的無向圖，存在一些滿足下面性質的生成樹：某個特殊節點的度為一個指定數值。最小度限制生成樹就是滿足此性質且權值和最小的一棵生成樹。把它抽象成數學模型就是：
設g=(v，e，ω)是連通的有權無向圖，v0∈v是特别指定的一個節點，k為給定的一個正整數。如果t是g的一棵生成樹且dt(v0)=k，則稱t為g的k度限制生成樹。g中權值和最小的k度限制生成樹稱為g的最小k度生成樹。
顯然，最小k度生成樹問題是有實際應用價值的，因為現實生活中許多問題可以歸結為該問題。下面，我們來探讨求解方法。
約定：t為圖g的一棵生成樹，a和b為圖g的兩個邊子集，ae，be。在Ｔ中增加邊集a、去除邊集b後得到圖t+a-b，記作(+a，-b)。如果t+a-b仍然是一棵生成樹，則稱(+a，-b)是t的一個可行交換。
【引理1.2-1】 設t′、t是圖g的兩棵不同的生成樹，
則存在e(t)＼e(t′)的一個按照權值遞增排序的邊序列b′1，b′2，…，b′n，使得t+ai-b′i(1≤i≤n)仍然是g的生成樹。
【定理1.2-2】 設t是g的k度限制生成樹，則t是g的最小k度限制生成樹當且僅當下面三個條件同時成立：
1) 對于g中任何兩條與v0關聯的邊所産生的t的可行交換都是不可改進的。
2) 對于g中任何兩條與v0不關聯的邊所産生的t的可行交換都是不可改進的。
3) 對于t的任何兩個可行交換(+a1，-b1)和(+a2，-b2)，若a1、b2與v0關聯，b1、a2不與v0關聯，則有ω(b1)+ω(b2)≤ω(a1)+ω(a2)。
證明：我們從必要性和充分性這兩個方面給予證明：
必要性：設t是最小k度限制生成樹，則條件1）、2）顯然成立。以下證明條件3）：由條件1）、2）可知，如果(+a1，-b2)和(+a2，-b1)都是t的可行交換，則有ω(b2)≤ω(a1)，ω(b1)≤ω(a2)，故ω(b1)+ω(b2)≤ω(a1)+ω(a2)；否則，或者(+a1，-b2)或者(+a2，-b1)不是t的可行交換，根據引理1，t′=t+{a1，a2}-{b1，b2}仍然是t的k度限制生成樹，則ω(t)≤ω(t′)，故ω(b1)+ω(b2)≤ω(a1)+ω(a2)。
充分性：設t是k度限制生成樹且滿足1）、2）、3），假如有另一個k度限制生成樹t′，ω(t′)<ω(t)，設
顯然有∑ω(ai)<∑ω(bi)，根據引理1.2-1，存在一個排列b′1，b′2，…，b′n，滿足t+ai-b′i仍然是g的生成樹。由ω(t′)<ω(t)得∑(ω(b′i)－ω(ai))>0，因而，在t的這n個可行交換中，一定存在某個可以改進的交換(+ai，-b′i)。由于t滿足1）、2），則ai、b′i若同時與v0關聯或不關聯都是不可改進的。也就是說，ai和b′i中必定恰好有一個不與v0關聯。不妨設ai與v0無關聯，因為d′t(v0)也等于k，是以必存在另一個交換(+aj，-b′j)，滿足aj與v0關聯，b′j與v0無關聯，且(ω(b′i)-ω(ai))+(ω(b′j)-ω(aj))>0，此與3）沖突。是以，t′是不存在的，即t是g的最小k度限制生成樹。(證畢)
由定理1.2-2，可引出定理1.2-3：
【定理1.2-3】 設t是g的最小k度限制生成樹，e0是g中與v0有關聯的邊的集合，e1=e0＼e(t)，e2=e(t)＼e0，a={(+a，-b)a∈e1，b∈e2}，設ω(a′)-ω(b′)=min{ω(a)-ω(b)(+a，-b)∈a}，則t+a′-b′是g的一個最小k+1度限制生成樹。
那麼，如何求最小k度限制生成樹呢？首先考慮邊界情況。先求出問題有解時k的最小值：把v0點從圖中删去後中可能會出現m個連通分量，而這m個連通分量必須通過v0來連接配接(見圖1.2-9)。是以，在圖g的所有生成樹中dt(v0)≥m。也就是說，當k
根據上述定理1.2-3，得出求最小k度限制生成樹的算法架構：
步驟1：先求出最小m度限制生成樹。
步驟2：由最小m度限制生成樹得到最小m+1度限制生成樹。
步驟3：若dt(v0)=k時停止；否則傳回步驟2。
下面分别考慮每一步:首先将v0和與之關聯的邊分别從圖中删去，此時的圖可能不再連通，對各個連通分量，分别求最小生成樹。接着，對于每個連通分量v′，求一點v1(v1∈v′)，且ω(v0，v1)=min{ω(v0，v′)v′∈v′}，則該連通分量通過邊(v1，v0)與v0相連(見圖1.2-10)。于是，我們就得到了一個m度限制生成樹，不難證明，這就是最小m度限制生成樹。步驟1的時間複雜度為o(vlog2v+e)。
我們所求的樹是無根樹，為了解題的簡便，把該樹轉化成以v0為根的有根樹。假設已經得到了最小p度限制生成樹，如何求最小p+1度限制生成樹呢？
根據定理1.2-3，最小p+1度限制生成樹肯定是由最小p度限制生成樹經過一次可行交換(+a1，-b1)得到的。我們自然就有了一個最基本的想法——枚舉!但是簡單的枚舉，時間複雜度高達o(e2)，顯然是不可取的。深入思考不難發現，任意可行的交換，必定是一條邊跟v0關聯，另一條與v0無關，是以，隻要先枚舉與v0關聯的邊，再枚舉另一條邊，然後判斷該交換是否可行，最後在所有可行交換中取最優值即可。于是時間複雜度降到了o(ve)，但這仍然不能令人滿意。進一步分析，在原先的樹中加入一條與v0相關聯的邊後，必定形成一個環。若想得到一棵p+1度限制生成樹，需删去一條在環上的且與v0無關聯的邊。删去的邊的權值越大，則所得到的生成樹的權值和就越小。如果每添加一條邊，都需要對環上的邊一一枚舉，時間複雜度将比較高，因為有不少邊重複統計多次。例如圖1.2-11a給出了一棵生成樹，依次添邊(v0，v4)、(v0，v3)(圖1.2-11b～c)。在形成的兩個環中，邊(v1，v2)和(v2，v3)分别被重複統計了兩次(圖1.2-11d)。
https://yqfile.alicdn.com/5437cb85622d5ed29b01a57a2d5d55baa99064a1.png" >
此時，動态規劃便有了用武之地。設best(v)為v0至v的路徑上與v0無關聯且權值最大的邊；father(v)為v的父節點。
狀态轉移方程：best(v)=max{best(father(v))，ω(father(v)，v)}；
邊界條件：best［v0］=-∞，best［v′］=-∞(v0，v′)∈e(t)。
狀态共v個，每次狀态轉移的時間複雜度為o(1)，是以時間複雜度為o(v)。故得出步驟2(由最小p度限制生成樹得到最小p+1度限制生成樹)的時間複雜度為o(v)。由于這一計算過程直至dt(v0)=k時為止，是以步驟2和步驟3的時間複雜度為o(kv)。
綜上所述，求最小k度限制生成樹算法總的時間複雜度為o(vlog2v+e+kv)。下面，我們通過一個範例來體驗最小k度限制生成樹的應用和程式實作。
【1.2.5 picnic planning】
contortion brothers是一群著名的馬戲團小醜，衆所周知，他們有着令人難以置信的能力，能把無限多的自己塞進即使是最小的車輛。在演出淡季，他們喜歡聚在當地的一個公園舉行年度的柔術演員會議(annual contortionists meeting，acm)。然而，他們不僅受限于狹窄的空間，而且缺錢，是以他們嘗試找一個方法使得參加會議的每個人的車的裡程數最小(以節省汽油、減少磨損等)。為此，他們要把自己擠塞進盡可能少的汽車内，并且盡量使他們的所有車輛的總裡程數最小化。這就導緻了這樣的情況，許多人開車到一個同伴的家，把他們的車放在那裡，與同伴擠進一輛車中。然而，在公園也有一條限制：在野餐地點的停車場隻能容納有限數量的汽車，是以必須考慮到整體的計算。此外，由于公園的門票原因，一旦一個同伴的車到了公園，他就不能放下他的乘客，然後離開去接其他的同伴。現在請你編寫一個程式來解決他們的裡程數最小化問題。
輸入給出一個問題的測試用例。第一行給出一個整數n，表示連接配接馬戲團小醜之間或馬戲團小醜和公園之間的公路的條數。接下來的n行每行表示一個公路連接配接，形式為“name1 name2 dist；”，其中name1和name2是馬戲團兩個小醜的名字，或者一個是小醜的名字，另一個是單詞park(順序是任意的)；dist是一個整數，表示他們之間的距離。這些公路都是雙向的道路，距離總是為正。馬戲團小醜的最大數量為20，任何name最多為10個字元。接下來的最後一行給出一個整數，表示在野餐的地點可以停車的數量。本題設定從每個小醜的家到公園都有一條路徑，每個測試用例都存在解。
輸出一行，格式如下。total miles driven: xxx其中xxx是總的裡程數除以所有小醜的車輛數。
簡述題意:有一群小醜開車到公園，但公園停車場隻能停k輛車。不過呢，這群小醜可以先開車到另外一個小醜家裡，然後搭他的便車(車上沒有人數限制)到公園。他們希望車駛過的路徑長度最小，問最短距離是多少。
如果将小醜作為節點，道路作為邊，則構成一個帶權的無向連通圖。試題要求計算一棵以節點v0(公園)為根的生成樹，但這棵生成樹并不是嚴格意義上的最小k度限制生成樹，而是在v0的度不超過k情況下的最小生成樹。也就是說，并不一定要求v0的度數為k，隻要圖的總權值不能繼續減小，計算就可以結束。
我們按照如下步驟計算這棵生成樹：
1) 将v0從圖中删除，将得到p個連通分量。
2) 對每個連通分量求最小生成樹。
3) 從每個連通分量中找出與v0關聯的權值最小的邊，與v0相連接配接，這樣将得到v0的最小p度生成樹。
4) 如果k
5) 如果k≥p，則考慮建構p+1度最小生成樹，即加入每一條與v0相連且不在目前生成樹的邊。
6) 顯然，在步驟5)添加一條與v0相連的樹外邊，必然會存在一個環，删掉該環中與v0不關聯的權值最大邊，将得到一棵最小生成樹，且v0是p+1度的。若p+1度最小生成樹的邊權和大于p度最小生成樹的邊權和，則直接輸出p度最小生成樹的邊權和；否則重複步驟5)、6)，直至k度最小生成樹出現為止。
由于節點數較少(n≤20)，是以算法步驟1)、2)、3)可以用prim算法實作，時間複雜度為o(n2)；在步驟5)、6)、中，若通過蠻力枚舉每條邊來進行增删操作的話，則時間複雜度是o(n2)，緻使總複雜度達到o(kn2)。為了提高效率，我們在增删邊的操作中設立了一個del［］數組，其中del［i］記錄了v0→vi路徑上的最長邊。加入邊(v0，i)、删除邊del［i］便形成了一棵p+1度的最小生成樹，其邊權和=原邊權和-del［i］的邊權+(v0，i)的邊權。顯然，每次隻要枚舉max{del［i］的邊權-(v0，i)的邊權}，即可使得生成樹的邊權和最大幅度地減少。注意每次操作後都要更新該連通塊的del［］，這樣可将時間複雜度降為o(kn)。
1.2.4 次小生成樹的思想和應用
設g=(v，e，w)是連通的無向圖，t是圖g的一棵最小生成樹。如果有另一棵樹t1，滿足不存在樹t′，ω(t′)<ω(t1)，則稱t1是圖g的次小生成樹。
現實生活中的許多問題可以歸結為次小生成樹問題，使得計算次小生成樹的算法有實際的應用價值。下面，我們來探讨這個算法。約定：
由t進行一次可行交換得到的新的生成樹所組成的集合，稱為樹t的鄰集，記為n(t)。
【定理1.2-4】 設t是圖g的最小生成樹，如果t1滿足ω(t1)=min{ω(t′)t′∈n(t)}，則t1是g的次小生成樹。
證明：如果t1不是g的次小生成樹，那麼必定存在另一棵生成樹t′，t′=t使得ω(t)≤ω(t′)<ω(t1)，由t1的定義式知t不屬于n(t)，則：
根據引理1.2-1知，存在一個排列bi1，bi2，…，bit，使得t+aj-bij仍然是g的生成樹，且均屬于n(t)，是以ω(aj)≥ω(bij)，ω(t′)≥ω(t+aj-bij)≥ω(t1)，故沖突。由此得出t1是圖g的次小生成樹。
通過定理1.2-4，我們就有了解決次小生成樹問題的基本思路：
首先先求該圖的最小生成樹t，時間複雜度o(vlog2v+e)。然後求t的鄰集中權值和最小的生成樹，即圖g的次小生成樹。問題是，如何在最小生成樹t的基礎上求次小生成樹，這是制約算法效率的瓶頸。
如果隻是簡單的枚舉，複雜度很高：首先枚舉兩條邊的複雜度是o(ve)，再判斷該交換是否可行的複雜度是o(v)，則總的時間複雜度是o(v2e)。這樣的算法顯得很盲目。
經過簡單的分析不難發現，每加入一條不在樹上的邊，總能形成一個環(見圖1.2-12)。
隻有删去環上的一條邊，才能保證交換後仍然是生成樹，而删去邊的權值越大，新得到的生成樹的權值和越小。我們可以以此将複雜度降為o(ve)。這已經前進了一大步，但仍不夠好。
回顧上一個模型——最小度限制生成樹，我們也曾面臨過類似的問題，并且最終采用動态規劃的方法避免了重複計算，使得複雜度大大降低。對于次小生成樹，我們也可以采用類似的思想：
1) 求圖g的最小生成樹t(時間複雜度為o(vlog2v+e))；
2) 做一步預處理，通過簡單的寬度優先搜尋求出樹上每兩個節點之間的路徑上的權值最大的邊(時間複雜度為o(v2))；
3) 枚舉圖中不在樹上的邊(時間複雜度為o(e))。有了剛才的預處理，我們就可以用o(1)的時間得到環上權值最大的邊。
由此可見，次小生成樹的時間複雜度為o(v2)。下面，我們通過一個範例來體驗次小生成樹的應用。
【1.2.6 次小生成樹tree】
小c最近學了很多最小生成樹的算法，prim算法、kurskal算法、消圈算法等。正當小c洋洋得意之時，小p來潑小c冷水了。小p讓小c求出一個無向圖的次小生成樹，而且這個次小生成樹還得是嚴格次小的，也就是說：如果最小生成樹選擇的邊集是em，嚴格次小生成樹選擇的邊集是es，那麼需要滿足(value(e)表示邊e的權值)∑e∈emvalue(e)<∑e∈esvalue(e)。這下小c蒙了，他找到你，希望你幫他解決這個問題。
第一行包含兩個整數n和m，表示無向圖的點數與邊數。接下來m行，每行3個數x、y和z表示，點x和點y之間有一條邊，邊的權值為z。
包含一行，僅一個數，表示嚴格次小生成樹的邊權和(資料保證必定存在嚴格次小生成樹)。
https://yqfile.alicdn.com/2895849814dde1c189bf75d0dce0d1ad6cdce9b4.png" >
提示：
資料中無向圖無自環；50%的資料n≤2000，m≤3000；80%的資料n≤50000，m≤100000；100%的資料n≤100000，m≤300000，邊權值非負且不超過10^9。
試題來源：北京2010組隊賽試題
顯然，這道試題是次小生成樹定義的直譯，可直接按照次小生成樹的算法求解。由于該圖為稀疏圖(n≤100000，m≤300000)，是以最小生成樹的計算采用kruskal算法。
【1.2.7 acm contest and blackout】
為了準備“全國首屆acm學校競賽”，也為防止在競賽期間停電，市長決定為所有的學校提供可靠的電力來源。是以，future電站必須和一所學校(是哪一所學校并不重要)連接配接；此外，一些學校也必須連接配接好。
本題設定，如果一家學校直接連接配接到future電站，或者連接配接到任何其他的有可靠的電力來源的學校，那麼這家學校就有可靠的電力來源。本題給出在一些學校之間進行連接配接的成本。市長決定挑選出兩個最便宜的連接配接方案——總的連接配接成本等于學校之間的連接配接成本的總和。請你幫助市長找到兩個最便宜的連接配接方案。
首先在第一行中給出測試用例的個數t(1≤t≤15)。然後給出t個測試用例，每個測試用例的第一行給出兩個整數，n(3≤n≤100)表示城市中學校的數目，m表示在它們之間可能的連接配接，用一個空格分開。接下來m行每行給出3個整數ai、bi、ci，其中ci是在學校ai和bi之間連接配接的成本(1≤ci≤300)。學校用從1到n的整數來編号。
對每個測試用例輸出一行，給出兩個整數，兩個最便宜的連接配接方案的成本，用一個空格分開。設s1是最便宜的連接配接方案的成本，s2是次便宜的連接配接方案的成本。s1=s2當且僅當有兩個最便宜的連接配接方案；否則s1≤s2。本題設定s1和s2是存在的。
簡述題意：在n個節點(學校)、m條邊(學校連接配接關系)組成的帶權(連接配接成本)連通圖中，計算最小生成樹的邊權和(最便宜的連接配接方案的成本)與次小生成樹的邊權和(次便宜的連接配接方案的成本)。
由于圖的節點數較少(3≤n≤100)，我們使用prim算法計算最小生成樹的邊權和ans1。在計算的過程中，順便記錄樹中每一對節點j、k間路徑上的最長邊權f［j］［k］。方法是：
若目前(v，k)進入生成樹，則搜尋生成樹内每個節點j，f［j］［k］=max{f［j］［v］，wvk}。
有了f［］［］和ans1，便可以計算次小生成樹的權值和ans2：
枚舉生成樹外的每一條邊(i，j)(1≤i，j≤n，(i，j)t)，計算加入(i，j)、删除生成樹中i與j間路徑上最長邊後的權值和增量(wij-f［j］［k］)。顯然ans2=min1≤i,j≤n,(i,j)t{ans1+wij-f［i］［j］}。
其實，最小生成樹問題的拓展形式是多種多樣的，并非隻有最優比率生成樹、次小生成樹和最小度限制生成樹三種。不僅僅是最小生成樹，其他經典的圖論模型亦是如此。這就需要我們在解決實際問題中，不能拘泥于經典模型，要因“題”制宜，适當對經典模型加以拓展，建立起符合題目本身特點的模型。當然，這并不是說經典模型已經被淘汰了，因為經典模型與模型拓展之間有着密切的孿生關系，一切拓展都建立在原模型的基礎之上。這就需要我們一方面娴熟掌握各種經典模型，另一方面根據實際情況靈活運用、大膽創新。隻有這樣，才能在難度日益增加的程式設計競賽中始終立于不敗之地。