⑴ 生成樹的標准有哪些各有什麼異同
一 區別
最小生成樹能夠保證整個拓撲圖的所有路徑之和最小，但不能保證任意兩點之間是最短路徑。
最短路徑是從一點出發，到達目的地的路徑最小。
二 實現方法
最小生成樹
最小生成樹有兩種演算法來得到：Prims演算法和Kruskal演算法。
Kruskal演算法：根據邊的加權值以遞增的方式，一次找出加權值最低的邊來構建最小生成樹，而且規定：每次添加的邊不能造成生成樹有迴路，知道找到N-1個邊為止。
Prims演算法：以每次加入一個的臨界邊來建立最小生成樹，直到找到N-1個邊為止。其規則為：以開始時生成樹的集合（集合U）為起始的定點，然後找出與生成樹集合鄰接的邊（集合V）中，加權值最小的邊來建立生成樹，為了確定新加入的邊不會造成迴路，所以每一個新加入的邊，只允許有一個頂點在生成樹集合中，重復執行此步驟，直到找到N-1個邊為止。
2 最短路徑
演算法描述
(這里描述的是從節點1開始到各點的dijkstra演算法，其中Wa->b表示a->b的邊的權值，d(i)即為最短路徑值)
1． 置集合S={2,3,n}, 數組d(1)=0, d(i)=W1->i(1,i之間存在邊) or +無窮大(1.i之間不存在邊)
2． 在S中，令d(j)=min{d(i),i屬於S}，令S=S-{j}，若S為空集則演算法結束，否則轉3
3． 對全部i屬於S,如果存在邊j->i，那麼置d(i)=min{d(i), d(j)+Wj->i}，轉2
Dijkstra演算法思想為：設G=(V,E)是一個帶權有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以後每求得一條最短路徑 , 就將 加入到集合S中，直到全部頂點都加入到S中，演算法就結束了），第二組為其餘未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大於從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。
演算法具體步驟
（1）初始時，S只包含源點，即S=，v的距離為0。U包含除v外的其他頂點，U中頂點u距離為邊上的權（若v與u有邊）或 ∞(若u不是v的出邊鄰接點）。
（2）從U中選取一個距離v最小的頂點k，把k，加入S中（該選定的距離就是v到k的最短路徑長度）。
（3）以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u（u U）的距離（經過頂點k）比原來距離（不經過頂點k）短，則修改頂點u的距離值，修改後的距離值為頂點k的距離加上邊上的權。
（4）重復步驟（2）和（3）直到所有頂點都包含在S中。
復雜度分析
Dijkstra 演算法的時間復雜度為O(n^2)空間復雜度取決於存儲方式，鄰接矩陣為O(n^2)
⑵ 計算機網路 STP
STP （Spanning Tree Protocol）是生成樹協議的英文縮寫搭衫孝。
生成樹協議 運行塌敬生成樹演算法(STA). 生成樹 演算法很復雜，但是其過程可以歸納為以下3個步驟：
（1）選擇根網橋
（2）選擇根埠
（3）選擇指定埠
First:BID（Bridge ID，網橋ID），因為根交換機的選舉是基於BID的，BID由三部分組成——優先順序、發送交換機的MAC地址、Extended System ID（擴展系統ID，可選項）
BID = 網橋ID=網橋優先順序+網橋MAC地址組成的
First：（PID）=埠ID等於優先順序加上埠編號，默認埠優先順序是128。
P:每個非根交換機有且只有一個根埠。
選舉根埠依照下面的順序：
首先，最低花費的埠將成為根埠；在花費相同的情況下比較發送者的BID，BID小的將成為根埠。--->
即:到根網橋最低的根路徑成本→發送BPDU的網橋ID(BID)較小→埠ID(PID)較小的。埠ID由埠優先順序與埠編號組成。
請看下面這張拓撲圖:
特殊的: 如果 發送者的BID相同,則比較發送者的PID:
關於選擇指定埠：每個網段上選擇一個指定埠。
P：每個網段有且只有一個指派埠
選擇順序為：根知稿路徑成本較低（花費較低）→發送BPDU的網橋ID值較小→本埠的PID值較小。
根網橋的介面皆為指定埠，因為根網橋上埠的根路徑成本為0 。
第一種情況:假設路徑花費不同的情況下 :
既不是根埠也不是指派埠的埠將被阻塞。看上圖
⑶ 最小生成樹的兩種演算法
主要有兩個：
1.普里姆（Prim)演算法
特點：時間復雜度為O(n2).適合於求邊稠密的最小生成樹。
2.克魯斯卡爾（Kruskal)演算法
特點：時間復雜度為O(eloge)(e為網中邊數），適合於求稀疏的網的最小生成樹。
⑷ 簡單生成樹協議的演算法原理
STP的工作過程是：首先進行根橋的選舉。選舉的依據是網橋優先順序和網橋MAC地址組合成的橋ID，橋ID最小的網橋將成為網路中的根橋，它的所有埠都連接到下游橋，所以埠角色都成為指定埠。接下來，連接根橋的下游網橋將各自選擇一條「最粗壯」的樹枝作為到根橋的路徑，相應埠的角色就成為根埠。循環這個過程到網路的邊緣，指定埠和根埠確定之後一棵樹就生成了。生成樹經過一段時間（默認值是30秒左右）穩定之後，指定埠和根埠進入轉發狀態，其他埠進入阻塞狀態。STP BPDU會定時從各個網橋的指定埠發出，以維護鏈路的狀態。