肖玲玲 范海輝

摘要：最小生成樹算法是數(shù)據(jù)結(jié)構中，求網(wǎng)絡模型耗費代價最優(yōu)解的一個重要工具?，F(xiàn)實生活中的連通網(wǎng)絡模型復雜而多變，有時還需兼顧其它的目標，一棵最小生成樹不足以解決問題，因此找出所有的最小生成樹是很有必要的，在此提出一種新的尋找所有最小生成樹的算法——最小差值法。無向連通圖網(wǎng)絡通過去掉連枝生成最小生成樹，一個連枝加入最小生成樹形成一個圈。這種算法是在一個圈中，用連枝的權與其它樹枝的權分別作差，求最小差值。由最小差值是否為零，判斷原有的最小生成樹能否通過換進換出邊，生成新的最小生成樹。該算法能夠有規(guī)律、高效率的尋找出所有的最小生成樹。在找出的所有最小生成樹方案中，選擇符合實時情況的最小生成樹方案，該方案即為網(wǎng)絡耗費代價的最優(yōu)解。

關鍵詞：網(wǎng)絡耗費代價；連通網(wǎng)絡模型；最小生成樹；算法；最小差值法

中圖分類號 TP311.12 文獻標識碼：A 文章編號：1009-3044（2014）28-6650-09

最小生成樹在生活中有廣泛的實際應用[1-3]，經(jīng)常用于求網(wǎng)絡模型耗費代價的最優(yōu)解。例如：實際生活中會遇到電力網(wǎng)路，通信線路，交通線路等求鋪設總代價最小問題，這類問題通?？赊D(zhuǎn)化為最小生成樹問題[4]。幾十年來，人們對生成樹相關的問題研究的很深刻，先后誕生了很多優(yōu)秀的相關算法，如Kruskal算法[5]，Prim算法[6]，破圈法[7] Dijkstra算法[8]等，還有對最小生成樹算法的分析[9]，有最新研究表明：生成樹個數(shù)與無向連通圖的無向圈定向數(shù)有關[10]。然而在實際生活中，往往還要兼顧其它因素，其中有些因素是無法控制和預測的。一棵最小生成樹對應一種解決方案，一種方案不足以應對這些復雜多變的問題，因此找到所有的解決方案是必要的，與此對應的需要求出全部最小生成樹。只有在全部最小生成樹中，選擇與實時情況匹配程度最高的最小生成樹，才能更好的解決問題?；凇捌迫Ψā泵看稳サ羧χ凶铋L的邊的思想，在一個圈中去掉的邊若不是唯一最長邊，則選擇去掉邊的可能性有多種。在一個基本回路中，使連枝與圈中其它樹枝兩者比較權值大小，并作差求最小差值。根據(jù)最小差值是否為零，來判斷多個最小生成樹的存在情況，就此提出了一種新的求所有最小生成樹的算法。

1 理論根據(jù)

1.1 最小生成樹的定義

定義1[11]：設G=（V，E）為無向連通帶權圖。若T是一個包含G的所有頂點且無回路的連通子圖，則T為圖G的一顆生成樹。圖G的所有最小生成樹中，各邊權值之和最小的生成樹稱為最小生成樹。

1.2 破圈法相關定義

定義2[12]：設T=（V，E）是G的一棵生成樹，則T為最小生成樹樹的充要條件是：對于任意不屬于E的邊e，在把e加入T后的子圖的唯一圈中，e是最長邊。

定義3[13]：設T=（V，E）是G的一棵生成樹，e是屬于G，而不屬于E的一條邊。把e加入T所得的子圖中必存在唯一的一個圈。

定義4[14]：將無向連通圖G=（V，E）按照兩句話反復進行：“任取一個圈，去掉圈上最長的邊。”直到圖上沒有圈時為止，這時，剩下的邊組成的子圖就是要找的最小生成樹，這種方法叫做破圈法。

定義5[15]：不含圈的圖稱為無圈圖，連通圖的無圈圖稱為樹。在樹的任意二個點之間添加一條邊，稱得到的圈為一個基本圈。

2 最小差值法

2.1最小差值法的方法

