Find an Eulerian Cycle in a Graph

[hamidgasmi]

Find an Eulerian cycle in a graph.

Input: An Eulerian directed graph Graph = {V,E}, where V is the set of vertices and E is the set of edges, in the form of an adjacency list.

Output: An Eulerian cycle in Graph.

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’

    return Cycle

Input Format.
Each line in the input represents all of the edges leaving a given node u in the format u -> v,w,...
E.g. if there exist nodes (0,1), (0,2), and (0,3), the resulting line in the input would be 0 -> 1,2,3.

Output Format.
An Eulerian cycle in the input graph, in which nodes in the path are delimited by ->.
E.g., for a path from 0 to 1 to 2 back to 0, the resulting output would be: 0->1->2->0

Constraints. |V| ≤ 100; |E| ≤ 100