最小生成樹

前置知識

• 并查集

• 圖論

概念

條件

最小生成樹的滿足條件為：

• 在無向圖中選取總權值最少的邊讓所有點連通。

• 要求結果是一棵樹，邊數比點數少 \(1\)。

當然，最小生成樹的結果可能不唯一。

特性

• 圖中任意一條非樹邊都會和樹邊構成一個環。
• 非樹邊一定是環中最大的邊。否則可以替換掉最大的邊，得到一個更小生成樹。

其他

最小生成樹有兩種算法：Kruskal 和 Prim。

Kruskal 是在并查集的基礎上展開。

Prim 是在最短路的基礎上展開。

Kruskal

我們可以從選邊的角度來構造生成樹，通過點的連通性來對邊的選取進行判斷。

我們按權值由小到大選擇不成環的邊加入樹中。（由樹的特性可知，成環時該邊一定是環中最大的邊，不應該選取）。如果選出的邊比點數少 \(1\)，說明最小生成樹存在，否則不存在。

那么如何快速的判斷是否成環？我們可以使用并查集來合并點及判斷點的連通性。

步驟

1. 讀入所有邊并初始化并查集（\(f_i = i\)）。

2. 按權值排序。

3. 合并所有邊并計算答案。

4. 輸出。

Prim

可以從選點的角度來構造生成樹，不斷將新的點拉入生成樹中。

步驟

1. 讀入所有邊。

2. 把所有點的距離設為 \(\infty\)，并將任意一點距離設為 \(0\)。

3. 尋找沒有進入生成樹且距離最小的點進入生成樹并累加距離到答案。

4. 更新相鄰點距離。

5. 重復 \(3, 4\) 步直到所有點進入生成樹。

6. 輸出。

例題 1（洛谷 P3366 【模板】最小生成樹）

給出一個無向圖，求出最小生成樹，如果該圖不連通，則輸出 orz。

原題：https://www.luogu.com.cn/problem/P3366

【Kruskal】

代碼是以前寫的，可能不好看。

#include <bits/stdc++.h>
using namespace std;
#define qwq ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 200000 + 20, M = 5000 + 50;

struct node {
  int x, y, z;
  friend bool operator<(const node &a, const node &b) {
    return a.z < b.z;
  }
};

node edge[N];
int n, m, x, y, z, f[M], l[M], ans = 0;
bool b = 1;

int find(int i) {
  if (f[i] == i)
    return i;
  return f[i] = find(f[i]);
}

void merge(int u, int v) {
  u = find(u), v = find(v);
  if (l[u] > l[v]) {
    swap(l[u], l[v]);
  }
  f[u] = v;
  l[v] += l[u];
}

int main() {
  qwq;
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    f[i] = i, l[i] = 1;
  }
  for (int i = 1; i <= m; ++i) {
    cin >> edge[i].x >> edge[i].y >> edge[i].z;
  }
  sort(edge + 1, edge + m + 1);
  for (int i = 1; i <= m; ++i) {
    if (find(edge[i].x) == find(edge[i].y))
      continue;
    merge(edge[i].x, edge[i].y);
    ans += edge[i].z;
    if (l[find(edge[i].x)] == n || l[find(edge[i].y)] == n) {
      b = 0;
      break;
    }
  }
  if (b)
    cout << "orz";
  else
    cout << ans;
  return 0;
}

【Prim】

借鑒一下老師寫的，我寫的 Kruskal。

例題 2（洛谷 P1550 [USACO08OCT] Watering Hole G）

Farmer John 決定將水引入到他的 \(n\) 個農場。他準備通過挖若干井，并在各塊田中修筑水道來連通各塊田地以供水。在第 \(i\) 號田中挖一口井需要花費 \(W_i\) 元。連接 \(i\) 號田與 \(j\) 號田需要 \(P_{i,j}\)（\(P_{j,i}=P_{i,j}\)）元。

每次輸入 \(w_i\) 時，把 \(i\) 和 \(n + 1\) 連接，邊權為 \(w_i\)。

然后在輸入 \(p\) 數組后，套一個雙層循環，如果 \(i \neq j\)，把 \(i\) 和 \(j\) 連接
，邊權為 \(p_{i, j}\)。

存完邊之后按照邊權排序。排序后跑一遍 Kruskal 即可。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;

using ll = long long;

#define mtest for (cin >> t; t; -- t)

const int kMaxN = 1e5 + 10, kMaxM = 1010, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;

int n, w[kMaxN], f[kMaxN], p[kMaxM][kMaxM], ans = 0;

struct node {
  int u, v, w;
} e[kMaxN];

int F(int x) {
  return f[x] == x? x : f[x] = F(f[x]);
}

bool cmp(node a, node b) {
  return a.w < b.w; // 注意是 <
}

void U(int u, int v, int w) {
  int x = F(u), y = F(v);
  if (x != y) {
    f[f[u]] = f[v];
    ans += w;
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 1; i - 1 <= n; ++ i) { // 初始化
    f[i] = i;
  }
  int id = 0;
  for (int i = 1; i <= n; ++ i) { // 村邊
    e[++ id].u = i;
    e[id].v    = n + 1;
    // i & n + 1 連接
    cin >> e[id].w;
  }
  for (int i = 1; i <= n; ++ i) {
    for (int j = 1; j <= n; ++ j) {
      cin >> p[i][j];
    }
  }
  for (int i = 1; i <= n; ++ i) {
    for (int j = 1; j <= n; ++ j) {
      if (i == j) {
        continue;
      }
      e[++ id].u = i;
      e[id].v = j;
      // i & j 連接
      e[id].w = p[i][j];
    }
  }
  sort(e + 1, e + id + 1, cmp); // 按邊權排序
  for (int i = 1; i <= id; ++ i) { // 跑 Kruskal 
    U(e[i].u, e[i].v, e[i].w); 
  }
  cout << ans << '\n';
  return 0;
}

習題

1. 洛谷 P1194 / P1195 / P1396 / P2330 / P2700 / P4047。

2. 自行在 CF / AT 上面找關于最小生成樹的題。

總結

以上是生活随笔為你收集整理的最小生成树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。