Kruskal（最小全域木）

graph/kruskal.hpp · GitHub で見る

共通ページ

重み付き無向グラフの最小全域木を求めます。非連結グラフでは、各連結成分の最小全域木を合わせた最小全域森を返します。

#include "lib/graph/kruskal.hpp"

Kruskal<> graph(4);
graph.add_edge(0, 1, 3); // 辺 ID 0
graph.add_edge(1, 2, 1); // 辺 ID 1
graph.add_edge(0, 2, 2); // 辺 ID 2
graph.add_edge(2, 3, 4); // 辺 ID 3
auto result = graph.solve();
assert(result.connected());
assert(result.cost == 7);
assert((result.edges == std::vector<int>{1, 2, 3}));
for (int id : result.edges) {
	auto [u, v, cost] = graph.get_edge(id);
}

操作・メンバー	内容・返り値	計算量
Kruskal<Cost,Sum>(n = 0)	頂点数を指定。既定値は Cost=int64_t、Sum=Cost	\(O(1)\)
add_edge(u,v,cost)	無向辺を追加し、0 始まりの辺 ID を返す	償却 \(O(1)\)
solve()	最小全域森の Result を返す	\(O(n+m\log m)\)
result.cost	採用した辺の重みの総和（Sum）	\(O(1)\)
result.edges	採用した辺 ID の vector<int>	\(O(1)\)
result.components	元のグラフの連結成分数。孤立点も数える	\(O(1)\)
result.connected()	連結か。空グラフも true とする	\(O(1)\)
get_edge(id)	辺を Edge{from,to,cost} として取得	\(O(1)\)
edges()	入力順の辺一覧を const vector<Edge>& で取得	\(O(1)\)
size() / edge_count()	頂点数／辺数	\(O(1)\)
reserve(m)	辺 m 本分の領域を予約	\(O(m)\)
clear()	全ての辺を削除。頂点数は維持し、辺 ID は 0 から再開	\(O(m)\)

頂点番号は [0,n) です。負の重み・多重辺・自己ループ・孤立点に対応します。自己ループは採用しません。採用する辺数は n-result.components です。空グラフでは総和 0、辺一覧は空、成分数 0 を返します。

辺は重みの昇順で採用し、同じ重みなら辺 ID が小さいものを優先します。solve() は入力を変更せず、辺の追加後にも再実行できます。返された結果はグラフを参照しません。

Cost は各辺の重みの型、Sum は総和の型です。どちらも整数型、またはどちらも浮動小数点型とし、Sum は Cost の全ての値を表現できる型を指定します。例えば Kruskal<uint32_t,uint64_t> は辺を 32 bit、総和を 64 bit で扱います。128 bit の総和には Kruskal<int64_t,__int128_t> を使えます。

整数の加算結果が Sum に収まらない場合は std::overflow_error を送出します。採用順の途中の総和も表現できる型を選んでください。浮動小数点の重みに NaN は使えず、総和には通常の丸め誤差があります。

頂点数・辺数はそれぞれ INT_MAX 以下とします。頂点数を \(n\)、辺数を \(m\) とすると、構築全体は \(O(n+m\log m)\) 時間、入力・結果・作業領域を含めて \(O(n+m)\) 空間です。

依存ライブラリ

• 64 bit キーの安定基数ソート
• Union-Find

検証コード

• test/minimum_spanning_tree.test.cpp

コード

#ifndef KRUSKAL_HPP
#define KRUSKAL_HPP

#include "../data_structure/union_find.hpp"
#include "../components/radix_sort.hpp"
#include <cstdint>
#include <limits>
#include <stdexcept>
#include <type_traits>

template<class Cost = std::int64_t, class Sum = Cost>
class Kruskal {
	static_assert((std::numeric_limits<Cost>::is_integer || std::is_floating_point_v<Cost>) && !std::is_same_v<Cost, bool>);
	static_assert((std::numeric_limits<Sum>::is_integer || std::is_floating_point_v<Sum>) && !std::is_same_v<Sum, bool>);
	static_assert(std::numeric_limits<Cost>::is_integer == std::numeric_limits<Sum>::is_integer);
	static_assert(std::numeric_limits<Cost>::digits <= std::numeric_limits<Sum>::digits);
	static_assert(!std::numeric_limits<Cost>::is_signed || std::numeric_limits<Sum>::is_signed);
	int n_;

