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

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.

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

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.

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.

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

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)

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:

If count is equal to 0
Call Algorithm_euler_path
Else:
For every vertex with odd degree
Call Algorithm_euler_path
Break
``````

🧩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

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.

🧩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
public:

// Constructor and destructor
Graph(int V)
{
this->V = V;
}
~Graph()
{
}

{
}

// 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++)
{
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;
{
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;
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

// 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
*iv = -1;

// Find u in adjacency list of v and replace
// it with -1
*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;
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.printEulerTour();

Graph g2(5);

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

// Constructor
Graph(int V)
{
this.V = V;

for(int i=0; i<V; i++){
}
}

// functions to add and remove edge
{
}

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

// Find u in adjacency list of v and replace
// it with -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)
{

// 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){

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

// 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.printEulerTour();

Graph g2(5);

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

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