带权连通图最小生成树：破圈法求解与实现

本文将深入探讨带权连通图最小生成树的求解方法，重点介绍一种名为“破圈法”的高效算法，并提供 C++ 代码实现，详细解释其原理和时间复杂度分析。

算法概述

“破圈法”是带权连通图求最小生成树的另一种方法，其思路是任意取一个圈，去掉圈上权值最大的一个边，反复执行这个步骤，直到图中没有圈为止。

C++ 代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct Edge {
    int u, v, w;
    Edge(int uu, int vv, int ww) : u(uu), v(vv), w(ww) {}
};

bool operator<(const Edge& e1, const Edge& e2) {
    return e1.w > e2.w; // 小根堆
}

int find(int x, vector<int>& parent) {
    if (parent[x] != x) {
        parent[x] = find(parent[x], parent);
    }
    return parent[x];
}

void merge(int x, int y, vector<int>& parent) {
    int px = find(x, parent);
    int py = find(y, parent);
    if (px != py) {
        parent[px] = py;
    }
}

vector<Edge> kruskal(vector<Edge>& edges, int n) {
    vector<Edge> mst;
    vector<int> parent(n);
    for (int i = 0; i < n; i++) {
        parent[i] = i; // 初始化每个点的祖先为自己
    }
    priority_queue<Edge> q;
    for (Edge& e : edges) {
        q.push(e);
    }
    while (!q.empty()) {
        Edge e = q.top();
        q.pop();
        if (find(e.u, parent) != find(e.v, parent)) {
            mst.push_back(e);
            merge(e.u, e.v, parent);
        }
    }
    return mst;
}

vector<Edge> breakCycles(vector<Edge>& edges, int n) {
    vector<Edge> mst;
    vector<int> parent(n);
    for (int i = 0; i < n; i++) {
        parent[i] = i; // 初始化每个点的祖先为自己
    }
    for (Edge& e : edges) {
        if (find(e.u, parent) != find(e.v, parent)) {
            mst.push_back(e);
            merge(e.u, e.v, parent);
        } else { // 如果边加进去会形成圈
            vector<Edge> candidates; // 存储所有可能被破掉的边
            int pu = find(e.u, parent);
            int pv = find(e.v, parent);
            for (Edge& f : mst) {
                if (find(f.u, parent) == pu && find(f.v, parent) == pv) {
                    candidates.push_back(f);
                }
            }
            Edge maxEdge = *max_element(candidates.begin(), candidates.end(), [](const Edge& e1, const Edge& e2) {
                return e1.w < e2.w;
            }); // 找到权值最大的那条边
            if (e.w < maxEdge.w) {
                mst.erase(find(mst.begin(), mst.end(), maxEdge)); // 破掉这条边
                mst.push_back(e); // 加上新的边
            }
        }
    }
    return mst;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<Edge> edges;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.emplace_back(u, v, w);
    }
    vector<Edge> mst = breakCycles(edges, n);
    for (Edge& e : mst) {
        cout << e.u << ' ' << e.v << ' ' << e.w << endl;
    }
    return 0;
}

该程序首先读入带权连通图的边，然后调用 breakCycles 函数来求最小生成树。该函数基于 Kruskal 算法，但增加了破圈的步骤。具体来说，如果加入一条边会形成圈，那么就找出该圈上所有边，然后选择权值最大的那条边破掉，再把新的边加入最小生成树中。一直重复这个过程，直到没有圈为止。最后程序输出最小生成树的所有边。

时间复杂度分析

需要注意的是，由于需要反复查找圈上所有边，所以该算法的时间复杂度可能较高。但由于每次只会破掉一条边，因此最多进行 n-1 次操作，所以时间复杂度应该是 O(m log m + m α(n))，其中 α(n) 是反阿克曼函数，可以认为是一个很小的常数。

总结

破圈法是一种求解带权连通图最小生成树的有效方法，它可以很好地处理图中存在的圈，并保证最终得到一个最小生成树。虽然其时间复杂度可能略高于 Kruskal 算法，但在许多情况下，它仍然是一个高效的算法。