次小生成樹的定義
設 G=(V,E,w)是連通的無向圖，T 是圖G 的一個最小生成樹。如果有另一棵樹T1，滿
足不存在樹T',ω（T'）<ω（T1） ，則稱T1是圖G的次小生成樹。
求解次小生成樹的算法
約定：由T 進行一次可行交換得到的新的生成樹所組成的集合，稱為樹T的鄰集,記為N(T)。
定理 3：設T是圖G的最小生成樹，如果T1滿足ω(T1)=min{ω(T')| T'∈N(T)},則T1是G
的次小生成樹。
證明：如果 T1 不是G 的次小生成樹，那么必定存在另一個生成樹T',T'=T 使得
ω(T)≤ω(T')<ω(T1)，由T1的定義式知T不屬于N(T)，則
E(T')/E(T)={a1,a2
1,……,at}，E(T)/E(T')={b1,b2,……,bt}，其中t≥2。根據引理1 知，存在一
個排列bi1,bi2,……,bit，使得T+aj-bij仍然是G 的生成樹，且均屬于N(T),所以ω(aj)≥ω(bij)，
所以ω(T')≥ω(T+aj-bij)≥ω(T1)，故矛盾。所以T1是圖G 的次小生成樹。
通過上述定理，我們就有了解決次小生成樹問題的基本思路。
首先先求該圖的最小生成樹T。時間復雜度O(Vlog2V+E)
然后，求T的鄰集中權值和最小的生成樹，即圖G 的次小生成樹。
如果只是簡單的枚舉，復雜度很高。首先枚舉兩條邊的復雜度是O(VE)，再判斷該交換是否
可行的復雜度是O(V)，則總的時間復雜度是O(V2E)。這樣的算法顯得很盲目。經過簡單的
分析不難發現，每加入一條不在樹上的邊，總能形成一個環，只有刪去環上的一條邊，才能
保證交換后仍然是生成樹，而刪去邊的權值越大，新得到的生成樹的權值和越小。我們可以
以此將復雜度降為O(VE)。這已經前進了一大步，但仍不夠好。
回顧上一個模型――最小度限制生成樹，我們也曾面臨過類似的問題，并且最終采用動態規
劃的方法避免了重復計算，使得復雜度大大降低。對于本題，我們可以采用類似的思想。首
先做一步預處理，求出樹上每兩個結點之間的路徑上的權值最大的邊，然后，枚舉圖中不在
樹上的邊，有了剛才的預處理，我們就可以用O(1)的時間得到形成的環上的權值最大的邊。
如何預處理呢？因為這是一棵樹，所以并不需要什么高深的算法，只要簡單的BFS 即可。
預處理所要的時間復雜度為O(V2)。
這樣，這一步時間復雜度降為O(V2)。
綜上所述，次小生成樹的時間復雜度為O(V2)。
練習
題目：
題目描述：
最小生成樹大家都已經很了解，次小生成樹就是圖中構成的樹的權值和第二小的樹，此值也可能等于最小生成樹的權值和，你的任務就是設計一個算法計算圖的最小生成樹。
輸入：
存在多組數據，第一行一個正整數t，表示有t組數據。
每組數據第一行有兩個整數n和m（2<=n<=100），之后m行，每行三個正整數s，e，w，表示s到e的雙向路的權值為w。
輸出：
輸出次小生成樹的值，如果不存在輸出-1。
樣例輸入：
2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2
樣例輸出：
4
6
ac代碼（注釋寫的比較清楚）：
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 100000 int father[210]; // 并查集 int visit[210]; // 記錄最小生成樹用到的邊的下標 int windex; // 記錄最小生成樹用到邊的數量 typedef struct node { int st, ed, w; } node; /** * 預處理并查集數組 */ void preProcess() { int i, len = sizeof(father) / sizeof(father[0]); for (i = 0; i < len; i ++) { father[i] = i; } } /** * kruskal使用貪心算法，將邊按權值從小到大排序 */ int cmp(const void *p, const void *q) { const node *a = p; const node *b = q; return a->w - b->w; } /** * 并查集尋找起始結點，路徑壓縮優化 */ int findParent(int x) { int parent; if (x == father[x]) { return x; } parent = findParent(father[x]); father[x] = parent; return parent; } /** * 求最小生成樹 */ int minTree(node *points, int m, int n) { preProcess(); int i, count, flag, pa, pb; for (i = count = flag = windex = 0; i < m; i ++) { pa = findParent(points[i].st); pb = findParent(points[i].ed); if (pa != pb) { visit[windex ++] = i; father[pa] = pb; count ++; } if (count == n - 1) { flag = 1; break; } } return flag; } /** * 求次小生成樹 */ int secMinTree(node *points, int m, int n) { int i, j, min, tmp, pa, pb, count, flag; for (i = 0, min = MAX; i < windex; i ++) { preProcess(); // 求次小生成樹 for (j = count = tmp = flag = 0; j < m; j ++) { if (j != visit[i]) { pa = findParent(points[j].st); pb = findParent(points[j].ed); if (pa != pb) { count ++; tmp += points[j].w; father[pa] = pb; } if (count == n - 1) { flag = 1; break; } } } if (flag && tmp < min) min = tmp; } min = (min == MAX) ? -1 : min; return min; } int main(void) { int i, t, n, m, flag, min; node *points; scanf("%d", &t); while (t --) { scanf("%d %d", &n, &m); points = (node *)malloc(sizeof(node) * m); for (i = 0; i < m; i ++) { scanf("%d %d %d", &points[i].st, &points[i].ed, &points[i].w); } qsort(points, m, sizeof(points[0]), cmp); flag = minTree(points, m, n); if (flag == 0) { // 無法生成最小生成樹 printf("-1/n"); continue; } else { min = secMinTree(points, m, n); printf("%d/n", min); } free(points); } return 0; } 新聞熱點
疑難解答
圖片精選