一個連枝加入最小生成樹形成唯一的一個圈。在一個圈中令連枝的權值不斷和其它樹枝權值進行作差，求出最小差值，將符合“差值為零”這個條件的連枝和樹枝進行換邊操作：連枝換進圈中，樹枝換出圈外。換邊操作完成后，可形成新的最小生成樹。選取不同的圈進行換邊操作，直到能找到所有的最小生成樹。

2.1.1相關定義

最小差值法的相關定義如下：

1）最小生成樹的連枝和樹枝。設T=（V，E）是G的一棵最小生成樹，存在邊ei，px∈G。邊ei∈T，ei稱為樹枝， px ?T，px稱為連枝。設P={p1，p2，…，pX，…，pn}為連枝集合。

2） 無向連通圖中的圈（或稱為基本回路）。由定義3和定義5可知： 任意連枝px∩T都會形成唯一的一個圈（或稱為一個基本回路），將圈記為Cx。在圈Cx中除邊px外，其它邊均為樹枝exi，exi∈T。px∈Cx，exi∈Cx。連枝集合P={p1，p2，…，pX，…，pn}對應著圈集合C={C1，C2，…，CX，…，Cn}。

3） 最小差值函數(shù)。最小差值法定義一個最小差值函數(shù)為：Min（pX）=min（w（pX）-w（exi））。Min（pX）為圈CX中連枝px的最小差值函數(shù)，w（pX）和w（exi）分別為圈CX中的連枝pX和樹枝exi的權值。min（w（pX）-w（exi））表示連枝pX的權分別與圈中其它的樹枝exi的權作差，最后只輸出最小的差值。

4）置換操作。圈CX中所有符合條件w（pX）=w（exi）的邊可組成一個置換對（pX，exi）。針對置換對的概念提出一種置換對的置換操作的方法，該方法將樹枝exi從圈CX中去掉，將連枝pX加入圈CX中，也即用連枝pX替換掉樹枝exi。

2.1.2最小差值法的步驟

最小差值法的步驟如下：

1）用破圈法求出一棵最小生成樹T0，并找出所有的連枝。

2） 求出所有連枝的最小差值函數(shù)值Min（pX）。若函數(shù)值為0，則該連枝達到置換要求。

3） 將所有達到置換要求的連枝所在的圈，組成一個新的集合B={b1，b2，…，by，…，bm}，每一個圈為一個置換組，則一共存在m個置換組，每個置換組只能同時選取一個置換對進行置換操作。

4）在m個置換組中，同時選取a個置換組參與置換操作，最后形成新的最小生成樹。

2.2最小差值函數(shù)的相關證明

推論1：若圈CX的最小差值函數(shù)Min（pX） ≥0，則T為最小生成樹。[]

證明：由Min（pX） ≥0說明pX的權值在圈CX中最大，pX為CX的最長邊。根據(jù)定義2， T為最小生成樹。

推論2：若圈CX的最小差值函數(shù)Min（pX） >0，則該最小生成樹是唯一的。

證明：由Min（pX） >0說明pX的權值在圈CX中最大，且pX為CX中唯一的最長邊。根據(jù)破圈法定義4，每次去掉圈上最長的邊。此時pX為CX中唯一的最長邊，在圈CX中，每次一定先去掉pX，則剩下的樹枝不會產(chǎn)生變更。由這些不變更的樹枝組成的最小生成樹是唯一的。

推論3：若圈CX的最小差值函數(shù)Min（pX）=0， 則圖G的最小生成樹不唯一。

證明：由Min（pX）=0說明pX的權值在圈CX中最大，pX不是CX中唯一的最長邊。即圈CX中存在樹枝exi，使w（pX）=w（exi）。根據(jù)定義4，每次去掉圈上最長的邊。則在圈CX去掉最長邊時，可能去掉pX，也可能去掉exi。去掉的邊有多種可能，則剩下的樹枝也可能會產(chǎn)生變更。由這些會變更的樹枝組成的最小生成樹不是唯一的。

2.3用最小差值法求全部最小生成樹

2.3.1找出所有的置換組

只有當Min（pX）=min（w（pX）-w（exi））=0時，圖G的最小生成樹不是唯一的。在圈集合C中，找出符合條件Min（pX）=min（w（pX）-w（exi））=0的所有圈集合B={b1，b2，…，by，…，bm}，每一個圈為一個置換組，則一共存在m個置換組。

2.3.2找出置換組中所有的置換對以及置換對的選取原則

1） 選取原則1：每個置換回路只能選取一個置換對

任選第y個置換組by（1≤y≤m），假設在圈by中符合條件w（pX）=w（exi）的樹枝exi有q個，即{ex1， ex2，…， exk，…exq}，構建置換對（pX，exi）。一個置換對（pX，exi）表示將樹枝exi從圈by中去掉，將連枝pX加入圈by中。也即用連枝pX替換樹枝exi。

在m個置換組中同時選取a個置換組，這用概率統(tǒng)計的[Cam]表示，令[Cam=d]，表示有 d種選擇置換組方案可供選擇。在這些被選擇的某個置換組中，存在這樣的情況：在該組中，有多個樹枝exi可以被連枝pX替換，即存在多組置換對。第y組的置換對集合為{（pX，ex1），…， （pX，exk），…， （pX，exq）}。

圖1 一個基本回路 Cy

假設存在如圖1中的一個基本回路Cy。邊<1，5>是連枝，邊<1，2><2，3><3，4><4，5>是樹枝。在這個回路里，存在4個置換對：

（<1，5>，<1，2>）（<1，5>，<2，3>）（<1，5>，<3，4>）（<1，5>，<4，5>）。在這個回路里，雖然有4個置換對可進行替換操作，但最終只能選取一個置換對進行替換操作。用Δ（pX）表示圈by中置換對的個數(shù)，則對于符合置換條件的任意連枝pX，都有Δ（pX）≥1（Δ（pX）為正整數(shù)）。圖1基本回路 Cy中的Δ（pX）=4。

2） 選取原則2：不同置換組間的置換對的沖突情況

當2個或2個以上的置換組同時進行置換操作時，置換組間的置換對有可能產(chǎn)生沖突。如存在圖2這樣的一個無向連通圖。

圖2 一個無向連通圖 G1

圖2中有兩個連枝，連枝AD和連枝DC。圖2有兩個基本回路，第一個基本回路Cp為A→B→D→A，第二個基本回路Cq為B→C→D→B。一個基本回路為一個置換組，第一個置換組的置換對為（AD，AB）和（AD，BD），第二個置換組的置換對為（DC，BD）和（DC，BC）?，F(xiàn)在對這兩個置換組進行置換操作，每個置換組只能選取一個置換對。第一組的置換對選擇（AD，BD），第二組選擇（DC，BD）。

在第一個基本回路Cp中，連枝AD換入Cp，將樹枝BD換出Cp；同時在第二個基本回路Cq中，連枝DC換入Cq，將樹枝BD換出Cq，兩組同時進行置換操作后，得到的不是一顆最小生成樹，而是一個基本回路。原因是這兩個回路同時都將樹枝BD換出回路，而樹枝BD是唯一的一個樹枝，這就造成了置換對換邊沖突的情況。當a（a≥2）個置換組同時進行置換操作時，會出現(xiàn)a個置換對（pk1，exi），…， （pXi，exi），…， （pka，exi），有若干個置換對含有相同的樹枝，這算一種沖突情況。假設在a（a≥2）個置換組時，造成這種置換對的換邊沖突的情況總共有β（ha）種，這些情況應該被舍棄。

2.3.3置換過程

找出m個所有的置換組，a為同時進行換邊操作的置換組個數(shù)。符合置換要求的每個圈為一個置換組，每個置換組有Δ（pX）個置換對。每個置換組最終只能選擇一個置換對。

a=1時，表示同時只有1個置換組參與置換。在符合置換條件的集合B={b1，b2，…，by，…，bm}中任選一個置換組，在該置換組中任選一個置換對（pX，exi），然后進行邊的置換操作。

