Minimum Spanning Tree Algorithms
(graph/mst.hpp)

• View this file on GitHub
• Last update: 2024-01-08 13:32:33+09:00
• Include: #include "graph/mst.hpp"

Description

最小全域木を求めるアルゴリズム詰め合わせ

Kruskal’s Algorithm

Kruskal のアルゴリズムは，無向重み付きグラフの最小全域木を求めるアルゴリズムである．

• pair<T, vector<Edge<T>>> kruskal(vector<Edge<T>> G, int V)
  • 頂点数 $V$ のグラフ $G$ の辺のリストが与えられたとき，最小全域木とその重みを求める
  • 時間計算量: $O(E\log V)$

Prim’s Algorithm

Prim のアルゴリズムは，無向重み付きグラフの最小全域木を求めるアルゴリズムである．

• pair<T, vector<Edge<T>>> prim(vector<vector<Edge<T>>> G)
  • グラフ $G$ の隣接リストが与えられたとき，最小全域木とその重みを求める
  • 時間計算量: $O(E\log V)$

Borůvka’s Algorithm

Borůvka のアルゴリズムは，無向重み付きグラフの最小全域木を求めるアルゴリズムである．

• pair<T, vector<Edge<T>>> boruvka(vector<Edge<T>> G, int V)
  • 頂点数 $V$ のグラフ $G$ の辺のリストが与えられたとき，最小全域木とその重みを求める
  • 時間計算量: $O(E\log V)$

Depends on

• Union Find (data-structure/unionfind/union_find.hpp)

Required by

• Manhattan Minimum Spanning Tree (graph/manhattan_mst.hpp)

Verified with

• test/aoj/GRL_2_A.boruvka.test.cpp
• test/aoj/GRL_2_A.kruskal.test.cpp
• test/aoj/GRL_2_A.prim.test.cpp
• test/yosupo/manhattanmst.test.cpp

Code

#pragma once
#include <algorithm>
#include <queue>
#include <utility>
#include <vector>

#include "../data-structure/unionfind/union_find.hpp"

template <typename T>
using Edge = std::tuple<int, int, T>;

/*
 * Kruskal's Algorithm
 */
template <typename T>
std::pair<T, std::vector<Edge<T>>> kruskal(std::vector<Edge<T>> G, int V) {
    std::ranges::sort(G, {}, [](auto& e) { return std::get<2>(e); });
    UnionFind uf(V);
    T weight = 0;
    std::vector<Edge<T>> edges;
    for (auto& [u, v, w] : G) {
        if (!uf.same(u, v)) {
            uf.unite(u, v);
            weight += w;
            edges.push_back({u, v, w});
        }
    }
    return {weight, edges};
}

/*
 * Prim's Algorithm
 */
template <typename T>
std::pair<T, std::vector<Edge<T>>> prim(
    const std::vector<std::vector<std::pair<int, T>>>& G) {
    std::vector<bool> used(G.size());
    auto cmp = [](const auto& e1, const auto& e2) {
        return std::get<2>(e1) > std::get<2>(e2);
    };
    std::priority_queue<Edge<T>, std::vector<Edge<T>>, decltype(cmp)> pq(cmp);
    pq.emplace(0, 0, 0);
    T weight = 0;
    std::vector<Edge<T>> edges;
    while (!pq.empty()) {
        auto [p, v, w] = pq.top();
        pq.pop();
        if (used[v]) continue;
        used[v] = true;
        weight += w;
        if (v != 0) edges.push_back({p, v, w});
        for (auto& [u, w2] : G[v]) {
            pq.emplace(v, u, w2);
        }
    }
    return {weight, edges};
}

/*
 * Boruvka's Algorithm
 */
