A cycle that traverses each edge of a graph exactly once is called an Eulerian cycle, and we say that a graph containing such a cycle is Eulerian. The following algorithm constructs an Eulerian cycle in an arbitrary directed graph.

EULERIANCYCLE(Graph) form a cycle Cycle by randomly walking in Graph (don't visit the same edge twice!) while there are unexplored edges in Graph select a node newStart in Cycle with still unexplored edges form Cycle’ by traversing Cycle (starting at newStart) and then randomly walking Cycle ← Cycle’ returnCycle

Eulerian Cycle Problem

Find an Eulerian cycle in a graph.

Given: An Eulerian directed graph, in the form of an adjacency list.