  public:
	struct Edge { int from, to; Cost cost; };
	struct Result {
		Sum cost = 0;
		std::vector<int> edges;
		int components = 0;
		bool connected() const { return components <= 1; }
	};

  private:
	std::vector<Edge> edges_;
	static void add_cost(Sum &sum, Cost value) {
		if constexpr (std::numeric_limits<Cost>::is_integer) {
#if defined(__GNUC__) || defined(__clang__)
			Sum next;
			if (__builtin_add_overflow(sum, value, &next)) throw std::overflow_error("Kruskal cost");
			sum = next;
#else
			if ((value > 0 && sum > std::numeric_limits<Sum>::max() - value) ||
				(std::numeric_limits<Cost>::is_signed && value < 0 && sum < std::numeric_limits<Sum>::lowest() - value))
				throw std::overflow_error("Kruskal cost");
			sum += value;
#endif
		} else sum += value;
	}

  public:
	explicit Kruskal(int n = 0) : n_(n) { assert(n >= 0); }
	int size() const { return n_; }
	int edge_count() const { return static_cast<int>(edges_.size()); }
	void reserve(std::size_t m) {
		assert(m <= std::size_t(std::numeric_limits<int>::max()));
		edges_.reserve(m);
	}
	int add_edge(int u, int v, Cost cost) {
		assert(0 <= u && u < n_ && 0 <= v && v < n_);
		assert(edges_.size() < std::size_t(std::numeric_limits<int>::max()));
		if constexpr (std::is_floating_point_v<Cost>) assert(cost == cost);
		int id = edge_count();
		edges_.push_back({u, v, cost});
		return id;
	}
	Edge get_edge(int id) const {
		assert(0 <= id && id < edge_count());
		return edges_[id];
	}
	const std::vector<Edge> &edges() const { return edges_; }
	void clear() { edges_.clear(); }
	Result solve() const {
		std::vector<int> order;
		order.reserve(edges_.size());
		for (int id = 0; id < edge_count(); ++id) if (edges_[id].from != edges_[id].to) order.push_back(id);
		auto compare = [&](int a, int b) {
			if (edges_[a].cost < edges_[b].cost) return true;
			if (edges_[b].cost < edges_[a].cost) return false;
			return a < b;
		};
		if constexpr (std::is_integral_v<Cost> && sizeof(Cost) <= sizeof(std::uint64_t)) {
			if (order.size() < 256) std::sort(order.begin(), order.end(), compare);
			else if (std::is_sorted(order.begin(), order.end(), [&](int a, int b) { return edges_[b].cost < edges_[a].cost; })) {
				std::reverse(order.begin(), order.end());
				for (std::size_t first = 0; first < order.size();) {
					std::size_t last = first + 1;
					while (last < order.size() && edges_[order[first]].cost == edges_[order[last]].cost) ++last;
					std::reverse(order.begin() + first, order.begin() + last);
					first = last;
				}
			} else {
				using Key = std::make_unsigned_t<Cost>;
				auto sort_key = [&](int id) {
					Key key = static_cast<Key>(edges_[id].cost);
					if constexpr (std::is_signed_v<Cost>) key ^= Key(1) << (std::numeric_limits<Key>::digits - 1);
					return key;
				};
				if (sizeof(Cost) >= 4 && order.size() >= 65536) stable_radix_sort<11>(order, sort_key);
				else stable_radix_sort(order, sort_key);
			}
		} else std::sort(order.begin(), order.end(), compare);
		UnionFind uf(n_);
		Result result;
		result.edges.reserve(std::min(order.size(), std::size_t(n_ ? n_ - 1 : 0)));
		for (int id : order) {
			const auto &e = edges_[id];
			if constexpr (std::is_same_v<Cost, std::int64_t> && std::is_same_v<Sum, Cost>) {
				int components = uf.count();
				uf.merge(e.from, e.to);
				if (uf.count() == components) continue;
				add_cost(result.cost, e.cost);
			} else {
				int u = uf.leader(e.from), v = uf.leader(e.to);
				if (u == v) continue;
				add_cost(result.cost, e.cost);
				uf.merge(u, v);
			}
			result.edges.push_back(id);
			if (uf.count() == 1) break;
		}
		result.components = uf.count();
		return result;
	}
};

#endif

Back to top page