ch10 最小生成樹

生成樹：對于 n 個結點 m 條邊的無向圖 G，由全部 n 個結點和其中 n - 1 條邊構成的無向連通子圖稱為 G 的一棵生成樹。

• 如果圖 G 原本就不連通，則不存在生成樹，只存在生成森林。

最小生成樹（Minimum Spanning Tree，MST）：對于帶邊權的無向圖 G，邊的權值之和最小的生成樹稱為 G 的最小生成樹。

求解 MST 常用 Kruskal 算法或 Prim 算法，這兩種算法都基于貪心法。

• Kruskal 算法時間復雜度 $O(m\log m)$ ，適用于稀疏圖。
• Prim 算法時間復雜度 $O(n^2)$ ，適用于完全圖或稠密圖。

模板

prim

算法流程：選取任意一個結點作為樹 T，然后貪心地選取離 T 最近的那個點，并把它和對應的邊加到 T 中。不斷進行這個操作，就可以得到一棵最小生成樹 T。

const int inf = 0x3f3f3f3f;
const int maxn = 5010;
int cost[maxn][maxn];
// 是否在 T 中
bool used[maxn];
// 點 i 與 T 相連的最短邊的權值
int d[maxn];
int n;/*
標記一個點 d[u] = 0
循環地執行：不在 T 中的節點與 T 相連的最短的邊，擁有該邊的節點 u最小生成樹權值加上這條邊把 u 加入 T：維護 used, d
直到 n 個點全部加入 T 中
*/
long long prim() {memset(d, 0x3f, sizeof(d));d[1] = 0;  // 希望第一步加入點 1long long res = 0;for (int i = 1; i <= n; ++i) {int u = -1;for (int v = 1; v <= n; ++v) {// 選不在樹 T 且與 T 相連的最短邊if (!used[v] && (u == -1 || d[v] < d[u])) u = v;}if (d[u] == inf) return -1;// 把點 u 加入樹 Tres += d[u];used[u] = 1;for (int v = 1; v <= n; ++v) {if (!used[v]) d[v] = min(d[v], cost[u][v]);}}return res;
}

kruskal

算法流程：每次都從剩余的邊中選出一條邊權最小的，并且這條邊的兩個端點 u 和 v 屬于兩個不同的連通分量（即 u 和 v 不連通），則加入該邊，連接兩個連通分量。

const int maxn = 100010, maxm = 100010;
struct Edge {int u, v, w;bool operator<(const Edge &n) const { return w < n.w; }
}E[maxm];
int fa[maxn], n, m;
void init() {for (int i = 1; i <= n; i++) fa[i] = i;
}
int find(int x) {if (fa[x] == x) return x;return fa[x] = find(fa[x]);
}
void merge(int x, int y) {int rx = find(x), ry = find(y);fa[ry] = rx;
}
long long kru() {sort(E, E + m); // 邊權從小到大排序long long res = 0;int cnt = n; // 記錄當前連通分量的個數for (int i = 0; i < m; ++i) {Edge e = E[i];if (find(e.u) != find(e.v)) {merge(e.u, e.v);--cnt, res += e.w;}}if (cnt > 1) return -1; // 不連通return res;
}
int main() {cin >> n >> m;for (int i = 0; i < m; ++i) {cin >> E[i].u >> E[i].v >> E[i].w;}init();cout << kru() << endl;return 0;
}

注意并查集只是維護結點的連通情況，不代表最終的 MST。如果需要將 MST 儲存起來方便后面遍歷這棵 MST，可以用 vector 數組（鄰接表）將加入的邊 e[i] 儲存。

// 有邊權的情況，需要儲存出邊的終點v和邊權w
struct Edge2{int v, w;
};
vector<Edge2> G[N]; // G[u]儲存結點u的所有出邊信息（終點v和邊權w）// 選中e[i]這條邊加入時，執行
G[e[i].u].push_back({e[i].v, e[i].w});
G[e[i].v].push_back({e[i].u, e[i].w});

瓶頸生成樹

• 指最大的邊權值最小的生成樹。

• 與最小生成樹的區別

  • 最小生成樹目標是希望所有邊權加起來最小。
  • 瓶頸生成樹目標是希望邊權最大的那條邊權值盡量小。如果把邊權理解為邊的長度，就是希望最長的那條邊盡量短。

• 性質： 最小生成樹一定是瓶頸生成樹，而瓶頸生成樹不一定是最小生成樹。

  反證法證明：

  設最小生成樹中的最大邊權為 w，如果最小生成樹不是瓶頸生成樹的話，則瓶頸生成樹的所有邊權都小于 w。

  只需刪去原最小生成樹中的最長邊，用瓶頸生成樹中的一條邊來連接刪去邊后形成的兩棵樹，得到的新生成樹一定比原最小生成樹的權值和還要小，這樣就產生了矛盾。