Find Euler circuit and path in a graph using Fleury’s algorithm.
In last post, Graphs: Find bridges in connected graphs, we discussed how we can find bridges in an undirected graph. In this post, we will be discussing an algorithm which uses bridges to find Euler’s path in a graph, algorithm is called as Fleury’s algorithm.
Fluery’s algorithm to find Euler path or circuit
- Start from the source node, call it as current node u. If there are nodes with odd degree (there can be max two such nodes), start any one of them. Else start from any node in graph.
- Traverse any edge (u, v) from current node which is not a bridge edge.
- Set current as v and go to step 2
- When all edges which are not bridge edges are traversed, start traversing bridges edges.
- Stop when all nodes are traversed.
Walk through Euler path step by step
1. Graph is as follows, there are two nodes 1 and 6 which have odd degrees, so our candidates for start will be either one of these. Start from 6.
|Initial graph with node 1 and 6 with odd degree|
2. Traverse to 5 and then to 1 and then to 3 followed by 2 one by one as these are not bridge edges.
3. At 2, there are three edges (2,1), (2,4) and (2,4). However, if we follow edge (2,1) then we will burn the bridge and never be able to come back to rest of the graph, hence we will not be going to that edge. So, we will be moving edge (2,4).
4. At 4 again, we have two edges (4,2), (4,6) and (4,3), But if we go through (4,2) we will again burn bridge as (4,2) is bridge edge. Hence, we will traverse (4,3).
5. At 3, we are left with only edge and we will follow it, which will be followed by edge (6,4).
At 4, bridge edge now has to be followed at 4 because there is no option and same for edge (2,1).
Hence, Euler path will be 6-5-1-3-2-4-3-6-4-2-1
Code for Fluery’s algorithm
Please refer Graphs : Euler circuit and Euler path in graphs for detail graph creation and finding if there is an Euler path existing in graph.
Complexity of above algorithm is O ((V + E)* (V+ E)), as for each vertex V, we need to check each edge whether it is bridge or not which take O (V+E) time. Hence, the overall complexity is as given above.