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
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.
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?
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 cycleTime 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
46+ registered 