Hierholzer’s Algorithm for directed Eulerian Graph

Intuition

Consider the graph given below. We will try to find the Eulerian cycle in that graph.

We will maintain one stack during the traversal named tempPath and the other vector as finalPath. Let us start our traversal from node 0 and tempPath initialized with 0:

• Move to 3 (only choice), adding 3 in the tempPath (0, 3)
   
• Move to 2 (only choice), adding 2 in the tempPath (0, 3, 2)
   
• Move to 4 (arbitrary choice), adding 4 in the tempPath (0, 3, 2, 4)
   
• Move to 1 (only choice) adding 1 in the tempPath (0, 3, 2, 4, 1)
   
• Move to 5 (think about this choice), adding 5 in the tempPath (0, 3, 2, 4, 1, 5)
   
• Move to 2 (only choice) adding 2 in the tempPath (0, 3, 2, 4, 1, 5, 2)
   
• Move to 1 (only choice left) adding 5 in the tempPath (0, 3, 2, 4, 1, 5, 2, 1)
   
• Move to 0 (only choice left) adding 0 in the tempPath (0, 3, 2, 4, 1, 5, 2, 1, 0)

We have reached the end of our traversal because we have visited every node in the graph. So we will be backtracking the nodes in tempPath and adding them to the finalPath.

Finally, tempPath will be () and finalPath will be (0, 1, 2, 5, 1, 4, 2, 3, 0)

For the path required, we will print the finalPath in reverse order.

Approach

We will be using Hierholzer’s algorithm for searching the Eulerian path. This algorithm finds an Eulerian circuit in a connected graph with every vertex having an even degree.

1. Select any vertex v and place it on a stack. At first, all edges are unmarked.
    
2. While the stack is not empty, examine the top vertex, u. If u has an unmarked incident edge to a vertex w (say), push w onto the stack and mark the edge uw. If, on the other hand, there are no unmarked incident edges, then remove it from the stack and print it.
    

You will have printed a sequence of vertices that correspond to an Eulerian circuit when the stack is empty.

Implementation in C++

// Implementation of Hierholzer's algorithm in c++
#include <bits/stdc++.h>
using namespace std;

void printfinalPath(vector< vector<int> > adj)
{
	// creating a map to count and modify
    // the edges which are unused
	map<int,int> edges;

	for (int i=0; i<adj.size(); i++)
	{
		// assigning no. of edges to each node
		edges[i] = adj[i].size();
	}

	if (!adj.size())
		return; //empty graph

	// creating the tempPath and finalPath
	stack<int> tempPath;
    vector<int> finalPath;

	// start from any vertex
	tempPath.push(0);
	int v = 0; // Current vertex

    // we will iterate till we visit all the edges
	while (!tempPath.empty())
	{
		// If there's a remaining edge adjacent to v
		if (edges[v])
		{
			// make nxt any unvisited node adjacent to v 
            // mark it as visited
			tempPath.push(v);
			int nxt = adj[v].back();
			edges[v]--;
			adj[v].pop_back();

			// Move to the next vertex
			v = nxt;
		}

		// back-tracking to find the remaining finalPath
		else{
			finalPath.push_back(v);
			v = tempPath.top();
			tempPath.pop();
		}
	}

	// we will print in reverse the finalPath 
    // vector to get our eulerian path
	for (int i=finalPath.size()-1; i>=0; i--){
		cout << finalPath[i];
		if (i)
		cout<<" -> ";
	}
}

