Fleury’s algorithm
Fleury’s algorithm
constructs an Euler circuit in a graph (if it’s possible).
- 1.
Pick any vertex to start
- 2.
From that vertex pick an edge to traverse, considering following rule: never cross a bridge of the reduced graph unless there is no other choice
- 3.
Darken that edge, as a reminder that you can’t traverse it again
- 4.
Travel that edge, coming to the next vertex
- 5.
Repeat 2-4 until all edges have been traversed, and you are back at the starting vertex
By “reduced graph” we mean the original graph minus the darkened (already used) edges.