Euler path and circuit in graph : Fleury’s algorithm

Euler path or circuit in graph: 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 path in graph, algorithm is called as Fleury’s algorithm.

What is Euler path or circuit in graph?  Euler path is trail in graph which visits each edge only once from source to destination. For example, in following graph, Euler path will be :

euler path in graph

If source and destination are same node, then it becomes Euler’s circuit.
For undirected graphs:
For an undirected graph to have Euler path, each and every node of the graph should have even degree except from start and end node of path which may odd degree. To understand what is degree,please follow the link at the top which explains basics about graphs. To have Euler circuit all nodes should have even degree with no exception.

For directed graphs:
For a directed graph to have Euler path, on each node, number of incoming edges should be equal to number of outgoing nodes except start node where out degree is one more than in degree and end node where incoming is one more than outgoing.
To have Euler circuit, all nodes should have in degree equal to out degree.

We have to keep in mind that for both directed and undirected graphs, above conditions hold when all nodes with non zero degree are part of strongly connected component of graph. To read more on strongly connected component, please follow this link :  Connected components in graph

Euler's path in graph theory

For implementation, count in degree and out degree of each node and check for conditions mentioned earlier. Based on output, Euler path exists or doesn’t .

To check if Euler path exists implementation

#include<stdio.h>
#include<stdlib.h>

#define NUM_NODE 6
#define TRUE 1
#define FALSE 0
typedef struct node{
    int value;
    struct node *next;

}Node;

Node *graph[NUM_NODE];

Node * createNode(int j){

    Node * newNode = (Node *)malloc(sizeof(Node));
    if(newNode){
        newNode->value = j;
        newNode->next = NULL;
    }
    else{
        printf("\n Node cannot be allocated");
    }
    return newNode;
}
void addEdge(int i, int j){

    Node * currentNode = graph[i];
    if(!currentNode){
        graph[i] = createNode(j);
    }
    else{
        while(currentNode->next){
            currentNode = currentNode->next;
        }
        currentNode->next = createNode(j);
    }
    currentNode = graph[j];
    if(!currentNode){
        graph[j] = createNode(i);
    }
    else{
        while(currentNode->next){
            currentNode = currentNode->next;
        }
        currentNode->next = createNode(i);
    }
}

int visited[NUM_NODE + 1];

void dfs(Node * current){
    if(!current) return;
    
    visited[current->value] = TRUE;
    Node *temp = current->next;
    
    while(temp){
        if(visited[temp->value] != TRUE){
            dfs(graph[temp->value]);
        }
        temp = temp->next;
    }
}
int isStrongComponent(Node * graph[], int degree[]){
	int i = 0;
    for(i=1; i<=NUM_NODE; i++){
        if(degree[i] != 0)
            break;
    }
    if(i == NUM_NODE) return TRUE;

    dfs(graph[0]);

    for(int i=1; i<=NUM_NODE; i++){
        if(degree[i] !=0 && visited[i]== FALSE)
            return FALSE;
    }
    return TRUE;
}

int EulerPathExists(Node * graph[]){
    int degree[NUM_NODE+1];
    int count =0;

    for(int i=1; i<=NUM_NODE; i++){
        degree[i] =0;
    }
    for(int i=1; i<=NUM_NODE; i++){
        count =0;
        Node * current  = graph[i];
        while(current){
            current = current->next;
            count++;
        }
        degree[i] = count;
    }
    int connected  = isStrongComponent(graph, degree);
    count = 0;
    for(int i=1; i<=NUM_NODE; i++){
        if(degree[i]%2){
            count++;
        }
    }
    if(count !=0 && count !=2 && !connected) return FALSE;

    return TRUE;
}
int main(){
	
   addEdge(1,4);
   addEdge(2,1);
   addEdge(2,6);
   addEdge(4,3);
   addEdge(3,6);
   addEdge(3,5);
   addEdge(5,6);

    int isEulerPath = EulerPathExists(graph);

    if(isEulerPath)
        printf("\n Graph contains Euler Path");
    else
        printf("\n Graph does not contain Euler Path");
    return 0;
}

Complexity of algorithm to is O(V+E). Once we have figured out that there is a Euler path, we need to find and print the actual path. There are two algorithms for it.
Fleury’s algorithm and Hierholzer’s algorithm. Let’s discuss Fleury’s algorithm.

Fluery’s algorithm to find Euler path or circuit

  1. 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.
  2. Traverse any edge (u, v) from current node which is not a bridge edge.
  3. Set current as v and go to step 2
  4. When all edges which are not bridge edges are traversed, start traversing bridges edges.
  5. 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.
Euler path in graph

2. Traverse to 5 and then to 1 and then to 3 followed by 2 one by one as these are not bridge edges.
Euler path in graph example

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).
euler path in graph implementation

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).
Euler's path

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).
Eulerean path or circuit example
Hence, Euler path will be 6-5-1-3-2-4-3-6-4-2-1

Print Euler path in graph :  Implementation

//This function removes a specific edge from undirected graph
void removeEdge(int start, int end){
    Node * current  = graph[start];
    Node * previous = current;
    Node * temp = NULL;
    if(current->value == end){
        graph[start] = current->next;
    }
    else{
        while(current && current->value != end){
            previous = current;
            current = current->next;
        }
        previous->next = current->next;
    }
    free(current);
 
    current = graph[end];
    previous = current;
    if(current->value == start){
        graph[end] = current->next;
    }
    else{
        while(current && current->value != start){
            previous = current;
            current = current->next;
        }
        previous->next = current->next;
    }
    free(current);
}
 
// Creating status for finding bridges in graph after removal of edge
int DFSUtil(int u, int low[],int d[], int parent[], int *time){
    Node * current  = graph[u];
    Node * v = NULL;
    d[u] = low[u] = ++(*time);
    visited[u] = TRUE;
    for(v = current; v != NULL; v = v->next){
        if(visited[v->value] != TRUE){
            parent[v->value] = u;
            DFSUtil(v->value,low,d, parent,time);
 
            low[u] = min(low[u], low[v->value]);
        }
        if(v->value != parent[u])
            low[u] = min(low[u], low[v->value]);
    }
}
 
Node * getValidNode(int source, int low[], int d[], int visited[]){
    int i =0;
    Node * temp = graph;
    // Find non bridge edge first, if not available then take any edge.
    while(temp){
        if(low[temp->value] <= d){
            return temp;
        }
        temp = temp->next;
    }
    temp = graph;
    return temp;
}
 
void dfs(int current, int low[], int d[], int parent[]){
    int time =0;
    int i;
    //Traversing the node 
    printf("\nCurrent : %d" , current);
    // Getting the next edge to be traversed. It should not be a bridge
    Node *temp = getValidNode(current, low, d, visited);
    while(temp){
        int a = temp->value;
        // Remove the edge which we have traverse from the graph
        remove_edge(current, temp->value);
        for(i=1; i<=NUM_NODE; i++){
            parent[i] = -1;
            low[i] = -1;
            d[i] = -1;
            visited[i] = FALSE;
        }
        // After removal of node, find if calculation
        // for finding if edge is bridge or not.
        DFSUtil(a, low, d, parent, &time);
        // Again go down to the edge which is eligible
        dfs(a, low, d,parent);
        // Find next eligible edge
        temp = getValidNode(current, low, d, visited);
    }
}

// Main function to print Euler path
void printEulerPath(Node * graph[]){
 
    int startNode = EulerPathExists(graph);
 
    int parent[NUM_NODE +1];
    int low[NUM_NODE +1];
    int d[NUM_NODE +1];
    int time=0;
 
    for(int i=1; i<=NUM_NODE; i++){
        parent[i] = -1;
        low[i] = -1;
        d[i] = -1;
        visited[i] = FALSE;
    }
    // Create book keeping to fin if edge is a bridge or not.
    DFSUtil(startNode, low, d, parent, &time);
    dfs(startNode,low, d, parent);
}
 

Complexity of  Fluery’s algorithm to find Euler path 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.

Please share if there is something missing or wrong, If you are interested in contributing to website or have an interview experience to share, please contact us and earn.