int main()
{
	vector< vector<int> > adj;

	adj.resize(6);
	adj[0].push_back(3);
	adj[3].push_back(2);
	adj[2].push_back(1);
	adj[2].push_back(4);
	adj[4].push_back(1);
	adj[1].push_back(0);
	adj[1].push_back(5);
	adj[5].push_back(2);
	printfinalPath(adj);

	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

0 -> 3 -> 2 -> 4 -> 1 -> 5 -> 2 -> 1 -> 0

You can also try this code with Online C++ Compiler

Run Code

Implementation in Java

import java.util.*;
public class Coding_ninjas
{
  public static void main(String args[])
  {
    List< List<Integer> > adj = new ArrayList<>();
  
    // Build the Graph
    adj.add(new ArrayList<Integer>());
    adj.get(0).add(3);
    
    adj.add(new ArrayList<Integer>());
    adj.get(1).add(0);
    adj.get(1).add(5);
    
    adj.add(new ArrayList<Integer>());
    adj.get(2).add(1);
    adj.get(2).add(4);
    
    adj.add(new ArrayList<Integer>());
    adj.get(3).add(2);
    
    adj.add(new ArrayList<Integer>());
    adj.get(4).add(1);


    adj.add(new ArrayList<Integer>());
    adj.get(5).add(2);
    
    printEulerianfinalPath(adj);
  
    
  }
  
  static void printEulerianfinalPath(List< List<Integer> > adj)
  {
    // creating a map to count and modify
    // the edges which are unused
    Map<Integer,Integer> edges=new HashMap<Integer,Integer>();
  
    for (int i=0; i<adj.size(); i++)
    {
        // assigning no. of edges to each node
        edges.put(i,adj.get(i).size());
    }
    
    // Maintain a stack to keep vertices
    Stack<Integer> tempPath = new Stack<Integer>();
    List<Integer> finalPath = new ArrayList<Integer>();
  
    // start from any vertex
    tempPath.push(0);
    int v = 0;  // current vertex
    // we will iterate till we visit all the edges
    while (!tempPath.empty())
    {
        // If there's remaining edge adjacent to v
        if (edges.get(v)>0)
        {
            // make nxt any unvisited node adjacent to v 
            // mark it as visited
            tempPath.push(adj.get(v).get(edges.get(v) - 1));
            edges.put(v, edges.get(v) - 1);
            v = tempPath.peek();
        }
  
        // back-tracking to find the remaining finalPath
        else
        {
            finalPath.add(tempPath.peek());
            v = tempPath.pop();
        }
    }
  
    // we will print in reverse the finalPath 
    // vector to get our eulerian path
    for (int i=finalPath.size()-1; i>=0; i--)
    {
        System.out.print(finalPath.get(i));
        
        if(i!=0)
        System.out.print(" -> ");
    }
  
  }
    
}

You can also try this code with Online Java Compiler

Run Code

Output:

0 -> 3 -> 2 -> 4 -> 1 -> 5 -> 2 -> 1 -> 0

You can also try this code with Online Java Compiler

Run Code

Complexity Analysis

Time Complexity: O(V + E)

This is because we are traversing each edge once, where V is the number of vertices and E is the number of edges.

Space Complexity: O(E)

This is because we are storing E+1 nodes for the eulerian path, where E is the number of edges in the graph.
Check out this problem - No of Spanning Trees in a Graph

Frequently Asked Questions

What is Hierholzer’s Algorithm?

Hierholzer's algorithm's fundamental step is the connection of disjunctive circles to create the Eulerian cycle. It begins with a random node and proceeds to a neighbor by following a random unvisited edge. Until one reaches the starting node, this step is repeated. The first circle results in the graph.

What is the Eulerian cycle?

The Eulerian cycle is a path in which we visit each edge of the graph exactly once and reach the starting vertex again. It is also called as Eulerian Circuit.

What is the time complexity of Hierholzer’s Algorithm?

The time complexity of Hierholzer’s algorithm is O(V+E) because we are traversing each edge once.

Conclusion

In this article, we have discussed Hierholzer’s algorithm and its implementation in C++ and Java. We also discussed Eulerian paths, Eulerian cycles, and Eulerian graphs up to some level.

If you think this blog has helped you enhance your knowledge about the above question, and if you would like to learn more, check out our articles. 

• Kadane's Algorithm
• Greedy Algorithms in Graphs
• Design and Analysis of Algorithms
• Graph Theory

And many more on our website.

Visit our website to read more such blogs. Make sure you enroll in the courses we provide, take mock tests, solve problems, and interview puzzles. Also, you can pay attention to interview stuff- interview experiences and an interview bundle for placement preparations.