C++初学者实现Kruskal算法：类内自定义谓词集合及边存储疑问

阿华AIGC实验室

2026-5-26

关于Kruskal算法中自定义谓词集合的实现建议

作为C++初学者，你选择用map<pair<int, int>, int>存储边权重的思路很合理，但要注意：map默认是按键（也就是pair<int,int>的字典序）排序的，而Kruskal算法需要按边的权重从小到大遍历，这时候自定义谓词的集合就能帮上大忙。我给你梳理下具体的实现思路和代码参考：

1. 先定义清晰的边结构体

为了更方便管理边的起点、终点和权重，建议先封装一个Edge结构体，后续排序和处理会更直观：

struct Edge {
    int u;
    int v;
    int weight;

    // 构造函数，快速创建边对象
    Edge(int u_, int v_, int w_) : u(u_), v(v_), weight(w_) {}
};

2. 自定义谓词实现边的排序逻辑

Kruskal需要按权重升序处理边，我们可以通过两种方式实现自定义排序规则：

方式一：用函数对象作为集合的谓词

如果想用std::set自动维护有序的边集合，可以写一个函数对象作为排序谓词：

struct EdgeCompare {
    // 重载()运算符，实现按权重升序排序；权重相同时按顶点对字典序排序，保证set元素唯一
    bool operator()(const Edge& e1, const Edge& e2) const {
        if (e1.weight != e2.weight) {
            return e1.weight < e2.weight;
        }
        return make_pair(e1.u, e1.v) < make_pair(e2.u, e2.v);
    }
};

然后把这个带谓词的集合整合到你的WeightedGraph类中：

class WeightedGraph {
private:
    int V;
    set<Edge, EdgeCompare> edges; // 带自定义谓词的set，自动按权重排序

public:
    // 构造函数
    WeightedGraph(int vertexCount) : V(vertexCount) {}

    // 添加无向边，统一u<=v避免重复存储
    void addEdge(int u, int v, int weight) {
        if (u > v) swap(u, v);
        edges.insert(Edge(u, v, weight));
    }

    // 后续实现Kruskal算法的方法...
};

方式二：用lambda表达式配合排序算法

如果你想保留原来的map存储方式，可以在Kruskal算法中提取所有边，用std::sort结合lambda实现排序：

// 在Kruskal算法的实现里
vector<Edge> edgeList;
for (const auto& entry : w_map) {
    int u = entry.first.first;
    int v = entry.first.second;
    int weight = entry.second;
    edgeList.emplace_back(u, v, weight);
}

// 用lambda作为谓词，按权重升序排序
sort(edgeList.begin(), edgeList.end(), [](const Edge& e1, const Edge& e2) {
    return e1.weight < e2.weight;
});

3. 补充Kruskal必备的并查集结构

Kruskal算法需要并查集检测环，你可以把它作为类的私有成员或单独实现：

class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;

public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    // 路径压缩的find操作
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // 按秩合并的unite操作，返回是否成功合并（无环）
    bool unite(int x, int y) {
        int xRoot = find(x);
        int yRoot = find(y);
        if (xRoot == yRoot) return false;

        if (rank[xRoot] < rank[yRoot]) {
            parent[xRoot] = yRoot;
        } else {
            parent[yRoot] = xRoot;
            if (rank[xRoot] == rank[yRoot]) rank[xRoot]++;
        }
        return true;
    }
};

然后在WeightedGraph中实现完整的Kruskal算法：

void kruskalMST() {
    UnionFind uf(V);
    int mstTotalWeight = 0;
    vector<Edge> mstEdges;

    for (const auto& edge : edges) {
        if (uf.unite(edge.u, edge.v)) {
            mstEdges.push_back(edge);
            mstTotalWeight += edge.weight;
            if (mstEdges.size() == V - 1) break; // 生成树已包含V-1条边，提前结束
        }
    }

    // 输出结果
    cout << "Minimum Spanning Tree Total Weight: " << mstTotalWeight << endl;
    cout << "Edges in MST:" << endl;
    for (const auto& e : mstEdges) {
        cout << e.u << " - " << e.v << " (weight: " << e.weight << ")" << endl;
    }
}