クラスカル法
(graph/minimumspanningtree/kruskal.hpp)

• View this file on GitHub
• Last update: 2020-08-25 17:20:34+09:00
• Include: #include "graph/minimumspanningtree/kruskal.hpp"

概要

最小全域木を求めるアルゴリズム. 内部でUnionFindを使用している.

計算量

$O(E\log V)$

使用例

• kruskal(g) : グラフgに対してクラスカル法を行う.
  • 返り値 : 最小全域木の重さ.

Verified with

• test/aoj/GRL_2_A.test.cpp

Code

/**
* @brief クラスカル法
* @docs docs/graph/minimumspanningtree/kruskal.md
*/

template <typename T>
T kruskal(const Graph<T> &g) {
    vector<Edge<T>> edges;
    for (int i = 0; i < g.V; ++i)
        for (auto &e : g.mat[i]) edges.emplace_back(e);
    sort(edges.begin(), edges.end(), [](const Edge<T> &a, const Edge<T> &b) {
        return a.cst < b.cst;
    });
    UnionFind uf(g.V);
    T ret(0);
    for (auto &e : edges)
        if (uf.unite(e.frm, e.to)) ret += e.cst;
    return ret;
}

#line 1 "graph/minimumspanningtree/kruskal.hpp"
/**
* @brief クラスカル法
* @docs docs/graph/minimumspanningtree/kruskal.md
*/

template <typename T>
T kruskal(const Graph<T> &g) {
    vector<Edge<T>> edges;
    for (int i = 0; i < g.V; ++i)
        for (auto &e : g.mat[i]) edges.emplace_back(e);
    sort(edges.begin(), edges.end(), [](const Edge<T> &a, const Edge<T> &b) {
        return a.cst < b.cst;
    });
    UnionFind uf(g.V);
    T ret(0);
    for (auto &e : edges)
        if (uf.unite(e.frm, e.to)) ret += e.cst;
    return ret;
}

Back to top page