1.
Introduction
2.
Problem Statement
3.
Intuition
4.
Approach
4.1.
Implementation in C++
4.2.
Implementation in Java
4.3.
Complexity Analysis
5.
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

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.

## 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.

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

{
// creating a map to count and modify
// the edges which are unused
map<int,int> edges;

{
// assigning no. of edges to each node
}

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);
edges[v]--;

// 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()
{

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

}

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

{
// assigning no. of edges to each node
}

// 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
edges.put(v, edges.get(v) - 1);
v = tempPath.peek();
}

// back-tracking to find the remaining finalPath
else
{
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

### 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.

Live masterclass