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

Select any vertex v and place it on a stack. At first, all edges are unmarked.

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.