×

Search anything:

Fleury’s Algorithm: Finding Eulerian tours in a graph

Internship at OpenGenus

Get this book -> Problems on Array: For Interviews and Competitive Programming


Reading time: 10 minutes | Coding time: 12 minutes

Fleury's algorithm is a simple algorithm for finding Eulerian paths or tours. It proceeds by repeatedly removing edges from the graph in such way, that the graph remains Eulerian.

The steps of Fleury's algorithm is as follows:

  • Start with any vertex of non-zero degree.
  • Choose any edge leaving this vertex, which is not a bridge (cut edges).
  • If there is no such edge, stop.
  • Otherwise, append the edge to the Euler tour, remove it from the graph, and repeat the process starting with the other endpoint of this edge.

Complexity

  • Worst case time complexity: Θ((V+E)^2)
  • Average case time complexity: Θ((V+E)^2)
  • Best case time complexity: Θ((V+E)^2)
  • Space complexity: Θ(V^2)

Pseudocode


vector E
dfs (v):
        color[v] = gray
        for u in adj[v]:
                erase the edge v-u and dfs(u)
        color[v] = black
        push v at the end of e

Problems

Applications

  • Find Eulerian path in a graph
Alexa Ryder

Alexa Ryder

Hi, I am creating the perfect textual information customized for learning. Message me for anything.

Read More

Vote for Author of this article:

Improved & Reviewed by:


Fleury’s Algorithm: Finding Eulerian tours in a graph
Share this