a=k時，表示同時有k個置換組參與置換，在符合置換條件的集合B={b1，b2，…，by，…，bm}中任選k個基本回路。將選取的k個基本回路，均進行這樣的操作：在每一個置換組中任選一個置換對（pX，exi），然后進行邊的置換操作，直到完成k個圈的置換操作，當然要遵守置換對的選取原則2，刪掉β（ha）種沖突情況。

a=m時，以此類推，直到輸出所有的最小生成樹。

2.3.4求所有最小生成樹的個數(shù)

假設m個圈中，同時只有a個置換組參與置換。把a個置換組組成一個集合D={d1，d2，…，di，…，da}，D∈B∈C。每一個置換組中存在[Δpxi]個置換對。同時選取a個置換組時，則一共有[y=1zpxi∈DΔpxi-βha]種情況。其中

[pxi∈DΔpxi=Δpx1，d1×Δpx2，d2×...×Δpxi，di×...×Δppa，da]

[Δpxi，di]表示圈[di]存在[Δpxi]個置換對，[z=Cam]。

在前提條件中，已經(jīng)給出了一棵最小生成樹T0，所以全部最小生成樹的總個數(shù)為：[a=1mΔpxa+a=2my=1zpxi∈DΔpxi-βha+1]（其中[z=Cam]）

2.4最小差值法的算法實現(xiàn)

算法具體實現(xiàn)步驟如下：

第一步：用破圈法求出一棵最小生成樹T0；

第二步：最小差值函數(shù)Min（pX）=min（w（pX）-w（exi））判斷最小生成樹的唯一性；

Step1：令圈集合C={C1，C2，…，CX，…，Cn}，先令x=1；

Step2：選取一個圈Cx，Cx∈C。求圈Cx的最小差值函數(shù)值；

Step3：x=x+1，如果x≤m，返回Step2；

Step4：輸出集合為：

Min={Min（p1），…，Min（px），…，Min（pn） }

Step5：若Min（pX） >0（0

Step6：若Min（pX） =0（0

第三步：找出所有置換組和置換對

Step1：找出符合Min（pX） =0這個條件的所有圈集合B={b1，b2，…，by，…，bm}，B∈C，令y=1；

Step2：一個圈by為一個置換組，在圈by中符合條件w（pX）=w（exi）的連枝pX和樹枝exi可組成一個置換對（pX，exi）。

Step3：y=y+1，如果y≤m，返回Step2；

Step4：找到m個置換組，且每個置換組中的置換對已全部找出。

第四步：求所有的最小生成樹

Step1：若集合B為空集合，則最小生成樹是唯一的，輸出T0后結(jié)束算法；

Step2：a為同時換邊的置換組的個數(shù)。先令a=1；

Step3：在B={b1，b2，…，by，…，bm}中任選取a個置換組，并且在每個置換組中任選取一個置換對；

Step4：設替換后的樹為Taj。符合Min（pX） =0這個條件共有m個圈，在m個圈中任選a個置換組同時進行置換操作，用概率統(tǒng)計中[Cam]表示。置換組的置換操作主要是指置換對的置換操作，每個置換組內(nèi)有[Δpxi]個置換對，則同時選取a個置換組一共有d種情況。其中當a=1時，[d=i=1mΔpxi]；a≥2時，[d=y=1zpxi∈DΔpxi-βha]，1≤j≤d；

Step5：a=a+1，如果a≤n，返回Step3；

3 應用舉例

3.1 實例

為促進經(jīng)濟交流發(fā)展，某市決定在ABCDEFGH這八個縣城之間鋪建公路，使縣城網(wǎng)絡線路之間的交通網(wǎng)絡能夠連通起來.鋪設公路網(wǎng)絡示意圖如圖3。無向圖G的邊代表鋪建的公路，邊上的權值表示兩縣之間需要鋪建的路程?，F(xiàn)該市派施工組前往實地考察，結(jié)果發(fā)現(xiàn)G縣和D縣周圍環(huán)繞著群山。若要鋪建通往G縣和D縣的公路，必須要打通山體，修建隧道。如鋪建公路AG、HG、BG、GF、DE、DF、DC均需要修建隧道?，F(xiàn)在施工組鋪建公路使所有縣城交通連通起來，在盡量少修建隧道的條件下，如何鋪設公路，使總的鋪設路程最小（外界環(huán)境條件：（1）每條線路打通隧道所花費的代價是一樣的。（2）兩個縣城之間修建公路的主要耗費代價為鋪設路程的距離代價，距離代價優(yōu)先于修建隧道代價。）

