生成樹演算法是

⑴ 圖的相關演算法（二）：最小生成樹演算法

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

例如，對於上圖中的連通網可以有多棵權值總和不相同的生成樹。

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

基本思想 ：按照權值從小到大的順序選擇n-1條邊，並保證這n-1條邊不構成迴路。
具體做法 ：首先構造一個只含n個頂點的森林，然後依照權值從小到大從連通網中選擇邊加入到森林羨冊乎中，並使得森林不產生迴路，直到森林變成一棵樹為止。

以圖G4為例（更詳細的可以參考《演算法導論》p367），對Kruskal進行演示（假設，用數組R保存最小生成樹結果）。

第1步 ：將邊<E,F>加入R中。
邊<兄悉E,F>的權值最小，因此將它加入到最小生成樹結果R中。
第2步 ：將邊<C,D>加入R中。
上一步操作之後，邊<C,D>的權值最小，因此將它加入到最小生成樹結果R中。
第3步 ：將邊<D,E>加入R中。
上一步操作之後，邊<D,E>的權值最小，因此將它加入到最小生成樹結果R中。
第4步 ：將邊<B,F>加入R中。
上一步操作之後，邊<C,E>的權值最小，但<C,E>會和已有的邊構成迴路；因此，跳過邊<C,E>。同理，跳過邊<C,F>。將邊<B,F>加入到最小生成樹結果R中。
第5步 ：將邊<E,G>加入R中。
上一步操作之後，邊<E,G>的權值最小，因此將它加入到最小生成樹結果R中。
第6步 ：將邊<A,B>加入R中。
上一步操作之後，邊<F,G>的權值最小，但<F,G>會和已有的邊構成迴路；因此，跳過邊<F,G>。同理，跳過邊<B,C>。將邊<A,B>加入到最小生成樹結果R中。

此時，最小生成樹構造完成！它包括的邊依次是： <E,F> <C,D> <D,E> <B,F> <E,G> <A,B> 。

根據前面介紹的克魯斯卡爾演算法的基本思想和做法，我們能夠了解到，克魯斯卡爾演算法重點需要解決的以下兩個問題：
問題一 對圖的所有邊按照權值大小進行排序。
問題二 將邊添加到最小生成樹中時，怎麼樣判斷是否形成了迴路。

問題一用排序演算法排序即可。
問題二，處理方式：記錄頂點在「最小生成樹」中的終點，頂點的終點是「在最小生成樹中與它連通的最大頂點"(關於這一點，後面會通過圖片給出說明)。然後每次需要將一條邊添加到最小生成樹時，判斷該邊的兩個頂點的終點是否重合，重合的話則會構成迴路。 以下圖來進行說明：

在將<E,F> <C,D> <D,E>加入到最小生成樹R中之後，這幾條邊的頂點就都有了終點：

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

普里姆（Prim）演算法，也是求加權連通圖的最小生成樹的演算法。

基本思想
對於圖G而言，V是所有頂點的集合；現在，設置兩個新的集合U和T，其中U用於存放G的最小生成樹中的頂點，T存放G的最小生成樹中的邊。從所有的 uЄU ，vЄ(V-U)（V-U表示除去U的所有頂點）的邊中選取權值最小的邊（u，v），將頂點v加入U中，將邊（u,v）加入集合T中，如此不斷重復，直到U=V為止，最小生成樹構造完畢，此時集合T中包含了最小生成樹中的所有邊。

以上圖G4為例，來對普里姆進行演示(從第一個頂點A開始通過普里姆演算法生成最小生成樹)。

初始狀態 ：V是所有頂點的集合，即V={A,B,C,D,E,F,G}；U和T都是空！
第1步 ：將頂點A加入到U中。
此時，U={A}。
第2步 ：將頂點B加入到U中。
上一步操作之後，U={A}, V-U={B,C,D,E,F,G}；因此，邊(A,B)的權值最小。將頂點B添加到U中；此時，U={A,B}。
第3步 ：將頂點F加入到U中。
上一步操作之後，U={A,B}, V-U={C,D,E,F,G}；因此，邊(B,F)的權值最小。將頂點F添加到U中；此時，U={A,B,F}。
第4步 ：將頂點E加入到U中。
上一步操作之後，U={A,B,F}, V-U={C,D,E,G}；因此，邊(F,E)的權值最小。將頂點E添加到U中；此時，U={A,B,F,E}。
第5步 ：將頂點D加入到U中。
上一步操作之後，U={A,B,F,E}, V-U={C,D,G}；因此，邊(E,D)的權值最小。將頂點D添加到U中；此時，U={A,B,F,E,D}。
第6步 ：將頂點C加入到U中。
上一步操作之後，U={A,B,F,E,D}, V-U={C,G}；因此，邊(D,C)的權值最小。將頂點C添加到U中；此時，U={A,B,F,E,D,C}。
第7步 ：將頂點G加入到U中。
上一步操作之後，U={A,B,F,E,D,C}, V-U={G}；因此，邊(F,G)的權值最小。將頂點G添加到U中；此時，U=V。

此時，最小生成樹構造完成！它包括的頂點依次是：A B F E D C G。

⑵ 生成樹演算法

「生成樹」資料

交換機內的生成樹演算法（STA）使你可以創建一條備用鏈路（當網路中存在多台交換機時）。在主鏈路正常工作時，備用鏈路處於空閑狀態（不工作）；只有在主鏈路出現問題時，備用鏈路才不需要任何人工干預自動地接替主鏈路。

這種自動重構的功能，使得網路上的用戶能夠最大限度地與網路保持正常的連接。生成樹演算法較復雜，所以，建議最好在充分研究理解其之後，再更改其一些設置。請仔細閱讀並理解下述內容之後，再去更改交換機上的生成樹的默認設置。

