有向・無向 Euler 路

graph/eulerian_trail.hpp · GitHub で見る

共通ページ

全ての辺をちょうど 1 回ずつ通る Euler 路を求めます。始点と終点が同じ Euler 閉路も含みます。自己辺・多重辺に対応し、元の辺 ID と頂点列を返します。

#include "lib/graph/eulerian_trail.hpp"
#include <cassert>

DirectedEulerianTrail graph(3);
graph.add_edge(0, 1); // 辺 ID 0
graph.add_edge(1, 2); // 辺 ID 1
auto result = graph.solve();
assert(result);
assert((result->vertices == std::vector<int>{0, 1, 2}));
assert((result->edges == std::vector<int>{0, 1}));

UndirectedEulerianTrail undirected(2);
undirected.add_edge(0, 1);
auto reversed = undirected.solve(1); // 頂点列は {1,0}

操作	内容・返り値	計算量
DirectedEulerianTrail(n = 0)	有向グラフ。EulerianTrail<true> の別名	\(O(1)\)
UndirectedEulerianTrail(n = 0)	無向グラフ。EulerianTrail<false> の別名	\(O(1)\)
EulerianTrail<Directed>(n,edges)	span<const pair<int,int>> の辺列から構築。vector<pair<int,int>> も渡せる	\(O(m)\)
size() / edge_count()	頂点数／辺数	\(O(1)\)
reserve(m)	辺の格納領域を予約	再確保時は既存の辺数に比例
add_edge(u,v)	辺を追加し、追加順の 0 始まりの辺 ID を返す。有向版では u から v	償却 \(O(1)\)
get_edge(id)	辺の両端を pair<int,int> で返す	\(O(1)\)
edges()	入力した辺列の const 参照	\(O(1)\)
clear()	頂点数・確保済み容量を保ち、全ての辺を取り除く	\(O(m)\) 以下
solve(start = -1)	Euler 路を optional<Result> で返す。存在しなければ nullopt	\(O(n+m)\)

頂点番号は [0,n) です。無向辺は add_edge を 1 回だけ呼んで登録します。両方向を別々に登録すると多重辺になります。

Result::vertices は通る順の頂点列、Result::edges は通る順の辺 ID 列で、どちらも vector<int> です。辺が m 本で頂点が存在する場合、長さはそれぞれ m+1・m です。edges[i] は vertices[i] から vertices[i+1] への辺で、無向版では登録時と逆向きに通る場合もあります。辺 ID は自己辺・多重辺も区別します。

start = -1 では始点を自動選択します。有向版の開路なら出次数が入次数より 1 大きい頂点、無向版の開路なら奇数次数の小さい方の頂点を選びます。閉路の場合は辺に接続する最小番号の頂点を選びます。始点を指定した場合は、その頂点から全辺を通る路がなければ nullopt を返します。辞書順最小の路を返す保証はありません。

次数条件だけでなく、全ての辺を使えたかも確認します。辺が別々の連結成分に分かれている場合は nullopt です。辺を持たない孤立点は無視しますが、辺があるのに孤立点を始点として指定した場合は nullopt です。

辺が 0 本なら、頂点が存在する場合は指定した始点だけを含む頂点列を返します。自動選択なら頂点 0 です。頂点数も 0 の場合は、頂点列・辺列が共に空の結果を返します。この場合は既定の solve() を使ってください。

solve() はグラフを変更せず、繰り返し呼べます。辺の追加後も再実行できます。求解結果は独立した配列です。edges() の参照は辺の追加・削除・代入・破棄に伴う通常の vector の規則に従います。

反復版 Hierholzer 法と CSR を使います。探索中の頂点・辺スタックと逆順に確定する結果に、同じ配列の両端を使います。有向版は各辺を 1 回だけ格納し、無向版は両方向の隣接辺と辺 ID ごとの使用済みフラグを持ちます。再帰と辺 ID の復元用の辞書は使いません。

頂点数は INT_MAX 未満、辺数は INT_MAX/2 以下とします。構築は \(O(1)\)、辺列からの構築は \(O(m)\)、辺追加は償却 \(O(1)\)、solve() は \(O(n+m)\) 時間・追加空間です。辺が 0 本の solve() は \(O(1)\) 時間・追加空間です。

検証コード

• test/eulerian_trail_directed.test.cpp
• test/eulerian_trail_undirected.test.cpp

コード

#ifndef EULERIAN_TRAIL_HPP
#define EULERIAN_TRAIL_HPP

