In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex.
We have the following properties for undirected graph,
- An undirected graph has an Eulerian cycle if and only if every vertex has even degree, and all of its vertices with nonzero degree belong to a single connected component.
- An undirected graph can be decomposed into edge-disjoint cycles if and only if all of its vertices have even degree. So, a graph has an Eulerian cycle if and only if it can be decomposed into edge-disjoint cycles and its nonzero-degree vertices belong to a single connected component.
- An undirected graph has an Eulerian trail if and only if exactly zero or two vertices have odd degree, and all of its vertices with nonzero degree belong to a single connected component
We have the following properties for directed graph,
- A directed graph has an Eulerian cycle if and only if every vertex has equal in degree and out degree, and all of its vertices with nonzero degree belong to a single strongly connected component. Equivalently, a directed graph has an Eulerian cycle if and only if it can be decomposed into edge-disjoint directed cycles and all of its vertices with nonzero degree belong to a single strongly connected component.
- A directed graph has an Eulerian trail if and only if at most one vertex has (out-degree) − (in-degree) = 1, at most one vertex has (in-degree) − (out-degree) = 1, every other vertex has equal in-degree and out-degree, and all of its vertices with nonzero degree belong to a single connected component of the underlying undirected graph.
Hierholzer’s algorithm
- Choose any starting vertex v, and follow a trail of edges from that vertex until returning to v. It is not possible to get stuck at any vertex other than v, because the even degree of all vertices ensures that, when the trail enters another vertex w there must be an unused edge leaving w. The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.
- As long as there exists a vertex u that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from u, following unused edges until returning to u, and join the tour formed in this way to the previous tour.
- Since we assume the original graph is connected, repeating the previous step will exhaust all edges of the graph.
By using a data structure such as a doubly linked list to maintain the set of unused edges incident to each vertex, to maintain the list of vertices on the current tour that have unused edges, and to maintain the tour itself, the individual operations of the algorithm (finding unused edges exiting each vertex, finding a new starting vertex for a tour, and connecting two tours that share a vertex) may be performed in constant time each, so the overall algorithm takes linear time, {\displaystyle O(|E|)}
This algorithm may also be implemented with a deque. Because it is only possible to get stuck when the deque represents a closed tour, one should rotate the deque by removing edges from the tail and adding them to the head until unstuck, and then continue until all edges are accounted for. This also takes linear time, as the number of rotations performed is never larger than {\displaystyle |E|}
// need to remove arbitary edges once visited, thus we use double linked list
unordered_map<int, list<int>> node_to_nexts;
// https://en.wikipedia.org/wiki/Eulerian_path#Hierholzer's_algorithm
// at most 2 points that indegree is not equal to outdegree
unordered_map<int, int> indegree;
unordered_map<int, int> outdegree;
unordered_set<int> nodes;
deque<int> eulerian_path;
void Dfs(int curr) {
while (!node_to_nexts[curr].empty()) {
int next = *node_to_nexts[curr].begin();
node_to_nexts[curr].erase(node_to_nexts[curr].begin());
Dfs(next);
}
eulerian_path.push_front(curr);
}
vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
for (auto const& p : pairs) {
node_to_nexts[p[0]].insert(node_to_nexts[p[0]].end(), p[1]);
indegree[p[1]]++;
outdegree[p[0]]++;
nodes.insert(p[0]);
nodes.insert(p[1]);
}
// if there's a cycle, start can be any point
int start = pairs[0][0];
for (auto const& node : nodes) {
if (int out = outdegree[node], in = indegree[node]; in != out) {
if (in < out) {
assert(out - in == 1);
start = node;
}
}
}
Dfs(start);
}Reference
https://en.wikipedia.org/wiki/Eulerian_path#Hierholzer’s_algorithm