圖3 無向圖 G

3.2 用最小差值法求出所有最小生成樹

1） 如圖3為一個無向圖G，圖4為圖G的一棵已知最小生成樹T0；

2） 連枝為圖G中的邊

3） 連枝與樹枝，組成圈A→H→G→A，連枝與樹枝組成基本回路A→G→B→A，連枝與樹枝組成圈B→G→F→D→C→B，連枝與樹枝組成圈C→D→F→C，連枝與樹枝組成圈D→F→E→D。

4） 求出每個連枝的最小差值函數(shù)

[MinA，H=MinwA，H-wH，G，wA，H-wA，G=Min3-3，3-3=0]

[MinA，B=MinwA，B-wA，G，wA，B-wB，G=Min6-3，6-6=0]

[MinB，C=MinwB，C-wB，G，wB，C-wG，F(xiàn)，wB，C-wF，D，wB，C-wD，C=Min8-6，，8-6，8-3，8-5=1]

[MinC，F(xiàn)=MinwC，F(xiàn)-wC，D，wC，F(xiàn)-wF，D=Min6-5，6-3=1]

[MinE，D=MinwE，D-wD，F(xiàn)，wE，D-wF，E=Min5-3，5-4=1]

由于存在Min（）=0和Min（）=0，則圖的最小生成樹不是唯一的。有兩個Min（pX） =0，表示有兩個置換組。第1個置換組為（，）（，），置換組內(nèi)有兩個置換對，則Δ（）=2。第2個置換組為（，），則Δ（）=1。

5） 找出所有最小生成樹。

a為同時進行邊置換操作的置換組個數(shù)。

①a=1時，表示同時只有1個置換組參與置換。

首先對第一組進行替換，w（）=w（），用第一組中的連枝換掉樹枝得到最小生成樹T1。

圖5 最小生成樹 T1

w（）=w（），用第一組中的連枝換掉另一個樹枝得到最小生成樹T2。

圖6 最小生成樹 T2

再對第二組進行替換，w（）=w（），用第二組中的連枝換掉樹枝得到最小生成樹T3。

圖7 最小生成樹 T3

②a=2，表示同時有2個置換組參與置換。

用第一組中的連枝換掉樹枝，再用第二組中的連枝換掉樹枝得到T4。

圖8 最小生成樹 T4

用第一組中的連枝換掉另一個樹枝，再用第二組中的連枝換掉樹枝得到T5。

圖9 最小生成樹 T5

6） 求所有最小生成樹的個數(shù)。

所有最小生成樹的個數(shù)為 [a=1mΔpxa+a=2my=1zpxi∈DΔpxi-βha+1]（其中[z=Cam]）

代入具體數(shù)值進行計算：

[i=1mΔpxi=2+1=3]

[z=Cam=C22=1]

[y=1zpxi∈DΔpxi-βha=2×1-0=2]

[a=1mΔpxa+a=2my=1zpx∈DΔpx-βha+1=3+a=22y=1zpx∈DΔpx-βha+1=3+y=1zpx∈DΔpx-βha+1=3+2+1=6]

即圖G所有最小生成樹個數(shù)為6個。這與實例中找出的所有最小生成樹T0 T1 T2 T3 T4 T5共有六棵最小生成樹相符合。

3.3實例解決方案分析

無向連通圖G的6棵最小生成樹代表6種解決方案，這6種方案都能使總鋪設距離最小。G縣和D縣周圍環(huán)山，若要少修建隧道，則通往G縣和D縣的公路盡可能少，即令頂點G和頂點D的度盡可能小。

表1 最小生成樹頂點G和頂點D的度

[最小生成樹＼&頂點G的度Degree（G）＼&頂點D的度Degree（D）＼&T0＼&4＼&2＼&T1＼&3＼&2＼&T2＼&3＼&2＼&T3＼&3＼&2＼&T4＼&2＼&2＼&T5＼&2＼&2＼&]

由表1分析得到：在所有最小生成樹中，最小生成樹T4和T5中的頂點G和頂點D的度是最小的。所以T4和T5為最佳方案。

4 最小差值法和傳統(tǒng)窮舉算法的比較

4.1 時間復雜度的比較

4.1.1傳統(tǒng)窮舉算法求全部最小生成樹

傳統(tǒng)窮舉算法是指：將一個帶權無向圖進行遍歷，窮舉出所有的生成樹情況，然后再在該無向圖中挑選出全部的邊權值之和最小的生成樹。根據(jù)定義1，這樣找出的生成樹即為全部的最小生成樹。

時間復雜度分析：帶權無向圖的每一條邊都有可能是某棵最小生成樹的組成部分，所以每一條邊都有兩種狀態(tài)。當一條邊被選進最小生成樹的組成部分時，記為狀態(tài)“1”；當這條邊是被舍棄的連枝時，記為狀態(tài)“0”。若該帶權無向圖有n條邊時，每一條邊都有2種狀態(tài)，則一共有2n種情況。因此傳統(tǒng)窮舉算法的時間復雜度為O（2n）。

4.1.2最小差值法求全部最小生成樹

最小差值法：已知一棵由n條邊的帶權無向圖G得到最小生成樹T0，將p個連枝加入最小生成樹T0，從而形成p個基本回路。在這p個基本回路中，用最小差值函數(shù)找出m個符合置換條件的基本回路（m

時間復雜度分析：

由[a=1mΔpxa+a=2my=1zpxi∈DΔpxi-βha+1] （其中[z=Cam]）最小生成樹個數(shù)公式可知，最小差值法的主要時間耗費在置換組的挑選和置換組間的組合上面。m個基本回路同時選取a個置換組參與置換操作，即[Cam]。

[a=1mΔpxa=Δpx1+Δpx2+......+Δpxm=N1]，[Δpxa]是一個常數(shù)值，它表示置換組內(nèi)置換對的個數(shù)，所以[N1]是一個常數(shù)值。

[a=2my=1zpxi∈DΔpxi-βha=C2m×px1∈DΔpx1+......+pxy2∈DΔpxy2-βha2+C3m×px1∈DΔpx1+......+pxy3∈DΔpxy3-βha3+......+Ckm×px1∈DΔpx1+......+pxyk∈DΔpxyk-βhak+......+Cmm×px1∈DΔpx1+......+pxym∈DΔpxym-βham]

其中設

[px1∈DΔpx1+......+pxym∈DΔpxyk-βhak=Nk]

[Δpxa]是一個常數(shù)值，同理[pxyk∈DΔpxyk]也是一個常數(shù)值，[βhak]是置換中的沖突情況，它也是個常數(shù)值。因此很顯然[Nk]是一個常數(shù)值，所以

[a=2my=1zpxi∈DΔpxi-βha=C2m×N2+C3m×N3+......+Ckm×Nk+......+Cmm×Nm]

那么則有：

[a=1mΔpxa+a=2my=1zpxi∈DΔpxi-βha+1=N1+C2m×N2+C3m×N3+......+Cam×Na+.....+Cmm×Nm+1]

由[C0m+C1m+C2m+......+Cam+......+Cmm=2m]可知，[a=1mΔpxa+a=2my=1zpxi∈DΔpxi-βha+1]的數(shù)量級為O（2m）。

所以用最小差值法求全部最小生成樹的最壞時間復雜度的數(shù)量級為O（2n）。

兩種算法的時間復雜度均在O（2n）這個數(shù)量級上，根據(jù)這個數(shù)量級可知求全部最小生成樹是個NP完全問題，它沒有一個多項式時間可解的算法，只能在這個問題上將算法在某些部分進行選擇性的優(yōu)化。

4.2 性能分析比較

4.2.1 傳統(tǒng)窮舉算法

傳統(tǒng)窮舉算法是指遍歷無向完全圖的每一條邊，窮舉出所有路徑，沒有優(yōu)化效果。

4.2.2 最小差值法

