Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Question
2.1.
Implementation: CPP
2.2.
Output
2.3.
Time Complexity: O(V+E)
3.
Frequently Asked Questions
3.1.
What is the difference between an Eulerian path and a circuit?
3.2.
What do you mean by the Eulerian path?
3.3.
What is a circuit on a graph?
3.4.
What is the difference between Euler circuit and Hamiltonian circuit?
3.5.
Can an Euler circuit also be an Euler trail?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Eulerian Path and Circuit

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

Welcome, Ninjas! We're back with a fresh Data Structure challenge:Eulerian path and circuit. The problem statement will be presented here first, followed by the approach and implementation in CPP with different approaches.

Let's discuss the problem statement that will clear up any questions regarding a graph.

Question

Question

A path known as an Eulerian Path traverses each edge of a graph exactly once. An Eulerian Path that begins and finishes on the same vertex is called an Eulerian Circuit.

Eulerian path and circuit

How can one determine whether or not a particular graph is Eulerian?

The issue is the same as the question that follows

Is it feasible to draw a specific graph without removing the pencil from the paper or repeatedly tracing any of the edges?

EULERIAN path

A graph with an Eulerian Cycle is said to be Eulerian, and if it has an Eulerian Path, it is said to be Semi-Eulerian. The issue is comparable to the NP-complete Hamiltonian Path problem for general graphs. Fortunately, we can determine in polynomial time whether a given graph has an Eulerian Path or not. In actuality, it may be located in O(V+E) time.

