Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Intuition
4.
Approach
4.1.
Implementation in C++
4.2.
Implementation in Java
4.3.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
What is Hierholzer’s Algorithm?
5.2.
What is the Eulerian cycle?
5.3.
What is the time complexity of Hierholzer’s Algorithm?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Hierholzer’s Algorithm for directed Eulerian Graph

Author Sonu Deo
0 upvote
Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

Introduction

If you don’t understand what graph theory is come back after reading Graphs, then only we will continue.

In graph theory, a path that visits all the edges of the graph exactly once is called an Euler path. The Euler path containing the same starting vertex and ending vertex is an Euler Cycle and that graph is termed an Euler Graph. We are going to search for such a path in any Euler Graph by using stack and recursion, also we will be seeing the implementation of it in C++ and Java. 

So, let’s get started by reading our problem statement first.

Hierholzer’s Algorithm for directed eulerian graph

Problem Statement

We will be given a directed Eulerian graph. We have to find the Euler cycle, i.e., the path traversing all the edges exactly once and ending on the starting node.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Intuition

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

Intuition of Hierholzer’s Algorithm

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;
}


Output:

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

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(" -> ");
    }
  
  }
    
}


Output:

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

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. 

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.

Previous article
Floyd Warshall Algorithm At a Glance
Next article
Check if Graph is Bipartite
Live masterclass