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 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.
- Validate if Eulerian trail exist in the graph
- If so, choose a starting point as follows:
- If the number of odd vertices is 2, pick one of them (here the first odd one)
- If there are no odd vertices pick any arbitrary vertex (here the first one)
- u = starting point
- While there are edges in the graph, do:
- Find edges going out from u
- Always go for non-bridge edges
- If there are no non-bridge edges left, choose a bridge
- Store the other vertex of the edge (nextVertex)
- Remove the edge from graph
- nextVertex = u
- Find edges going out from u
You can pass a command line argument pointing to an adjacency matrix that contains the graph.
This source code is only for demonstration purposes for a university class without any performance considerations or optimizations.