Eulerian Path

Summary

An Eulerian path is a path in a finite graph that visits every edge exactly once (allowing for revisiting vertices).

An Eulerian cycle is a Eulerian path that starts and ends on the same vertex.

We give the following properties without proof.

An undirected graph has an Eulerian trail iif

1. exactly 0 or 2 vertices have odd degree,
2. its vertices with nonzero degree belong to a single connected component

A directed graph has an Eulerian trail iif

1. at most 1 vertex has (out-degree) − (in-degree) = 1
2. at most one vertex has (in-degree) − (out-degree) = 1
3. every other vertex has equal in-degree and out-degree
4. all of its vertices with nonzero degree belong to a single connected component of the underlying undirected graph.

Hierholzer algorithm

There is an efficient algorithm to finding Euler cycles or paths: the Hierholzer algorithm.

• Step 1). Starting from any vertex, we keep following the unused edges until we get stuck at certain vertex where we have no more unvisited outgoing edges.
• Step 2). We then backtrack to the nearest neighbor vertex in the current path that has unused edges and we repeat the process until all the edges have been used.

The first vertex that we got stuck at would be the end point of our Eulerian path. So if we follow all the stuck points backwards, we could reconstruct the Eulerian path at the end.

Alphabetical Smallest Eulerian Path

class AlphabeticalSmallestEulerianPath {
public:
    unordered_map<string, multiset<string>> m;
    
    list<string> l;
    vector<string> findItinerary(vector<vector<string>>& edges) {
        for (auto const &e : edges) {
            m[e[0]].insert(e[1]);
        }
        string start = kFixedStartPoint;
        dfs(start);
        return vector<string>(l.begin(), l.end());
    }
    
    void dfs(string const &curr) {
        while (m.count(curr)) {
            string next = *m[curr].begin();
            m[curr].erase(m[curr].begin());
            if (m[curr].size() == 0) {
                m.erase(curr);
            }
            dfs(next);
        }
        // Only after all outgoing edges of curr are visited, we return back to the last level 
        l.push_front(curr);
    }
};

Reference

1. OI-Wiki/Euler
2. Wikipedia/Eulerian Path