『普及』浅谈最小生成树

如履薄冰 · 2025-06-01 22:22:35 · 算法·理论

最小生成树的概念

在一个 n 个节点 m 条边的连通图 G 中，选取其所有的点，n - 1 条边所构成的连通子图被称为 G 的生成树。其中在加权图中边权和最小的生成树被称为最小生成树。本章将讲述两个最经典的最小生成树算法：克鲁斯卡尔算法与普里姆算法。下图是本章的思维导图：

克鲁斯卡尔算法

讲解

克鲁斯卡尔算法的思想基于贪心。一个图中可能有多个最小生成树，但边权和一定唯一。克鲁斯卡尔算法的思想是这样的：将边权和从小到大加边，直到图中所有节点连通。不能再已经连通的两个点之间加边，所以需要不断判断两个点是否连通，并在选边的时候连接边的两个端点，通常使用并查集。该算法的主体代码如下：

int n, m, cnt, fa[110000];
struct Node{
    int u, v, w;
    bool operator < (const Node &e) const
    {
        return w < e.w;
    }
}G[110000];
void init()
{
    for (int i = 1; i <= n; ++ i)
    {
        fa[i] = i;
    }
}
int find(int x)
{
    if (x == fa[x])
    {
        return x;
    }
    return fa[x] = find(fa[x]);
}
void merge(int x, int y)
{
    x = find(x), y = find(y);
    if (x == y)
    {
        return;
    }
    fa[x] = y;
}
void kruskal()
{
    cnt = n;
    int sum = 0;
    sort(G + 1, G + 1 + m);
    init();
    for (int i = 1; i <= m; ++ i)
    {
        int u = G[i].u, v = G[i].v;
        if (find(u) == find(v))
        {
            continue;
        }
        merge(u, v);
        sum += G[i].w;
        -- cnt;
    }
    return;
}

此算法的时间复杂度为 O(M \log M)，适用于稀疏图中。

克鲁斯卡尔算法的证明

我们可以使用归纳法，证明任何时候克鲁斯卡尔算法选择的边集都被某棵最小生成树所包含。证明如下：算法刚开始时，这条性质显然成立，因为边权最小的边必然在某棵最小生成树里。接下来，我们假设在某一时刻这条性质成立，将已选边的集合设为 E，包含 E 的某个最小生成树设为 T，那么现在我们要证明的是新加入的一条边 e 也必然在某棵最小生成树中。如果 e 在 T 中，这条性质成立。如果 e 不在 T 中，那么如果 T 加入 e，必定存在一个环，我们将这个环上不属于 E 的另一条边设为 f，那么 f 的权值一定与 e 的权值相同，为什么呢？我们分情况讨论。如果 f 的权值比 e 小，因为如果 f 的权值比 e 小，那么按照克鲁斯卡尔算法的选法，f 应该在 e 之前加入 E，那么 f 就应该属于 E，矛盾了。如果 f 的权值比 e 大，不然如果我们从 T 中去掉 f，加入 e，形成另一个生成树 R，那么 R 的权值和就比 T 的权值和更小了，但 T 是最小生成树，不存在比它的权值和还要小的生成树。所以 f 的权值不能比 e 大，也不能比 e 小，所以 f 的权值只能等于 e。根据这条结论，我们可以得出 T 去掉 f，加入 e，仍然是一颗最小生成树。综上所述，当某一时刻命题成立时，接下来新加入的一条边也会在某棵最小生成树中，证毕。

习题推荐

基础

• P1396 营救
• P2504 [HAOI2006] 聪明的猴子
• P1195 口袋的天空
• P3366 【模板】最小生成树

  拓展

• P9709 [KMOI R1] 军事行动

  习题讲解

  我们以这道题为例。

  可行的算法

  暴力枚举

  我们可以枚举这个图中所有生成树，然后再找出其中边权和最小的某一个生成树。这个算法虽简单，但用时太长，是不能用的。

  克鲁斯卡尔算法

  在此题中，1 \le M \le 2 \times 10^5，而克鲁斯卡尔算法的时间复杂度为 O(M \log M)，时间复杂度是合格的，于是，我们可以采用这个算法。首先，我们需要对边排序，所以我们可以用一个结构体存每个边，然后再重载小于号，最后对所有边进行排序。然后我们就可以开始计算了。我们从小到大枚举每条边，如果这条边中的两个端点 u 和 v 已经连通，我们就不需要在最小生成树中加入这条边了，因为加了也没用。否则，我们就加入这条边，并让最小生成树的目前总边权加上这条边的边权。在这个过程中，我们需要判断很多次两个点是否连通，不难想到用并查集实现。如果要加入这条边，我们就把这条边的两个端点所在的集合合并，如果需要判断是否连通，只需要看看他们各自的“老大”是否相同即可。当我们把每个边都枚举了一遍后，我们就已经求好了最小生成树，只需输出我们算出的边权和即可。这里我们还需要面对另一种情况：最小生成树不存在。那么如何判断存不存在呢？我们只需要拿一个 cnt 变量来维护当前并查集的集合数，如果最后 cnt = 1，就证明有最小生成树，反之就没有。此题的代码如下：

  #include<bits/stdc++.h>
  #define int long long
  using namespace std;
  int n, m, cnt, fa[110000];
  struct Node{
  int u, v, w;
  bool operator < (const Node &e) const
  {
      return w < e.w;
  }
  }G[110000];
  void init()
  {
  for (int i = 1; i <= n; ++ i)
  {
      fa[i] = i;
  }
  }
  int find(int x)
  {
  if (x == fa[x])
  {
      return x;
  }
  return fa[x] = find(fa[x]);
  }
  void merge(int x, int y)
  {
  x = find(x), y = find(y);
  if (x == y)
  {
      return;
  }
  fa[x] = y;
  }
  int kruskal()
  {
  cnt = n;
  int sum = 0;
  sort(G + 1, G + 1 + m);
  init();
  for (int i = 1; i <= m; ++ i)
  {
      int u = G[i].u, v = G[i].v;
      if (find(u) == find(v))
      {
          continue;
      }
      merge(u, v);
      sum += G[i].w;
      -- cnt;
  }
  return (cnt == 1? sum : -1);
  }
  signed main()
  {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= m; ++ i)
  {
      cin >> G[i].u >> G[i].v >> G[i].w;
  }
  int ans = kruskal();
  if (ans == -1)
  {
      cout << "orz";
      return;
  }
  cout << ans;
  return 0;
  }

  普里姆算法

  讲解

  普里姆算法也是一种贪心求最小生成树的方法，且类似于最短路算法中的迪杰斯特拉算法。它的算法思想是：从一个节点开始，不断加入离最小生成树最近的点。这个算法比较重要的两点是：

