次小生成樹的兩種算法:
算法1、step 1. 先用prim求出最小生成樹T.
在prim的同時,用一個矩陣max[u][v] 記錄 在T中連結任意兩點u,v的唯一的
路中權值最大的那條邊的權值. (注意這里).
這是很容易做到的,因為prim是每次增加一個結點s, 而設已經標號了的結點
集合為W, 則W中所有的結點到s的路中的最大權值的邊就是當前加入的這條邊.
step 1 用時 O(V^2).
step 2. 枚舉所有不在T中的邊uv, 加入邊uv則必然替換權為max[u][v]的邊。
算法2、先用prim求出最小生成樹T。
枚舉T中的每一條邊,把它刪除,求剩下的圖的最小生成樹。選所有枚舉得到的生成樹中的最小的那一個。