トポロジカルソート

graph/topological_sort.hpp · GitHub で見る

共通ページ

有向グラフの全頂点を、各辺の始点が終点より前になるように並べます。閉路がある場合は std::nullopt を返します。

#include "lib/graph/topological_sort.hpp"
#include <iostream>

std::vector<std::vector<int>> graph{ {}, {}, {0}, {1} };
auto order = topological_sort(graph);       // {2, 3, 0, 1}
auto smallest = topological_sort<true>(graph); // {2, 0, 3, 1}
if (order) {
	for (int v : *order) {
		std::cout << v << ' ';
	}
}
graph[0].push_back(2);
auto cyclic = topological_sort(graph);      // std::nullopt

関数	返り値	時間計算量
topological_sort(graph)	トポロジカル順序を格納した optional<vector<int>>	\(O(n+m)\)
topological_sort<true>(graph)	辞書順最小のトポロジカル順序	\(O(m+n\log n)\)

入力は vector<vector<int>> などの隣接リストです。graph.size() で頂点数を取得でき、graph[v] が行き先の int を列挙できれば、array・span なども渡せます。頂点番号は 0 以上 n 未満、頂点数は INT_MAX 以下としてください。辺 u -> v は graph[u].push_back(v) で登録します。

非連結グラフや孤立点も含めて全頂点を返します。空グラフでは、空の vector<int> を格納した有効な optional を返します。多重辺はそのまま扱えます。自己辺は閉路と判定します。一部にだけ閉路がある場合も nullopt で、処理途中の順序は返しません。

通常版は入次数 0 の頂点を FIFO で処理します。最初の候補は頂点番号順に追加し、その後は入力の隣接リスト順に追加します。辞書順最小が必要な場合は <true> を指定してください。この場合は常に候補の最小頂点を選び、隣接リスト内の辺の順序に依存しません。

Kahn のアルゴリズムを使い、通常版では出力配列をキューとして兼用します。入力は変更せず、再帰は使いません。返された結果は入力を参照しないため、同じグラフに何度でも適用できます。

頂点数を \(n\)、辺数を \(m\) とすると、通常版は \(O(n+m)\) 時間、辞書順最小版は \(O(m+n\log n)\) 時間です。どちらも出力を含めて \(O(n)\) の追加空間を使います。

依存ライブラリ

• Predecessor Set（64 分木）
• 64 bit 内の XOR 順位選択

検証コード

• test/topological_sort.test.cpp

コード

#ifndef TOPOLOGICAL_SORT_HPP
#define TOPOLOGICAL_SORT_HPP

#include "../components/predecessor_set.hpp"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <functional>
#include <limits>
#include <optional>
#include <vector>

template<bool Lexicographical = false, class G>
std::optional<std::vector<int>> topological_sort(const G &graph) {
	assert(graph.size() <= std::size_t(std::numeric_limits<int>::max()));
	int n = static_cast<int>(graph.size());
	std::vector<std::size_t> indegree(n);
	for (int v = 0; v < n; ++v) for (int to : graph[v]) {
		assert(0 <= to && to < n);
		++indegree[to];
	}
	std::vector<int> order;
	order.reserve(n);
	if constexpr (Lexicographical) {
		std::vector<int> ready;
		for (int v = 0; v < n; ++v) if (!indegree[v]) ready.push_back(v);
		std::optional<PredecessorSet> ready_set;
		bool use_set = ready.size() > 128;
		if (use_set) {
			ready_set.emplace(n);
			for (int v : ready) ready_set->insert(v);
			ready.clear();
		} else std::make_heap(ready.begin(), ready.end(), std::greater<int>{});
		while (use_set || !ready.empty()) {
			int v;
			if (use_set) {
				v = ready_set->min();
				ready_set->erase(v);
			} else {
				std::pop_heap(ready.begin(), ready.end(), std::greater<int>{});
				v = ready.back();
				ready.pop_back();
			}
			order.push_back(v);
			for (int to : graph[v]) if (--indegree[to] == 0) {
				if (use_set) ready_set->insert(to);
				else {
					ready.push_back(to);
					std::push_heap(ready.begin(), ready.end(), std::greater<int>{});
				}
			}
			if (use_set && ready_set->size() <= 32) {
				while (!ready_set->empty()) {
					int x = ready_set->min();
					ready_set->erase(x);
					ready.push_back(x);
				}
				std::make_heap(ready.begin(), ready.end(), std::greater<int>{});
				use_set = false;
			} else if (!use_set && ready.size() > 128) {
				if (!ready_set) ready_set.emplace(n);
				for (int x : ready) ready_set->insert(x);
				ready.clear();
				use_set = true;
			}
		}
	} else {
		for (int v = 0; v < n; ++v) if (!indegree[v]) order.push_back(v);
		for (std::size_t head = 0; head < order.size(); ++head)
			for (int to : graph[order[head]]) if (--indegree[to] == 0) order.push_back(to);
	}
	if (order.size() != std::size_t(n)) return std::nullopt;
	return order;
}

#endif

Back to top page