Eulerian cycle

Another may well know example with 44 solutions

Definition

A Eulerian cycle is a cycle in a directed or undirected graph that contains each edge/arc exactly once. Redundant information for clarification: In the directed case, each arc must have forward orientatin on the cycle.

Input

A strongly connected directed or connected undirected graph.

Output

A Eulerian cycle as an alternating sequence of nodes and edges/arcs or, alternatively, the (correct) message that no such cycle exists.

Known algorithms

Classical eulerian cycle algorithm

Example

• 

  Step 1

• 

  Step 2

• 

  Step 3

• 

  Step 4

• 

  Step 5

• 

  Step 6

• 

  Step 7

• 

  Step 8

• 

  Step 9

• 

  Step 10

• 

  Final Step