Skip to content

This repository contains the implementation of Fleury's algorithm for finding Eulerian trails in a graph.

Notifications You must be signed in to change notification settings

karolyp/eulerianPath

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

2 Commits
 
 
 
 
 
 

Repository files navigation

eulerianTrail

This program aims to find Eulerian trails and cycles in a connected graph. The underlying algorithm is the so-called Fleury's algorithm.

The algorithm

The algorithm states that Eulerian trail exists in a graph if and only if the number of odd degrees in the graph is either 0 or 2.

  1. Validate if Eulerian trail exist in the graph
  2. If so, choose a starting point as follows:
    1. If the number of odd vertices is 2, pick one of them (here the first odd one)
    2. If there are no odd vertices pick any arbitrary vertex (here the first one)
  3. u = starting point
  4. While there are edges in the graph, do:
    1. Find edges going out from u
      1. Always go for non-bridge edges
      2. If there are no non-bridge edges left, choose a bridge
    2. Store the other vertex of the edge (nextVertex)
    3. Remove the edge from graph
    4. nextVertex = u

Usage

You can pass a command line argument pointing to an adjacency matrix that contains the graph.

Disclaimer

This source code is only for demonstration purposes for a university class without any performance considerations or optimizations.

About

This repository contains the implementation of Fleury's algorithm for finding Eulerian trails in a graph.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages