Fleury's algorithm

Fleury’s algorithm is used to find a Euler Path or a Euler Circuit in a connected graph.

Before going further, we need to discuss some terminologies:

Euler Path: Euler Path is a path that visits each edge of a graph exactly once. It may start and end at a different vertex. A graph contain Euler Path only if it has exactly 0 or 2 odd degree vertices.

Euler Circuit: Euler Circuit is a circuit that visits each edge of a graph exactly once. It starts and ends at the same vertex. A graph contain Euler Circuit only if it has exactly 0 odd degree vertices.

Bridge: Bridge is an edge such that removing it from the graph disconnects the graph into 2 connected components. A bridge can never be part of a cycle.

Principle

The basic principle of Fleury’s algorithm is very simple. In order to find the Euler Path or Euler Circuit, the bridge edge should be the last edge we want to cross. This is because the bridge is the only edge connecting the two components of a graph. If we crossed the bridge without visiting all edges in the first component then we cannot come back to the first component without re-visiting the bridge.

For example,

As we already know, Euler Path or Euler Circuit visits each edge exactly once. Thus, the bridge edge is traversed only after visiting all the other edges in the component.

Steps

The first step is to make sure that the graph G is connected and contains exactly 2 or 0 odd degree vertices.
Create a copy of the input graph. Call it G_PAST.
Choose a starting vertex. If the graph contains odd vertices, then it must be one of them. If the graph contains only even vertices, then any vertex can be taken as starting vertex.
Let the starting vertex be v.
If there are zero neighbors of v in G_PAST, then the algorithm is complete.
If there is only one neighbor of v in G_PAST. Let the neighbor be u. Set v = u and delete the edge (v, u) from G_PAST. Go back to step 5.
If there is more than one neighbor of v in G_PAST. Choose a vertex u such that the edge (v, u) is not a bridge edge in G_PAST. Set v = u and delete the edge (v, u) from G_PAST. Go back to step 5.

Step by Step Example

We will perform Fleury’s algorithm on the following graph for illustration.

Step 1
The first step is to create a copy of the graph, G_PAST. Vertex f and d have odd degree. One of them should be chosen as the starting vertex. Let the starting vertex v be ‘f’.

Step 2
We can travel from f to any of the neighbors since none of the edges is a bridge. Travel to a. Set v = a. delete (f, a).

Step 3
We cannot travel from a to d since (a, d) is a bridge. Travel to b. Set v = b and delete (a, b).

Step 4
We cannot travel from b to c since (b, c) is a bridge. Travel to e. Set v = e and delete (b, e).

Step 5
We can only travel to f. Set v = f and delete (e, f).

Step 6
We can only travel to g. Set v = g and delete (f, g).

Step 7
We can only travel to b. Set v = b and delete (g, b).

Step 8
We can only travel to c. Set v = c and delete (b, c).

Step 9
We can only travel to a. Set v = a and delete (c, a).

Step 10
We can only travel to d. Set v = d and delete (a, d).

Step 11
d have no neighbor. Terminate the program.

Euler Path: f-a-b-e-f-g-b-c-a-d

Note: If the graph contains an Euler Circuit, then the path will end at the starting vertex.

Program

We are assuming that the input graph is connected. Also, the input graph is the same as the graph in the above example. The vertices are mapped as such
a-1, b-2, c-3, d-4, e-5, f-6, g-7

#include<iostream>
#include<vector>
using namespace std;

class Graph{
	
	int vertex; // number of vertices
	vector<vector<int>> adj; // adjacency list
	
	public:
		
		// constructor to initialize graph
		// set number of vertices to v
		// initialize adjacency list for v nodes
		Graph(int v){
			vertex = v;
			adj = vector<vector<int>>(v+1);
		}
		
		// add edge (u, v) to graph
		void addEdge(int u, int v){
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
		
		// remove edge (u, v) from the graph
		void removeEdge(int v,int u){
			
			// find vertex u in adjacency list of v
			// swap u with last vertex of adj[v]
			// delete the last vertex
			for(int i=0;i<adj[v].size();++i){
				if(adj[v][i]==u){
					swap(adj[v][i], adj[v][adj[v].size()-1]);
					adj[v].pop_back();
					break;
				}
			}
			
			// find vertex v in adjacency list of u
			// swap v with last vertex of adj[u]
			// delete the last vertex
			for(int i=0;i<adj[u].size();++i){
				if(adj[u][i]==v){
					swap(adj[u][i], adj[u][adj[u].size()-1]);
					adj[u].pop_back();
					break;
				}
			}
			
		}
		
		// function to print euler path or euler circuit
		// the function first checks if the euler contains euler circuit or euler path
		// by counting the number of odd vertices
		void printEulerPathCircuit(){
			
			int odd = 0; // number of vertices with odd degree
			int oddVertex = 0; // it stores vertex with odd degree if it exists
			
			for(int i=1;i<=vertex;++i){
				if(adj[i].size()%2==1){
					++odd;
					oddVertex = i;
				}
			}
			
			if(odd==0){
				// if the number of odd degree vertices is 0
				// the graph contains a Euler Circuit
				// we can use any vertex as the starting vertex
				cout<<"Euler Circuit: ";
				// print euler circuit with '1' as the starting vertex
				printEuler(1);
			}
			else if(odd==2){
				// if the number of odd degree vertices is 0
				// the graph contains a Euler Path
				// starting vertex should be of odd degree
				cout<<"Euler Path: ";
				printEuler(oddVertex);
			}
			else{
				cout<<"Euler Path/Circuit Doesn't Exist"<<endl;
			}
			
		}
		
		// the function to print euler path or circuit
		void printEuler(int v){
			
			// print current edge
			cout<<" "<<v<<" ";
			
			// if there are no adjacent vertices left
			// terminate the program
			if(adj[v].size()==0){
				return;
			}
			
			// if there is only 1 edge connected to v
			// choose that edge
			if(adj[v].size()==1){
				int u = adj[v][0];
				removeEdge(v, u);
				printEuler(u);
				return;
			}	
						
			// traverse all neighbours of v 
			// to find a non-bridge edge
			for(auto u: adj[v]){

				if(isValidEdge(v, u)){
					// if edge (v, u) is not a bridge, that it is valid edge
					// then remove edge (v, u) and set u as the current edge
					removeEdge(v, u);
					printEuler(u);
					return;
				}
				
			}
			
		}
		
		// this function checks if (v, u) is a bridge or not
		bool isValidEdge(int v, int u){
			
			int c1, c2;
			c1 = c2 = 0;
			vector<bool> visited;
			
			// first we remove edge (v, u) from the graph
			// then count the number of vertices we can reach from v
			removeEdge(v, u);
			visited = vector<bool>(vertex+1,false);
			c1 = countConnectedVertices(u, visited);
			
			// we add the vertex (v, u) back to the graph
			// then count the number of vertices we can reach from v
			addEdge(v, u);
			visited = vector<bool>(vertex+1,false);
			c2 = countConnectedVertices(u, visited);
			
			// if c1 == c2, that means vertex (v, u) is not a bridge
			// removing (v, u) doesn't disconnect the graph
			// if c1 != c2, that means vertex (v, u) is a bridge
			// removing (v, u) disconnects the graph
			if(c2 == c1) return true;
			else		 return false;
			
		}
		
		// depth first search to count the number of vertices
		// we can reach from u
		int countConnectedVertices(int u, vector<bool> &visited){
			
			visited[u] = true;
			int count = 1;
			for(auto v: adj[u]){
				if(!visited[v]){
					count += countConnectedVertices(v, visited);
				}
			}
			return count;
			
		}
	
};

int main()
{
	// graph G, containing 7 vertices from 1 to 7.
	Graph G(7);
	
	// adding edges to the graph
	// this graph is same as the graph we used in the above example
	// a-1 b-2 c-3 d-4 e-5 f-6 g-7
	// we are assuming graph is connected and undirected
	G.addEdge(1,2);
	G.addEdge(1,3);
	G.addEdge(1,4);
	G.addEdge(1,6);
	G.addEdge(2,3);
	G.addEdge(2,5);
	G.addEdge(2,7);
	G.addEdge(5,6);
	G.addEdge(6,7);
	
	// function to print Euler Path or Euler Ciruit
	G.printEulerPathCircuit();
}

Output

Euler Path: 6 1 2 7 6 5 2 3 1 4

After mapping the path obtained with the alphabets we get,

Euler Path: f – a – b -g – f – e – b – c – a – d

The Euler Path obtained from the program is different from the example. This is because a graph may contain multiple Euler paths.

Note: The above code modifies the input graph G. We must create a copy of graph G if we don’t want any modification.

Time Complexity

Basically, we are traversing each vertex and each edge attached to that vertex. This takes $O(V+E)$ comparisons. For each edge, we are checking if the edge is a bridge or not using a depth-first search. Checking if an edge is a bridge or not requires $O(V+E)$ comparisons.

$\\*Time Complexity = O(V+E)*O(V+E)\\*\newline\newlineTime\;Complexity = O((V+E)^2)\newline\\*Since\;the\;graph\;is\;connected,\;we\;can\;say\;that\; \\*\newline\dfrac{V*(V-1)}{2}>=E>=V-1\newline\\*Therefore,\newline\\*Time\;Complexity = O(E^2)$