The undirected graphs with an Eulerian path and cycle have the following intriguing features. These characteristics can be used to determine if a graph is Eulerian or not.

  • If the two conditions below are true, an undirected graph has an Eulerian cycle.
     
  • All non-zero degree vertices are connected. Vertices of zero degrees are irrelevant to us because they don't fit into the Eulerian Cycle or Path (we only consider all edges).
     
  • Every vertex has an even degree.
     
  • Eulerian Route If the first two conditions are met, an undirected graph has an Eulerian Path.
     
  • If only one or two vertices are oddly oriented while the rest are oriented correctly. Keep in mind that an undirected graph cannot have a single vertex with an odd degree (An undirected graph's sum of all degrees is always even).
     
  • Because there are no edges to traverse, a graph with no edges is said to be Eulerian.

 

How does this work? 

Every time we travel along an Eulerian path, we pass through two unexplored edges with one endpoint as the vertex (v). As a result, the degree of each middle vertex in the Eulerian Path must be even. Since any vertex can be the central vertex in an Eulerian cycle, all vertices must have an even degree.

Implementation: CPP

#include<iostream>
#include <list>
using namespace std;

// A class for undirected graph representation
class Grph
{
	int Vertices; // No. of vertices
	list<int> *adjac; // A dynamic array of adjacency lists
public:
	// Constructor and destructor
	Grph(int Vertices) {this->Vertices = Vertices; 
      adjac = new list<int>[Vertices]; 
    }
    
	~Grph() { 
                delete [] adjac; 
      } // Deconsturctor

	//graphing function to add edges
	void add_Edge(int u, int v);

	//How to determine whether this graph is Eulerian or not
	int CheckEulerian();

	// Method to check if all non-zero degree vertices are connected
	bool CheckConnected();

	// Function to do DFS starting from v. Used in isConnected();
	void DFS_Util(int v, bool vst[]);
};

void Grph::add_Edge(int u, int v)
{
	adjac[u].push_back(v);
	adjac[v].push_back(u); // Note: the graph is undirected
}

void Grph::DFS_Util(int v_new, bool vst[])
{
	//Print the current node's visitation status and mark it.
	vst[v_new] = true;

	//Repeat for every vertex surrounding this one.
	for (auto i = adjac[v_new].begin(); i != adjac[v_new].end(); ++i)
		if (!vst[*i])
			DFS_Util(*i, vst);
}

// Procedure to determine if all vertices with non-zero degrees are //related.
// It primarily performs DFS traversal beginning at
bool Grph::CheckConnected()
{
	// Mark all the vertices as not visited
	bool vst[Vertices];
      int v;
	for (int i = 0; i < Vertices; i++)
		vst[i] = 0;

	//Find a vertex with a degree that is not zero.
	for (int i = 0; i < Vertices; i++)
                  if (adjac[i].size() != 0)
                  {
                       v=i;
			     break;
                  }
	//Return true if the graph has no edges.
	if (v == Vertices)
		return true;

	//DFS traversal should begin at a vertex with a non-zero degree.
	DFS_Util(v, vst);

	// Verify that each non-zero degree vertex has been visited.
	for (int i = 0; i < Vertices; i++)
	if (vst[i] == 0 && adjac[i].size() > 0)
			return false;
	return true;
}

/* The function outputs one of the values listed below.
0 —> If the graph has an Euler path but is not Eulerian 1 (Semi-Eulerian)
2 — If the graph has an Euler Circuit (Eulerian)
*/
int Grph::CheckEulerian()
{
	// Verify that each non-zero degree vertex is connected.
	if (CheckConnected() == false)
		return 0;

	//Count the odd-degree vertices.
	int odd_vert = 0;
	for (int i = 0; i < Vertices; i++)
		if (adjac[i].size()%2==1)
			odd_vert++;

	// Graph is not Eulerian if Count is greater than 2
	if (odd_vert >= 3)
		return 0;

	// Semi-eulerian if the odd Count is 2. When the odd Count is //zero, Euler is used. Take note that for an undirected graph, odd count //can never equal 1.
	return (odd_vert)? 1: 2;
}

// Function to run test cases
void check(Grph &g)
{
	int ans = g.CheckEulerian();
	if (ans == 0)
		cout << "graph is not Eulerian\n";
	else if (ans == 1)
		cout << "graph has a Euler path\n";
	else
		cout << "graph has a Euler cycle\n";
}

// Driver program to test the above function
int main()
{
	// Let us create and test the graphs shown in the above figures
	Grph g1(5);
	
	Grph g2(5);
	g2.add_Edge(1, 0);
	g2.add_Edge(0, 2);
	g2.add_Edge(2, 1);
	g2.add_Edge(0, 3);
	g2.add_Edge(3, 4);
	g2.add_Edge(4, 0);
	check(g2);
      
      g1.add_Edge(1, 0);
	g1.add_Edge(0, 2);
	g1.add_Edge(2, 1);
	g1.add_Edge(0, 3);
	g1.add_Edge(3, 4);
	check(g1);
	return 0;
}

 

Output

graph has a Euler path
graph has a Euler cycle

Time Complexity: O(V+E)

Where V stands for vertices and E stands for Edges. Finding an Eulerian cycle is equivalent to solving the challenge of finding an Eulerian path. 

When there is an Eulerian path for a given graph G, G has precisely two vertices of odd degree. 

Between these vertices, add an edge e, locate an Eulerian cycle on V+E, then take E out of the cycle to get an Eulerian path in G.

Read More - Time Complexity of Sorting Algorithms

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

Frequently Asked Questions

What is the difference between an Eulerian path and a circuit?

Every edge of a graph is utilized exactly once by an Euler path. Every edge of a graph is used precisely once in an Euler circuit.

What do you mean by the Eulerian path?

An Eulerian trail (also known as an Eulerian path) is a finite graph trail in graph theory that reaches each edge exactly once (allowing for revisiting vertices). An analogous Eulerian trail that begins and finishes at the same vertex is known as an Eulerian circuit or cycle.

What is a circuit on a graph?

A circuit is a path that culminates at the starting vertex (so a loop is a circuit of length one). Entire graph A graph with n vertices that is complete (denoted Kn) has n vertices, and each vertex is connected to every other vertex (with one edge between each pair of vertices).

What is the difference between Euler circuit and Hamiltonian circuit?

While a Hamiltonian circuit sees each graph vertex exactly once but may repeat edges, an Eulerian circuit visits each edge in a graph but may repeat vertices.

Can an Euler circuit also be an Euler trail?

A path known as an Euler Path traverses every edge of a graph exactly once. An Euler Path that starts and finishes at the same vertex is known as an Euler Circuit.

The Euler Theorem

  • A graph lacks Euler pathways if it contains more than two vertices of odd degrees.
  • A linked graph contains at least one Euler path if it has 0 or precisely two vertices of odd degree.
  • A graph has at least one Euler circuit if it is linked and has 0 vertices of odd degrees.

Conclusion

Finally, you have reached the article's conclusion. Congratulations!! You gained knowledge of the Eulerian path and circuit in this blog.

Are you eager to read more articles on Graph questions for Interview? Coding Ninjas cover you, so don't worry. View more topics on Coding ninjas.

Check out this problem - Root To Leaf Path

Please refer to our guided pathways on Code studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses, and use the accessible sample exams and questions as a guide. For placement preparations, look at the interview experiences and interview package.

Please do upvote our blogs if you find them helpful and informative!

Happy learning!

Previous article
Minimum Cost Path in a Directed Graph via a Given Set of Necessary Nodes
Next article
Printing Eulerian Path using Fleury's Algorithm
Live masterclass