Eularian Cycle

An Eularian Cycle is a cycle which every edge is visited exactly once and the starting and ending vertex is the same. Children often play the game of trying to trace through a graph without taking their pencil off the paper, and returning back to where they started. This has the same idea.

Hierholzer's Algorithm

Begin with an arbitrary node. Perform a DFS procedure on this node, each time removing the edge you walk across and the connecting vertex into a stack. Note that if the graph is undirected you will have to remove A->B and B->A. The moment you get struck (cannot move to any other edge), append the top of the stack into the final solution and pop from the stack. Continue from the top of the stack until the stack is empty. Finally return the inverse of solution, since the stack append in the reverse order.

Note that there are multiple possible solutions, and if you use a unordered data-structure, it is bound to return different solutions on different runs.

Complexity: O(|E|) time, and O(|V|^2) space (consider the complete graph)

Consider the following graph:

unordered_map<string, unordered_set<string>> graph =
{
    { "0",{ "1","3" } },
    { "1",{ "2","0","4","5" } },
    { "2",{ "5","4","3","1" } },
    { "3",{ "2","0" } },
    { "4",{ "2","1" } },
    { "5",{ "1","2" } }
};

One possible traversal follows

0 -> 1 -> 2 -> 3 -> 0

stuck. Append 0.

3

stuck. Append 3.

2 -> 4 -> 1 -> 5 -> 2

stuck. At this point all the edges are erased, the algorithm pops and returns all the elements from the stack.

Discussion

What is the intuition behind why an even degree ensures an Eularian Graph?

Because when you traverse the graph and get struck, wherever you got struck, having an even degree ensures that when you come back, you will have somewhere else to go.

Why does the algorithm perform in O(|E|)?

Because we at most ever push a edge once in the stack, and erase the edge after. Therefore it is guaranteed to not reappear in the stack again. The algorithm terminates once the stack is empty, and all edges are erased once.