Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Königsberg Bridge Problem
2.1.
Are you pondering how did he conclude that no path exists?
2.2.
Euler’s Path
2.3.
Euler’s Cycle
3.
Problem Statement
3.1.
Sample Example 1
3.2.
Sample Example 2
4.
Approach
4.1.
Pseudo Code
4.2.
Implementation in C++
4.3.
Implementation in Java
4.3.1.
Output 
4.3.2.
Time Complexity
4.3.3.
Space complexity
5.
Frequently Asked Questions
5.1.
What is an Euler’s Path and Euler’s Cycle?
5.2.
What is ‘The Seven Bridges of Königsberg’ Problem?
5.3.
What is the DFS algorithm?
6.
Conclusion
Last Updated: Mar 27, 2024
Hard

The Seven Bridges of Königsberg

Author Neha Chauhan
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

The ancient town of Königsberg was divided into four land masses by the river Pregel. Seven bridges connected these land masses. The people of Königsberg created a game to find a path that would allow them to walk all over the town crossing the seven bridges exactly once. This problem came to be known as the Seven Bridges of Königsberg. 

 

The Seven Bridges of Konigsberg

 

In this article, we will discuss the solution to the Königsberg Bridge problem and its implementation in C++ and Java. 

Königsberg Bridge Problem

Our story starts in the 18th century, in a town on the banks of the Pregel River. This town was called Königsberg. The river split the town into Four distinct regions which were connected by Seven Bridges. The people of Königsberg liked to walk around the city. They created a game among themselves- Find a path that would allow them to cover all four regions using the seven bridges but - each bridge should be crossed exactly once
 

external bridge img

You can find the above image here.

The famous mathematician Leonhard Euler was asked to solve this puzzle. Even though this puzzle had nothing to do with mathematics, he found it interesting enough to pursue it. This puzzle was found to be related to a topic - Geometry of Positions or what we call today the Graph Theory. So, we can say this problem birthed the Graph Theory. 

Euler divided the problem into small parts. He viewed the four land regions as the four nodes and named them A, B, C, D and the seven bridges as the edges connecting these nodes. 

This was the first time someone had used this kind of representation which we now call a Graph. 

selfmade bridge img

Euler used this Geometry of Positions and gave a negative solution to this problem i.e.walk through Königsberg was NOT possible. 

Are you pondering how did he conclude that no path exists?

As mentioned, Euler viewed the four land masses as vertices (A, B, C, D) and the seven bridges as the edges. 3 bridges join to the land mass A, 3 to B, 5 to C and 3 D. All the four vertices have an odd number of edges (bridges) connected to them and are called Odd Vertices. 

Konigsberg Bridge

Euler worked out that in order for a vertex to be an odd vertex, it should either be a starting vertex or a destination vertex (like if it had only 1 edge, given that we can traverse the edge only once, we can either start from that vertex or finish at that vertex but we cannot turn back and reach the same vertex). Since there can be only one beginning vertex and one ending vertex, there can be only two odd vertices so that we can traverse all the vertices only once, but in this problem, there are 4 odd vertices, hence no path exists!

While solving this problem, Euler came up with some interesting graph traversal techniques - Euler’s Path and Euler’s cycle. 

Euler’s Path

Euler’s path is a path that visits every edge in a graph exactly once. 

Euler’s Cycle

Euler’s cycle is an Euler’s path that starts and ends at the same vertex. 

Euler said that even though the Seven Bridges of Königsberg cannot be solved, there are some other graphs that can be traversed completely by going over each edge exactly once or simply said that there can be graphs that can have an Eulerian Path.

To check if there exists an Eulerian Path, any one of the following conditions must be true -

1️⃣ Two vertices are odd vertices i.e.two vertices have an odd degree.

2️⃣ All of the vertices in the connected graph are of an even degree.

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

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. 																												

 

Input 1

Output

The Euler Path is 2 -> 0 ->1 ->3->0.

 

Output 1

Sample Example 2

Input

The graph has 5 vertices. 

 

Input 2


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

Live masterclass