1. 不能加入重复的节点，通常使用数组标记每个节点是否已经加入。
2. 我们把节点分为未加入的点集 S 和已加入的点集 T。在 S 中找到距离 T 最近的节点 u 加入 T 中，用 u 的连边更新其他节点距离 T 的最短距离，这个操作有点像迪杰斯特拉算法中的松弛操作。 该算法的主体代码如下：

   int n, m, dis[1100000];
   bool vis[1100000];
   struct Node{
   int v, w;
   };
   vector<Node> G[5001];
   int Prim()
   {
   memset(dis, 0x3f, sizeof dis);
   int No = dis[2];
   dis[1] = 0;
   for (int i = 1; i <= n; ++ i)
   {
       int u = -1;
       for (int v = 1; v <= n; ++ v)
       {
           if (!vis[v] && (u == -1 || dis[v] < dis[u]))
           {
               u = v;
           }
       }
       if (u == -1 || dis[u] == No)
       {
           return 0;
       }
       vis[u] = true;
       for (auto v : G[u])
       {
           if (!vis[v.v])
           {
               dis[v.v] = min(dis[v.v], v.w);
           }
       }
   }
   return;
   }

   该算法的时间复杂度为 O(N^2)，适合用在稠密图中。该算法的证明与克鲁斯卡尔的证明大同小异，就不解释了。

   习题推荐

   基础

   • P1194 买礼物
   • P1265 公路修建
   • P4047 [JSOI2010] 部落划分

     拓展

   • P2573 [SCOI2012] 滑雪
   • P5425 [USACO19OPEN] I Would Walk 500 Miles G

     习题讲解

     以这道题为例。我们可以把每个礼物都抽象成一个点，两个礼物之间的关系抽象成图中的边，然后再求最小生成树的总边权即可。由于这道题中每个礼物都有价格，所以对于所有的 1 \le i,j \le n，只要 i 不等于 j，K_{i,j} 必然不等于 0。那么这个图就是个稠密图，非常适合用普利姆算法。我们先加入节点 1，然后再把最小生成树的边权总和加上最小生成树离 1 号节点的最短距离，最后再更新所有节点离最小生成树的最短距离。然后再找出现在离最小生成树最近的节点，重复上面的操作。我们要这样操作 B 次，最后再输出最小生成树的边权总和加 A 即可，加 A 的原因是因为 1 号礼物本身也要钱。本题的代码如下：

     #include<bits/stdc++.h>
     #define int long long
     using namespace std;
     int a, n, w[501][501], dis[501];
     bool vis[501];
     int Prim()
     {
     dis[1] = 0;
     int tot = 0;
     for (int i = 1; i <= n; ++ i)
     {
     int u = -1;
     for (int v = 1; v <= n; ++ v)
     {
         if (!vis[v] && (u == -1 || dis[v] < dis[u]))
         {
             u = v;
         }
     }
     tot += dis[u];
     vis[u] = true;
     for (int v = 1; v <= n; ++ v)
     {
         if (!vis[v])
         {
             dis[v] = min(dis[v], w[u][v]);
         }
     }
     }
     return tot;
     }
     signed main()
     {
     ios::sync_with_stdio(false);
     cin >> a >> n;
     for (int i = 1; i <= n; ++ i)
     {
     for (int j = 1; j <= n; ++ j)
     {
         if (i == j)
         {
             continue;
         }
         w[i][j] = a;
     }
     }
     for (int i = 1; i <= n; ++ i)
     {
     for (int j = 1; j <= n; ++ j)
     {
         int x;
         cin >> x;
         if (i == j || x == 0)
         {
             continue;
         }
         w[i][j] = min(w[i][j], x);
     }
     }
     memset(dis, 0x3f, sizeof dis);
     cout << Prim() + a;
     return 0;
     }