用最小差值函數(shù)Min（pX）=min（w（pX）-w（exi））去檢驗由p個連枝加入最小生成樹T0形成的p個基本回路。對于不符合最小差值函數(shù)為零的基本回路，刪除該回路中的連枝。圖G中刪除這些連枝邊，避免了一些無用的連枝邊的遍歷，對圖G進行了約化。

設圖有p個連枝，將p個連枝加入最小生成樹T0，形成p個基本回路。在p個基本回路中，符合置換條件Min（pX） =0基本回路有m個（m

圖10 分析圖

如圖10中，橫坐標單位為“/個”，表示連枝個數(shù)；縱坐標單位為“/%”，表示圖G中刪除邊的比例。

從分析圖中可得到結(jié)論：

當p為一個定值時，m的值越小則y的值越大；或是當m的值一定時，p的值越大則y的值越大。y的值越大說明圖G中刪除邊的比例越大，圖G的約化程度越大，圖G中不需要遍歷的邊的個數(shù)越多。

當m<

最小差值法的實際應用意義在于首先用最小差值法找出解決問題的所有方案；其次，針對實際約束條件，在已提出的方案中進行方案的二次選擇。在找到最終合適方案的過程中，這種二次選擇也實現(xiàn)了一種問題解決的再次優(yōu)化。

5 結(jié)論

基于“破圈法”去掉圈中最長邊的思想，提出一種新的求所有最小生成樹的算法——最小差值法。在一個圈中令連枝的權值不斷和其它樹枝權值進行作差，以最小差值是否等于零為標準，刪去不符合置換條件的圈的連枝，完成圖的初始約化。當圖的規(guī)模非常大的時，對圖的約化操作能使邊的遍歷次數(shù)減少，算法效率提高。

將符合“最小差值為零”條件的圈中的連枝和樹枝進行置換操作：連枝換進圈中，樹枝換出圈外。選取不同的圈進行換邊操作，最終能找到所有的最小生成樹，并能計算出所有的最小生成樹的個數(shù)。

參考文獻：

[1] 王化宇. 最小生成樹算法及其應用[J]. 內(nèi)蒙古科技與經(jīng)濟， 2011（6）：72-73.

[2] 段東東. 最小生成樹算法及其應用 [J]. 西安航空技術高等?？茖W校學報， 2010（1）：55-57.

[3] 袁衛(wèi)東. 最小生成樹的算法及其應用 [J]. 科學技術與工程， 2009，9（15）：4409-4412.

[4] Salama H F， Reeves D S， Viniotis Y. The delay-constrained minimum spanning tree problem[C]//Computers and Communications， 1997. Proceedings.， Second IEEE Symposium on. IEEE， 1997： 699-703.

[5] Kruskal J B. On the shortest spanning subtree of a graph and the traveling salesman problem[J]. Proceedings of the American Mathematical society， 1956， 7（1）： 48-50.

[6] Prim R C. Shortest connection networks and some generalizations[J]. Bell system technical journal， 1957， 36（6）： 1389-1401.

[7] 管梅谷. 求最小樹的破圈法[J]. 數(shù)學的實踐與認識， 1975，5（4）：38-41.

[8] Dijkstra E W. A note on two problems in connexion with graphs[J]. Numerische mathematik， 1959，1（1）：269-271.

[9] Edmonds J. Paths， trees， and flowers[J]. Canadian Journal of mathematics， 1965，17（3）：449-467.

[10] Thomassen C. Spanning trees and orientations of graphs[J]. Journal of Combinatorics， 2010，1（2）：101-111.

[11] 王海英. 圖論算法及其MATLAB實現(xiàn)[M] 北京：北京航空大學出版社，2010.

[12] Ford D R， Fulkerson D R. Flows in networks[M]. Princeton university press， 2010.

[13] C.貝爾熱.圖的理論及其應用[M].李修睦，譯.上海：上?？茖W技術出版社，1963.

[14] 董躍華， 李云浩， 姜在東. 用破圈法實現(xiàn)普里姆算法[J]. 江西理工大學學報ISTIC， 2008，29（4）：20-22.

[15] 田豐， 圖論， 馬仲蕃. 圖與網(wǎng)絡流理論[M]. 北京：科學出版社， 1987.