Problem Statement
You are given an undirected graph with N nodes and M edges, you need to find a path such that we can traverse through ALL the edges EXACTLY once ( i.e. if there exists an Eulerian Path or not.)
Sample Example 1
Input
The graph has 4 vertices.
Output
The Euler Path is 2 -> 0 ->1 ->3->0.
Sample Example 2
Input
The graph has 5 vertices.
Output
There is no Euler Path.
Approach
The input will be an adjacency matrix of the graph. We will store the Eulerian Path in an array called Answer.
Check the number of odd vertices - if there are zero or two odd vertices then call a function that will return the Euler Path.
For finding the Euler Path we will need to find the edges which are non-bridge edges.
For finding the count of the adjacent vertices we will use the Depth First Search Algorithm (DFS Algorithm).
We create three functions -
✅ euler_path - It is a function for storing the Euler path in an array.
✅ isValidNextEdge - It will check whether the edge is a non-bridge edge or a bridge edge. If the graph still stays connected after removing an edge, then that edge is called a non-bridge edge.
✅ dfs - It will return the count of all the reachable vertices from the vertex.
Pseudo Code
Algorithm( Integer no_of_vertices, Array edge_list)
Array answer
Create an adjacency matrix
Int count = 0
For i = 0 to no_of_vertices
If i is odd:
Increase count
If count is NOT equal to 0 or 2:
Put -1 in answer
Return answer
If count is equal to 0
Put 0 in answer
Call Algorithm_euler_path
Else:
For every vertex with odd degree
Put the vertex in answer
Call Algorithm_euler_path
Break
🧩Create an adjacency matrix.
🧩Calculate the number of odd vertices.
🧩 If the number of odd vertices is equal to 0 or 2, then check for the Euler path otherwise, return -1.
Algorithm_euler_path(Integer ver, Array adj, Array answer)
For i =0 to all the neighbors of ver
If ver.isValidNextEdge is true:
Put the corresponding edge in answer
Delete the edge
Call Algorithm_euler_path
🧩Check for all the edges of the given vertex whether it is a Non-bridge edge, by calling isValidNextEdge.
🧩If the edge is a Non-bridge edge, add the vertex to the answer array and delete the edge.
🧩Recurse over the euler_path algorithm.
Algorithm_isValidNextEdge(Inetger ver1, Integer ver2, Array adj)
If ver2 is the only edge of ver1
Return true
Call Algorithm_dfs store result is count_withver2
Remove ver2
Call Algorithm_dfs store result is count_withoutver2
Add ver1 to ver 2
If count_withoutver2 is greater than or equal to count_withver2
Return true
Else
Return false
🧩If ver2 is the only adjacent vertex to ver1, then return true.
🧩Call dfs algorithm and store the count of the adjacent vertices in variable count_withver2.
🧩Remove ver2.
🧩Call dfs algorithm and store the count of the adjacent vertices in variable count_withoutver2.
🧩Add ver2 back.
🧩Return true if count_withoutver2 is greater than count_withver2, else return false.
Try solving the Euler Path problem in Coding Ninjas Studio platform.
Implementation in C++
// A C++ program print Eulerian Trail
#include <iostream>
#include <string.h>
#include <algorithm>
#include <list>
using namespace std;
// A class for undirected graph
class Graph
{
int V;
// A dynamic array of adjacency lists
list<int> *adj;
public:
// Constructor and destructor
Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
~Graph()
{
delete [] adj;
}
// function to add edge
void addEdge(int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
// function to remove edge
void removeEdge(int u, int v);
// Methods to print Euler Path
void printEulerTour();
void printEulerUtil(int s);
// call DFS which will return the count of nodes that are reachable by the vertex v.
int DFSCount(int v, bool visited[]);
// check if edge u-v is a valid next edge in Euler Path
bool isValidNextEdge(int u, int v);
};
void Graph::printEulerTour()
{
// Find a vertex with odd degree
int u = 0;
for (int i = 0; i < V; i++)
if (adj[i].size() & 1)
{
u = i;
break;
}
// Print tour starting from oddv
printEulerUtil(u);
cout << endl;
}
// Print Euler Path starting from vertex u
void Graph::printEulerUtil(int u)
{
// Recurse for all the vertices adjacent to the vertex u
list<int>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
{
int v = *i;
// If edge u-v has not been removed and it's a valid next edge
if (v != -1 && isValidNextEdge(u, v))
{
cout << u << "-" << v << " ";
removeEdge(u, v);
printEulerUtil(v);
}
}
}
// check if edge u-v can be considered as next edge in Euler Path
bool Graph::isValidNextEdge(int u, int v)
{
// The edge u-v is valid in one of the following two cases:
// 1) If v is the only adjacent vertex of u
int count = 0; // To store count of adjacent vertices
list<int>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
if (*i != -1)
count++;
if (count == 1)
return true;
// 2) If there are multiple adjacents, then u-v
// is not a bridge
// Do following steps to check if u-v is a bridge
// 2.a) count of vertices reachable from u
bool visited[V];
memset(visited, false, V);
int count1 = DFSCount(u, visited);
// 2.b) Remove edge (u, v) and after removing the edge, count vertices reachable from u
removeEdge(u, v);
memset(visited, false, V);
int count2 = DFSCount(u, visited);
// 2.c) Add the edge back to the graph
addEdge(u, v);
// 2.d) If count1 is greater, then edge (u, v) is a bridge
return (count1 > count2)? false: true;
}
// This function removes edge u-v from graph.
// It removes the edge by replacing adjacent
// vertex value with -1.
void Graph::removeEdge(int u, int v)
{
// Find v in adjacency list of u and replace
// it with -1
list<int>::iterator iv = find(adj[u].begin(),
adj[u].end(), v);
*iv = -1;
// Find u in adjacency list of v and replace
// it with -1
list<int>::iterator iu = find(adj[v].begin(),
adj[v].end(), u);
*iu = -1;
}
// A DFS based function to count reachable vertices from v
int Graph::DFSCount(int v, bool visited[])
{
// Mark the current node as visited
visited[v] = true;
int count = 1;
// Recur for all vertices adjacent to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (*i != -1 && !visited[*i])
count += DFSCount(*i, visited);
return count;
}
// Driver program to test above function
int main()
{
// Let us first create and test
// graphs shown in above figure
Graph g1(4);
g1.addEdge(0,1);
g1.addEdge(0,2 );
g1.addEdge(0,3 );
g1.addEdge(1, 2);
g1.addEdge(2,3);
g1.printEulerTour();
Graph g2(5);
g2.addEdge(0,4 );
g2.addEdge(0,1 );
g2.addEdge(1,3 );
g2.addEdge(1, 2);
g2.printEulerTour();
return 0;
}
Implementation in Java
// A java program print Eulerian Trail in a given Eulerian or Semi-Eulerian Graph
import java.util.*;
public class Solution{
// A class that represents an undirected graph
static class Graph
{
// No. of vertices
int V;
// A dynamic array of adjacency lists
ArrayList<ArrayList<Integer>> adj;
// Constructor
Graph(int V)
{
this.V = V;
adj = new ArrayList<ArrayList<Integer>>();
for(int i=0; i<V; i++){
adj.add(new ArrayList<Integer>());
}
}
// functions to add and remove edge
void addEdge(int u, int v)
{
adj.get(u).add(v);
adj.get(v).add(u);
}
// This function removes edge u-v from graph.
// It removes the edge by replacing adjacent
// vertex value with -1.
void removeEdge(int u, int v)
{
// Find v in adjacency list of u and replace
// it with -1
int iv = find(adj.get(u), v);
adj.get(u).set(iv, -1);
// Find u in adjacency list of v and replace
// it with -1
int iu = find(adj.get(v), u);
adj.get(v).set(iu, -1);
}
int find(ArrayList<Integer> al, int v){
for(int i=0; i<al.size(); i++){
if(al.get(i) == v){
return i;
}
}
return -1;
}
// Methods to print Eulerian tour
/* The main function that print Eulerian Trail.
It first finds an odd degree vertex (if there is any)
and then calls printEulerUtil() to print the path */
void printEulerTour()
{
// Find a vertex with odd degree
int u = 0;
for (int i = 0; i < V; i++){
if (adj.get(i).size() % 2 == 1)
{
u = i;
break;
}
}
// Print tour starting from oddv
printEulerUtil(u);
System.out.println();
}
// Print Euler tour starting from vertex u
void printEulerUtil(int u)
{
// Recur for all the vertices adjacent to
// this vertex
for (int i = 0; i<adj.get(u).size(); ++i)
{
int v = adj.get(u).get(i);
// If edge u-v is not removed and it's a
// valid next edge
if (v != -1 && isValidNextEdge(u, v))
{
System.out.print(u + "-" + v + " ");
removeEdge(u, v);
printEulerUtil(v);
}
}
}
// This function returns count of vertices
// reachable from v. It does DFS
// A DFS based function to count reachable
// vertices from v
int DFSCount(int v, boolean visited[])
{
// Mark the current node as visited
visited[v] = true;
int count = 1;
// Recur for all vertices adjacent to this vertex
for (int i = 0; i<adj.get(v).size(); ++i){
int u = adj.get(v).get(i);
if (u != -1 && !visited[u]){
count += DFSCount(u, visited);
}
}
return count;
}
// Utility function to check if edge u-v
// is a valid next edge in Eulerian trail or circuit
// The function to check if edge u-v can be considered
// as next edge in Euler Tout
boolean isValidNextEdge(int u, int v)
{
// The edge u-v is valid in one of the following
// two cases:
// 1) If v is the only adjacent vertex of u
int count = 0; // To store count of adjacent vertices
for (int i = 0; i<adj.get(u).size(); ++i)
if (adj.get(u).get(i) != -1)
count++;
if (count == 1)
return true;
// 2) If there are multiple adjacents, then u-v
// is not a bridge
// Do following steps to check if u-v is a bridge
// 2.a) count of vertices reachable from u
boolean visited[] = new boolean[V];
Arrays.fill(visited, false);
int count1 = DFSCount(u, visited);
// 2.b) Remove edge (u, v) and after removing
// the edge, count vertices reachable from u
removeEdge(u, v);
Arrays.fill(visited, false);
int count2 = DFSCount(u, visited);
// 2.c) Add the edge back to the graph
addEdge(u, v);
// 2.d) If count1 is greater, then edge (u, v)
// is a bridge
return (count1 > count2)? false: true;
}
}
// Driver program to test above function
public static void main(String args[])
{
// Let us first create and test graphs shown in above figure
Graph g1(4);
g1.addEdge(0,1);
g1.addEdge(0,2 );
g1.addEdge(0,3 );
g1.addEdge(1, 2);
g1.addEdge(2,3);
g1.printEulerTour();
Graph g2(5);
g2.addEdge(0,4 );
g2.addEdge(0,1 );
g2.addEdge(1,3 );
g2.addEdge(1, 2);
g2.printEulerTour();
}
}
Output
The Euler Path is 2-> 0-> 1-> 3-> 0.
Euler Path does not exist.
Time Complexity
O(N * M), where ‘N’ is the total number of nodes and ‘M’ is the total number of edges in the graph.
Building a graph takes O(M) time as we need to add ‘M’ edges to the graph.
Euler path function takes O(M) time as we need to check O(M) edges in the worst case.
Function isNonBridge is taking O(N) time by calling the dfs function as we need to visit O(N) nodes in the worst case.
So, Euler Path function and isNonBridge function in combination takes O(M*N) time.
Hence, the overall time complexity will be O(M) + O(N * M) = O(N * M).
Space complexity
O(N + M), where ‘N’ is the total number of nodes and ‘M’ is the total number of edges in the graph.
Inserting ‘M’ edges to the adjacency list that takes O(M) space.
The Euler path function takes O(M) stack space in recursive calls as we can have O(M) edges in the recursive stack.
The dfs function takes O(N) stack space in recursive calls as we can have O(N) nodes in the recursive stack. We are using a visited array that takes O(N) space.
Hence, the overall space complexity will be O(M) + O(M) + O(N) + O(N) = O(N + M).
Frequently Asked Questions
What is an Euler’s Path and Euler’s Cycle?
Euler’s path is a path that visits every edge in a graph exactly once. Euler’s cycle is an Euler’s path that starts and ends at the same vertex.
What is ‘The Seven Bridges of Königsberg’ Problem?
In Königsberg town, the river Peri divided the town into 4 land masses- two river banks and 2 islands and they were connected to each other by seven bridges. The people wanted to find a way by which they could walk all over the city by crossing each bridge exactly once. This is the Seven Bridges of Königsberg Problem.
What is the DFS algorithm?
The Depth-First-Search Algorithm traverses the tree or graph data structure as far as possible along the branch without backtracking.
Conclusion
Pat yourself on the back for finishing this article. We discussed what the Königsberg problem is. Along with Königsberg's problem, we discussed Euler’s Path and Euler’s cycle. We finally discussed the pseudo code and the implementation of the code in C++ and Java.
If you liked this article and want to learn more, please read some of our articles -
🔥 Floyd’s Cycle Detection
🔥 0-1 BFS in Graph
🔥 DFS traversal
🔥 M-coloring Problem
Head to the Guided Path on the Coding Ninjas Studio and upskill in Data Structures and Algorithms, Competitive Programming, System Design, and many more courses.
If you want to Practice top Coding Problems, attempt mock tests, or read interview experiences, head to Coding Ninjas Studio, our practice platform.
We wish you Good Luck!🎈 Please upvote our blog 🏆 and help other ninjas grow.
85+ registered