ch10 最小生成樹
生成樹:對于 n 個結點 m 條邊的無向圖 G,由全部 n 個結點和其中 n - 1 條邊構成的無向連通子圖稱為 G 的一棵生成樹。
- 如果圖 G 原本就不連通,則不存在生成樹,只存在生成森林。
最小生成樹(Minimum Spanning Tree,MST):對于帶邊權的無向圖 G,邊的權值之和最小的生成樹稱為 G 的最小生成樹。
求解 MST 常用 Kruskal 算法或 Prim 算法,這兩種算法都基于貪心法。
- Kruskal 算法時間復雜度 O ( m log ? m ) O(m\log m) O(mlogm) ,適用于稀疏圖。
- Prim 算法時間復雜度 O ( n 2 ) O(n^2) O(n2) ,適用于完全圖或稠密圖。
模板
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。
只需刪去原最小生成樹中的最長邊,用瓶頸生成樹中的一條邊來連接刪去邊后形成的兩棵樹,得到的新生成樹一定比原最小生成樹的權值和還要小,這樣就產生了矛盾。