網路環路的偵測和預防（Network loop detection and prevention）：任何兩個區域網之間應該只有一條路徑，否則，網路中將出現環路。如果存在著多於一條的路徑，那麼生成樹演算法將會偵測到環路的發生，並自動選擇開銷值（c ost）最低的那條路徑作為可使用的路徑（主鏈路），而阻斷其它路徑，將它們作為備用路徑（備用鏈路）。

自動拓撲重構（Automatic topology re-configuration）：當主鏈路出現故障時，生成樹演算法將自動啟用備用鏈路，重構網路結構。

生成樹的級別（STA Operation Levels）

生成樹有兩種工作級別：橋級別（bridge level）和埠級別（port level）。在橋一級上，生成樹演算法為每台交換機計算橋的標志級數（Bridge Identifier），然後設定根橋（Root Bridge）和指定橋（Designated Bridges）。而在埠一級上，生成樹演算法設定根埠（Root Port）和指定埠（Designated Ports）。詳述如下：

在橋一級上（On the Bridge Level）：

根橋（Root Bridge）：具有最小橋標志級數的（lowest Bridge Identifier）交換機是根橋（Root Bridge）。當然，你希望根橋是環路中所有交換機當中最好的一台（交換機），以保證能夠提供最好的網路性能和可靠性。

橋標志級數（Bridge Identifier）：橋標志級數是橋的優先順序（Bridge Priority）和交換機的MAC地址的綜合數值，其中橋的優先順序（Bridge Priority）是一個你可以設定的參數。例如，「4 00 80 C8 00 01 00」中的「4」是橋的優先順序，「00 80 C8 00 01 00」是交換機的MAC地址。交換機的橋標志級數越低，則交換機的優先順序越高，這樣可以增加其成為根橋的可能性。

指定橋（Designated Bridge）：在每個網段中，到根橋（Root Bridge）的路徑開銷最低的（lowest Root Path Cost）橋將成為指定橋（Designated Bridge），數據包將通過它轉發到網段。一旦所有的交換機具有相同的根路徑開銷（Root Path Cost），那麼具有最低的橋標志級數的（lowest Bridge Identifier）交換機才會被定為指定橋（De signated Bridge）。

根路徑開銷（Root Path Cost）：一台交換機的根路徑開銷（Root Path Cost）是根埠（Root Port）的路徑開銷（Path Cost）與數據包經過的所有交換機的根路徑開銷（Root Path Cost）之和。根橋（Root Bridge）的根路徑開銷（Root Path Cost）是零。

橋的優先順序（Bridge Priority）：是一個用戶可以設定的參數。設定的值越小，優先順序越高。交換機具有越高的優先順序，才越有可能成為根橋。

在埠一級上（On the Port Level）：

根埠（Root Port）：每台交換機都有一個根埠（Root Port），這個埠到根橋的路徑開銷最低。一旦多個埠具有相同的到根橋的路徑開銷時，那麼具有最低的埠標志級別的才會成為根埠。

指定埠（Designated Port）：指定埠就是指定橋（Designated Bridge）上的埠。

埠優先順序（Port Priority）：數值越小，埠的優先順序就越高。具有越高埠優先順序，才越有可能成為根埠。

路徑開銷（Path Cost）：這是一個可變的參數，它將隨著生成樹中的設定值的變化而變化。依據STA的默認參數值，每個1000Mbps網段有一個指定的路徑開銷值為4 ，100Mbps網段的路徑開銷值19，10Mbps網段的路徑開銷值100.

生成樹參數（STA Parameters）

生成樹的參數用戶可以根據自己的需要進行修改，但是建議最好使用出廠時的默認設置。除非確實需要對出廠設置值進行變動時，再去改動默認值。用戶可以改動的生成樹參數有如下幾個：

橋優先順序（Bridge Priority）：數值范圍從0到65535.「0」的優先順序最高。

呼叫時間（Bridge Hello Time）：數值范圍從1秒到10秒。是指根橋向其它所有交換機發出BPDU數據包的時間間隔，以告知其它所有交換機它是根橋。如果你的交換機還未是根橋時為其設置了呼叫時間，那麼，一旦你的交換機成為根橋，該呼叫時間就會派上用處。

注意：呼叫時間不能大於橋的最大老化時間（Max. Age），否則，將出現錯誤信息。

最大的橋老化時間（Bridge Max. Age）：數值范圍從6秒到40秒。如果在超出最大老化時間之後，還沒有收到根橋發出的BPDU數據包，那麼，在允許的條件下你的交換機將充當根橋向其它所有的交換機發出B PDU數據包。如果交換機確實具有最小的橋標志級數，那麼，它將隨之成為根橋。

橋轉發時延（Bridge Forward Delay）：數值范圍從4秒到30秒。是指交換機的埠從阻塞狀態轉為轉發狀態所用的監聽時間。

當你欲變動生成樹參數時，請一定記住下述公式：

最大的橋老化時間≤ 2 x（橋轉發時延 – 1秒）

即：Max. Age ≤ 2 x （Forward Delay - 1 second）

最大的橋老化時間≥ 2 x（呼叫時間 + 1秒）

即：Max. Age ≥ 2 x （Hello Time + 1 second）

埠優先順序（Port Priority）：數值范圍從0到255.數值越小，那麼該埠越可能成為根埠。

⑶ 最小生成樹的兩種演算法

主要有兩個：
1.普里姆（Prim)演算法
特點：時間復雜度為O(n2).適合於求邊稠密的最小生成樹。
2.克魯斯卡爾（Kruskal)演算法
特點：時間復雜度為O(eloge)(e為網中邊數），適合於求稀疏的網的最小生成樹。