Fleury’s algorithm

Fleury’s algorithmMathworldPlanetmath constructs an Euler circuit in a graph (if it’s possible).

  1. 1.

    Pick any vertex to start

  2. 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. 3.

    Darken that edge, as a reminder that you can’t traverse it again

  4. 4.

    Travel that edge, coming to the next vertex

  5. 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.

Title Fleury’s algorithm
Canonical name FleurysAlgorithm
Date of creation 2013-03-22 13:35:15
Last modified on 2013-03-22 13:35:15
Owner mathcam (2727)
Last modified by mathcam (2727)
Numerical id 9
Author mathcam (2727)
Entry type Algorithm
Classification msc 05C45
Related topic EulerCircuit