#include <cassert>
#include <cstddef>
#include <limits>
#include <memory>
#include <optional>
#include <span>
#include <utility>
#include <vector>

template<bool Directed> class EulerianTrail {
	struct Arc { int to, id; };
	int n_;
	std::vector<std::pair<int, int>> edges_;
	void vertex([[maybe_unused]] int v) const { assert(0 <= v && v < n_); }

  public:
	struct Result { std::vector<int> vertices, edges; };
	explicit EulerianTrail(int n = 0) : n_(n) {
		assert(0 <= n && n < std::numeric_limits<int>::max());
	}
	EulerianTrail(int n, std::span<const std::pair<int, int>> edges) : EulerianTrail(n) {
		reserve(edges.size());
		for (auto [u, v] : edges) add_edge(u, v);
	}
	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() / 2));
		edges_.reserve(m);
	}
	int add_edge(int u, int v) {
		vertex(u), vertex(v);
		assert(edges_.size() < std::size_t(std::numeric_limits<int>::max() / 2));
		int id = edge_count();
		edges_.emplace_back(u, v);
		return id;
	}
	std::pair<int, int> get_edge(int id) const {
		assert(0 <= id && id < edge_count());
		return edges_[id];
	}
	const std::vector<std::pair<int, int>> &edges() const { return edges_; }
	void clear() { edges_.clear(); }
	std::optional<Result> solve(int start = -1) const {
		assert(start == -1 || (0 <= start && start < n_));
		const int m = edge_count();
		if (!m) {
			Result result;
			if (n_) result.vertices.push_back(start == -1 ? 0 : start);
			return result;
		}
		std::vector<int> offset(std::size_t(n_) + 1), balance;
		if constexpr (Directed) balance.resize(n_);
		for (auto [u, v] : edges_) {
			++offset[u + 1];
			if constexpr (Directed) ++balance[u], --balance[v];
			else ++offset[v + 1];
		}
		int required = -1, finish = -1, active = -1;
		for (int v = 0; v < n_; ++v) {
			if (active == -1 && offset[v + 1]) active = v;
			if constexpr (Directed) {
				if (balance[v] == 1 && required == -1) required = v;
				else if (balance[v] == -1 && finish == -1) finish = v;
				else if (balance[v] != 0) return std::nullopt;
			} else if (offset[v + 1] & 1) {
				if (required == -1) required = v;
				else if (finish == -1) finish = v;
				else return std::nullopt;
			}
		}
		if ((required == -1) != (finish == -1)) return std::nullopt;
		if (start == -1) start = required == -1 ? active : required;
		if (required != -1 && start != required) {
			if constexpr (Directed) return std::nullopt;
			else if (start != finish) return std::nullopt;
		}
		if (!offset[start + 1]) return std::nullopt;
		for (int v = 0; v < n_; ++v) offset[v + 1] += offset[v];
		std::unique_ptr<Arc[]> adjacency(new Arc[offset.back()]);
		std::vector<int> cursor(offset.begin(), offset.end() - 1);
		for (int id = 0; id < m; ++id) {
			auto [u, v] = edges_[id];
			adjacency[cursor[u]++] = {v, id};
			if constexpr (!Directed) adjacency[cursor[v]++] = {u, id};
		}
		std::vector<unsigned char> used;
		if constexpr (!Directed) used.resize(m);
		Result result{std::vector<int>(std::size_t(m) + 1), std::vector<int>(m)};
		result.vertices[0] = start;
		int top = 1, vertex_out = m + 1, edge_out = m;
		while (top) {
			int v = result.vertices[top - 1];
			if constexpr (!Directed)
				while (cursor[v] > offset[v] && used[adjacency[cursor[v] - 1].id]) --cursor[v];
			if (cursor[v] > offset[v]) {
				auto [to, id] = adjacency[--cursor[v]];
				if constexpr (!Directed) used[id] = 1;
				result.edges[top - 1] = id;
				result.vertices[top++] = to;
			} else {
				int edge = top > 1 ? result.edges[top - 2] : -1;
				--top;
				result.vertices[--vertex_out] = v;
				if (edge != -1) result.edges[--edge_out] = edge;
			}
		}
		if (edge_out) return std::nullopt;
		return result;
	}
};

using DirectedEulerianTrail = EulerianTrail<true>;
using UndirectedEulerianTrail = EulerianTrail<false>;

#endif

Back to top page