オイラー路 (Eulerian trail) 無向グラフ版
(include/emthrm/graph/eulerian_trail_in_undirected_graph.hpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Include: #include "emthrm/graph/eulerian_trail_in_undirected_graph.hpp"

オイラー路 (Eulerian trail)

グラフのすべての辺を一度だけ通る路である。

準オイラーグラフ (semi-Eulerian graph)

閉路でないオイラー路が存在するグラフである。

連結グラフ $G$ が準オイラーグラフである必要十分条件は

• $G$ が無向グラフのとき、奇数次数の頂点がちょうど $2$ 個存在することであり、
• $G$ が有向グラフのとき、相対出次数 $1$、相対入次数 $1$ の頂点が一つずつ存在し、他の頂点の相対次数が $0$ であることである。

オイラーグラフ (Eulerian graph)

オイラー閉路 (Euler circuit) が存在するグラフである。

連結グラフ $G$ がオイラーグラフである必要十分条件は

• $G$ が無向グラフのとき、任意の頂点の次数が偶数であることであり、
• $G$ が有向グラフのとき、任意の頂点の相対次数が $0$ であることである。

時間計算量

$O(\lvert V \rvert + \lvert E \rvert)$

仕様

Hierholzer’s algorithm 有向グラフ版

名前	戻り値
template <typename CostType> std::vector<Edge<CostType>> eulerian_trail_in_directed_graph(std::vector<std::vector<Edge<CostType>>> graph, int s = -1);	有向グラフ $\mathrm{graph}$ における始点 $s$ のオイラー路。ただし存在しないときは空配列を返す。

Hierholzer’s algorithm 無向グラフ版

struct EulerianTrailInUndirectedGraph;

メンバ変数

名前	説明
std::vector<int> trail	オイラー路。ただし存在しないときは空配列となる。

メンバ関数

名前	効果・戻り値
explicit EulerianTrailInUndirectedGraph(const int n);	頂点数 $N$ の無向グラフのオブジェクトを構築する。
void add_edge(const int u, const int v);	辺 $(u, v)$ を加える。
bool build(int s = -1);	始点 $s$ のオイラー路を構築できたか。

参考文献

• Carl Hierholzer: Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren, *Mathematische Annalen *, Vol. 6, pp. 30–32 (1873). https://doi.org/10.1007/BF01442866
• https://kokiymgch.hatenablog.com/entry/2017/12/07/193238

オイラー路 有向グラフ版

• http://www.prefield.com/algorithm/graph/directed_euler_path.html

オイラー路 無向グラフ版

• https://github.com/spaghetti-source/algorithm/blob/2c70d7af4d132513fa699a5de5b2aaf21aaf7890/graph/eulerian_path_undirected.cc

Submissons

• オイラー路 有向グラフ版
• オイラー路 無向グラフ版

Verified with

• グラフ/オイラー路 無向グラフ版 (test/graph/eulerian_trail_in_undirected_graph.test.cpp)

Code

#ifndef EMTHRM_GRAPH_EULERIAN_TRAIL_IN_UNDIRECTED_GRAPH_HPP_
#define EMTHRM_GRAPH_EULERIAN_TRAIL_IN_UNDIRECTED_GRAPH_HPP_

#include <algorithm>
#include <cassert>
#include <iterator>
#include <utility>
#include <vector>

namespace emthrm {

struct EulerianTrailInUndirectedGraph {
  std::vector<int> trail;

  explicit EulerianTrailInUndirectedGraph(const int n)
      : n(n), is_visited(n), graph(n) {}

  void add_edge(const int u, const int v) {
    graph[u].emplace_back(v, graph[v].size());
    graph[v].emplace_back(u, graph[u].size() - 1);
  }

  bool build(int s = -1) {
    trail.clear();
    int odd_deg = 0, edge_num = 0;
    for (int i = 0; i < n; ++i) {
      if (graph[i].size() & 1) {
        ++odd_deg;
        if (s == -1) s = i;
      }
      edge_num += graph[i].size();
    }
    edge_num >>= 1;
    if (edge_num == 0) {
      trail = {s == -1 ? 0 : s};
      return true;
    }
    if (odd_deg == 0) {
      if (s == -1) {
        s = std::distance(
            graph.begin(),
            std::find_if_not(graph.begin(), graph.end(),
                             [](const std::vector<Edge>& edges) -> bool {
                               return edges.empty();
                             }));
      }
    } else if (odd_deg != 2) {
      return false;
    }
    for (int i = 0; i < n; ++i) {
      is_visited[i].assign(graph[i].size(), false);
    }
    dfs(s);
    if (std::cmp_equal(trail.size(), edge_num + 1)) {
      std::reverse(trail.begin(), trail.end());
      return true;
    }
    trail.clear();
    return false;
  }

 private:
  struct Edge {
    int dst, rev;
    explicit Edge(const int dst, const int rev) : dst(dst), rev(rev) {}
  };

  const int n;
  std::vector<std::vector<bool>> is_visited;
  std::vector<std::vector<Edge>> graph;

  void dfs(const int ver) {
    const int deg = graph[ver].size();
    for (int i = 0; i < deg; ++i) {
      if (!is_visited[ver][i]) {
        const int dst = graph[ver][i].dst;
        is_visited[ver][i] = true;
        is_visited[dst][graph[ver][i].rev] = true;
        dfs(dst);
      }
    }
    trail.emplace_back(ver);
  }
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EULERIAN_TRAIL_IN_UNDIRECTED_GRAPH_HPP_

#line 1 "include/emthrm/graph/eulerian_trail_in_undirected_graph.hpp"



#include <algorithm>
#include <cassert>
#include <iterator>
#include <utility>
#include <vector>

namespace emthrm {

struct EulerianTrailInUndirectedGraph {
  std::vector<int> trail;

  explicit EulerianTrailInUndirectedGraph(const int n)
      : n(n), is_visited(n), graph(n) {}

  void add_edge(const int u, const int v) {
    graph[u].emplace_back(v, graph[v].size());
    graph[v].emplace_back(u, graph[u].size() - 1);
  }

  bool build(int s = -1) {
    trail.clear();
    int odd_deg = 0, edge_num = 0;
    for (int i = 0; i < n; ++i) {
      if (graph[i].size() & 1) {
        ++odd_deg;
        if (s == -1) s = i;
      }
      edge_num += graph[i].size();
    }
    edge_num >>= 1;
    if (edge_num == 0) {
      trail = {s == -1 ? 0 : s};
      return true;
    }
    if (odd_deg == 0) {
      if (s == -1) {
        s = std::distance(
            graph.begin(),
            std::find_if_not(graph.begin(), graph.end(),
                             [](const std::vector<Edge>& edges) -> bool {
                               return edges.empty();
                             }));
      }
    } else if (odd_deg != 2) {
      return false;
    }
    for (int i = 0; i < n; ++i) {
      is_visited[i].assign(graph[i].size(), false);
    }
    dfs(s);
    if (std::cmp_equal(trail.size(), edge_num + 1)) {
      std::reverse(trail.begin(), trail.end());
      return true;
    }
    trail.clear();
    return false;
  }

 private:
  struct Edge {
    int dst, rev;
    explicit Edge(const int dst, const int rev) : dst(dst), rev(rev) {}
  };

  const int n;
  std::vector<std::vector<bool>> is_visited;
  std::vector<std::vector<Edge>> graph;

  void dfs(const int ver) {
    const int deg = graph[ver].size();
    for (int i = 0; i < deg; ++i) {
      if (!is_visited[ver][i]) {
        const int dst = graph[ver][i].dst;
        is_visited[ver][i] = true;
        is_visited[dst][graph[ver][i].rev] = true;
        dfs(dst);
      }
    }
    trail.emplace_back(ver);
  }
};

}  // namespace emthrm

Back to top page