template <typename T>
std::pair<T, std::vector<Edge<T>>> boruvka(std::vector<Edge<T>> G, int V) {
    UnionFind uf(V);
    T weight = 0;
    std::vector<Edge<T>> edges;
    while (uf.size(0) < V) {
        std::vector<Edge<T>> cheapest(V,
                                      {-1, -1, std::numeric_limits<T>::max()});
        for (auto [u, v, w] : G) {
            if (!uf.same(u, v)) {
                u = uf.find(u);
                v = uf.find(v);
                if (w < std::get<2>(cheapest[u])) cheapest[u] = {u, v, w};
                if (w < std::get<2>(cheapest[v])) cheapest[v] = {u, v, w};
            }
        }
        for (auto [u, v, w] : cheapest) {
            if (u != -1 && !uf.same(u, v)) {
                uf.unite(u, v);
                weight += w;
                edges.push_back({u, v, w});
            }
        }
    }
    return {weight, edges};
}

#line 2 "graph/mst.hpp"
#include <algorithm>
#include <queue>
#include <utility>
#include <vector>

#line 4 "data-structure/unionfind/union_find.hpp"

class UnionFind {
   public:
    UnionFind() = default;
    explicit UnionFind(int n) : data(n, -1) {}

    int find(int x) {
        if (data[x] < 0) return x;
        return data[x] = find(data[x]);
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (data[x] > data[y]) std::swap(x, y);
        data[x] += data[y];
        data[y] = x;
    }

    bool same(int x, int y) { return find(x) == find(y); }

    int size(int x) { return -data[find(x)]; }

   private:
    std::vector<int> data;
};
#line 8 "graph/mst.hpp"

template <typename T>
using Edge = std::tuple<int, int, T>;

/*
 * Kruskal's Algorithm
 */
template <typename T>
std::pair<T, std::vector<Edge<T>>> kruskal(std::vector<Edge<T>> G, int V) {
    std::ranges::sort(G, {}, [](auto& e) { return std::get<2>(e); });
    UnionFind uf(V);
    T weight = 0;
    std::vector<Edge<T>> edges;
    for (auto& [u, v, w] : G) {
        if (!uf.same(u, v)) {
            uf.unite(u, v);
            weight += w;
            edges.push_back({u, v, w});
        }
    }
    return {weight, edges};
}

/*
 * Prim's Algorithm
 */
template <typename T>
std::pair<T, std::vector<Edge<T>>> prim(
    const std::vector<std::vector<std::pair<int, T>>>& G) {
    std::vector<bool> used(G.size());
    auto cmp = [](const auto& e1, const auto& e2) {
        return std::get<2>(e1) > std::get<2>(e2);
    };
    std::priority_queue<Edge<T>, std::vector<Edge<T>>, decltype(cmp)> pq(cmp);
    pq.emplace(0, 0, 0);
    T weight = 0;
    std::vector<Edge<T>> edges;
    while (!pq.empty()) {
        auto [p, v, w] = pq.top();
        pq.pop();
        if (used[v]) continue;
        used[v] = true;
        weight += w;
        if (v != 0) edges.push_back({p, v, w});
        for (auto& [u, w2] : G[v]) {
            pq.emplace(v, u, w2);
        }
    }
    return {weight, edges};
}

/*
 * Boruvka's Algorithm
 */
template <typename T>
std::pair<T, std::vector<Edge<T>>> boruvka(std::vector<Edge<T>> G, int V) {
    UnionFind uf(V);
    T weight = 0;
    std::vector<Edge<T>> edges;
    while (uf.size(0) < V) {
        std::vector<Edge<T>> cheapest(V,
                                      {-1, -1, std::numeric_limits<T>::max()});
        for (auto [u, v, w] : G) {
            if (!uf.same(u, v)) {
                u = uf.find(u);
                v = uf.find(v);
                if (w < std::get<2>(cheapest[u])) cheapest[u] = {u, v, w};
                if (w < std::get<2>(cheapest[v])) cheapest[v] = {u, v, w};
            }
        }
        for (auto [u, v, w] : cheapest) {
            if (u != -1 && !uf.same(u, v)) {
                uf.unite(u, v);
                weight += w;
                edges.push_back({u, v, w});
            }
        }
    }
    return {weight, edges};
}

Back to top page