详解次小生成树以及相关的C++求解方法

什么是次小生成树

在普通的生成树中，每个节点只有一条边与其相连。而次小生成树则是指，在所有的生成树中，除了最小生成树之外，权值和第二小的生成树。

求解方法

Kruskal算法

Kruskal算法是一种贪心算法，也是求解最小生成树的常用算法。我们可以对Kruskal算法做一些修改，使其求出次小生成树。

一般情况下，我们需要两个并查集$fa1$和$fa2$，分别表示这个点在第一最小生成树中的父亲和第二最小生成树中的父亲。如果一个点和它的父亲在两颗生成树中不相交，那么这个联通块中一定会有一个是用第一大生成树拼接的，另一个是第二小生成树。在做Kruskal的过程中，如果我们将边加入当前的生成树后，发现边的两个端点$u$和$v$在$fa1$和$fa2$中的根节点不同，那么说明我们已经找到了新的一条边，可以将当前的生成树的权值和记录为此时的最小边权和第二小边权（前者是用于求解最小生成树，后者是用于求解次小生成树）。

以下是对应的C++代码实现：

const int maxn = ...;
int fa1[maxn], fa2[maxn];

struct edge {
    int u, v, w;
    bool operator < (const edge e) const {
        return w < e.w;
    }
} edges[maxn];

int find_fa(int *fa, int u) {
    if (u == fa[u]) return u;
    return fa[u] = find_fa(fa, fa[u]);
}

int kruskal() {
    int ans1 = 0, ans2 = 0;
    int cnt = 0;
    sort(edges, edges + n);
    for (int i = 1; i <= n; ++i) {
        fa1[i] = i; fa2[i] = i;
    }
    for (int i = 0; i < m; ++i) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        int fu1 = find_fa(fa1, u), fv1 = find_fa(fa1, v);
        int fu2 = find_fa(fa2, u), fv2 = find_fa(fa2, v);
        if (fu1 != fv1 && fu2 != fv2) {
            fa1[fu1] = fv1, fa2[fu2] = fv2;
            ans1 += w;
            if (++cnt == n - 1) break;
        }
    }
    return ans1;
}

Prim算法

Prim算法同样可以用于求解次小生成树。在Prim算法中，我们需要用两个数组$lowcost1$和$lowcost2$存储每个节点和当前最小生成树以及次小生成树中的最短边，分别对应着最小的权值和次小的权值。而在Prim算法的每一轮中，我们需要维护两个堆$heap1$和$heap2$，分别对应着已经加入最小生成树和次小生成树的节点。在加入一个点$u$的时候，我们需要判断这个点加入最小生成树时的边是否成环，并且将另一条边更新到次小生成树中。具体的实现细节可参见以下的C++代码：

const int maxn = ...;
const int inf = ...;
int lowcost1[maxn], lowcost2[maxn], vis[maxn];
int heap1[maxn], heap2[maxn];

struct edge {
    int to, w;
};

vector<edge> G[maxn];

void prim(int start) {
    memset(lowcost1, inf, sizeof(lowcost1));
    memset(lowcost2, inf, sizeof(lowcost2));
    memset(vis, 0, sizeof(vis));
    memset(heap1, 0, sizeof(heap1));
    memset(heap2, 0, sizeof(heap2));
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q1, q2;

    lowcost1[start] = 0;
    q1.push(make_pair(0, start));
    while (!q1.empty()) {
        pair<int, int> p = q1.top();
        q1.pop();
        int u = p.second;
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = 0; i < G[u].size(); ++i) {
            int v = G[u][i].to, w = G[u][i].w;
            if (!vis[v] && lowcost1[v] > w) {
                lowcost2[v] = lowcost1[v];
                lowcost1[v] = w;
                heap2[v] = heap1[v];
                heap1[v] = u;
                q2.push(make_pair(lowcost2[v], v));
                q1.push(make_pair(lowcost1[v], v));
            } else if (vis[v] && heap1[v] != u && lowcost2[v] > w) {
                lowcost2[v] = w;
                heap2[v] = u;
                q2.push(make_pair(lowcost2[v], v));
            }
        }
    }
}

示例说明

案例一

下列是一个有$n=5$个节点，$m=7$条边的无向图，每条边都有对应的正整数权值：

1 ----- 2 ----- 5 
|       | 4     / |  
| 3     |/     /2 |  
|/      3     /   |
3 ----- 4 ----- 5

我们可以用Kruskal算法和Prim算法求解这个无向图的次小生成树。首先，我们需要存储每条边的信息，例如：

struct edge {
    int u, v, w;
}

则上图对应的边可以描述如下：

edge es[] = {
    { 1, 2, 3 },
    { 1, 3, 4 },
    { 2, 4, 4 },
    { 2, 5, 2 },
    { 3, 4, 3 },
    { 4, 5, 5 },
    { 3, 5, 2 }
};

Kruskal算法的代码详见上述部分，这里不再赘述。使用Kruskal算法求解这个无向图的次小生成树的结果如下：

1 ---3--- 2 ---4--- 5
         | 2
         |
         4
         |
         3

次小生成树的权值和为$14$。

Prim算法的代码详见上述部分，这里不再赘述。使用Prim算法求解这个无向图的次小生成树的结果如下：

1 --3-- 2 --2-- 5
        | 4
        4
        | 3
        3

次小生成树的权值和为$14$。

案例二

接着我们考虑下列这个比较复杂的案例，在这个案例中，我们有$n=6$个节点，$m=10$条边：

1 ----- 2 ----- 5 --15-- 6
|       | 5     / |  7  /  | 
| 3     |/     /2 |  /9  |  
|/      3     /   | /   \ |
3 ----- 4 ----- 5 --24-- 7

同样，我们可以使用Kruskal算法和Prim算法求解这个无向图的次小生成树。求解的过程和上述案例一样，这里不再赘述。得到的结果如下：

Kruskal算法：

1 ---3--- 3 ---4--- 5 ---7--- 6
         | 5    | 2    | 7
         |      |      |  
         2      3     /  |
         |      |   24   |
         | 4    |/      |
         6 ---15--- 4   /
             \        |9
              \       |
               1 ---  5

次小生成树的权值和为$65$。

Prim算法：

1 --3-- 3 --5-- 5 --7-- 6
        | 2   | 7  /  |
        |     |   /   |
        4     3 /   \ |
        |     |24     9
        | 5   |/     /
        2 --15-- 4  --
              \   | 
               \  |
                1 5

次小生成树的权值和为$65$。