Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Solution
3.1.
Algorithm
4.
Code Implementation
4.1.
C++
4.2.
Python
4.3.
Time and Space Complexity
5.
Frequently Asked Questions
5.1.
What is a Graph?
5.2.
What is an Undirected Graph?
5.3.
What is a Directed Graph?
5.4.
What is Dijkstra Algorithm?
5.5.
What is a weighted graph?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

Find Minimum Weight Cycle in an Undirected Graph

Author Rajat Agrawal
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

A graph is a non-linear data structure made up of nodes and edges. In a graph, the edges are the lines or arcs that link any two nodes, and the nodes are occasionally referred to as vertices. Formally, a graph is described as,

A graph is made up of a finite set of vertices, also known as nodes, and a set of edges, which link each pair of nodes together.

Graph

In this blog, we will learn how to find the minimum weight cycle in an undirected graph.

Also checkout Application of graph data structure

Problem Statement

Given a weighted undirected graph having positive edge weights, find the minimum weight cycle in it.

Example

Weighted Graph

There are three cycles in the undirected graph given above.

Cycle1: 0->1->4->5->3->2->0

The sum of edge weights for Cycle1 is (2 + 6 + 8 + 7 + 1 + 4) = 28.

Cycle2: 0->1->4->3->2->0

The sum of edge weights for Cycle2 is (2 + 6 + 3 + 1 + 4) = 16.

Cycle3: 4->5->3->4

The sum of edge weights for Cycle3 is (8 + 7 + 3) = 18.

The minimum edge weight cycle among all three cycles is Cycle2, with an edge weight of 16.

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

Solution

The objective is to use the shortest path algorithm. We first delete each edge from the graph one at a time before calculating the shortest distance between any two corner vertices. Before we process the next edge, we add an edge back.

Algorithm

Let’s discuss the algorithm steps.

Step1: Create an empty vector of size "E" ( E is the total number of edges). Each element of this vector holds information about every edge in the graph.

Step2: Traverse each edge[i] one at a time.

  • Remove the 'edge[i]' from graph 'G' first.
  • Get the current edge vertices that we just deleted from the graph.
  • Using Dijkstra's shortest path algorithm, determine the shortest path between them.
  • To create a cycle, we add the weight of the edge that was removed to the shortest path.
  • If necessary, update min_weight_cycle.


Step3: Finally, return the minimum weighted cycle.

Code Implementation

C++

#include<bits/stdc++.h>
using namespace std;
# define INF 0x3f3f3f3f

// creating a struct for an edge
struct Edge
{
	int u, v, wt;
};

class Graph
{
	int V;
	// adjacency list
	list < pair <int, int > >*adjacency;

	vector < Edge > edges;

	public :
	Graph( int V )
	{
		this->V = V ;
		adjacency = new list < pair <int, int > >[V];
	}

	// declaring all the functions
	// inserting an edge
	void insertEdge ( int u, int v, int w );

	// deleting an edge
	void deleteEdge( int u, int v, int w );

	// finding minimum path
	int minimumPath (int u, int v );

	// deleting an edge
	void deleteEdge( int u, int v );

	// finding min cycles
	int FindMinCycle();

};

// inserting an edge
void Graph :: insertEdge ( int u, int v, int w )
{
	adjacency[u].push_back( make_pair( v, w ));
	adjacency[v].push_back( make_pair( u, w ));

	Edge e = { u, v, w };
	edges.push_back ( e );
}

// deleting an edge
void Graph :: deleteEdge( int u, int v, int w )
{
	adjacency[u].remove(make_pair( v, w ));
	adjacency[v].remove(make_pair(u, w ));
}

// finding minimum path function
int Graph :: minimumPath ( int u, int v )
{
	// storing vertices
	set< pair<int, int> > setds;

	// vector for distances
	vector<int> dist(V, INF);

	/* insert self source at first and initialize its distance as 0 */ 
	setds.insert(make_pair(0, u));
	dist[u] = 0;

	while (!setds.empty())
	{
/* The first vertex in Set is the one with the shortest distance; remove it from Set. */
		pair<int, int> tmp = *(setds.begin());
		setds.erase(setds.begin());

/* To preserve the vertices sorted distance, vertex label must be put in second of pair (distance must be first item in pair) */
		int u = tmp.second;
		list< pair<int, int> >::iterator i;
		for (i = adjacency[u].begin(); i != adjacency[u].end(); ++i)
		{
			int v = (*i).first;
			int weight = (*i).second;

			if (dist[v] > dist[u] + weight)
			{
/* If the distance of v is not INF, then it must be in our set; therefore, it should be removed and reinserted with an updated shorter distance. We only remove from Set the vertices for which the distance has been determined. Therefore, they would never see us arrive here. */
				if (dist[v] != INF)
				setds.erase(setds.find(make_pair(dist[v], v)));
				dist[v] = dist[u] + weight;
				setds.insert(make_pair(dist[v], v));
			}
		}
	}

	return dist[v] ;
}

// finding minimum path function
int Graph :: FindMinCycle ( )
{
	int min_cycle = INT_MAX;
	int E = edges.size();
	for ( int i = 0 ; i < E ; i++ )
	{
		Edge e = edges[i];
/* Obtain the edge vertices that we currently delete from the graph, and then use Dijkstra's shortest path technique to discover the shortest path between these two vertices. */
		deleteEdge( e.u, e.v, e.wt ) ;

		int dist = minimumPath( e.u, e.v );

/* If this is the shortest cycle, update min cycle; otherwise, add weight to currently deleted edges to create a cycle. */
		min_cycle = min(min_cycle, dist + e.wt);

		// add current edge back to the graph
		insertEdge( e.u, e.v, e.wt );
	}

	return min_cycle ;
}

int main()
{
	int V = 6;
	Graph g(V);

	g.insertEdge(0,1,2);
    	g.insertEdge(0,2,4);
    	g.insertEdge(1,4,6);
    	g.insertEdge(2,3,1);
    	g.insertEdge(3,4,3);
    	g.insertEdge(3,5,7);
    	g.insertEdge(4,5,8);
	cout << "Minimum weight cycle in the graph is: "<<g.FindMinCycle() << endl;
	return 0;
}


Output

Minimum weight cycle in the graph is 16.

Python

# Minimum weight cycle in an undirected graph
from sys import maxsize

INF = int(0x3f3f3f3f)

class Edge:

	def __init__(self, u: int,v: int,wt: int) -> None:

		self.u = u
		self.v = v
		self.wt = wt

class Graph:

	def __init__(self, V: int) -> None:

		self.V = V
		self.adjacency = [[] for _ in range(V)]

		self.edge = []

	# inserting an edge
	def addEdge(self, u: int, v: int, w: int) -> None:

		self.adjacency[u].append((v, w))
		self.adjacency[v].append((u, w))

		e = Edge(u, v, w)
		self.edge.append(e)

	#removing an edge
	def removeEdge(self, u: int, v: int, w: int) -> None:

		self.adjacency[u].remove((v, w))
		self.adjacency[v].remove((u, w))

	# finding minimum path
	def minimumPath(self, u: int, v: int) -> int:

		"""The first vertex in Set is the one with the shortest distance; remove it from Set."""
		setds = set()

		dist = [INF] * self.V

		setds.add((0, u))
		dist[u] = 0

		while (setds):

			tmp = setds.pop()

"""To preserve the vertices sorted distance, vertex label must be put in second of pair (distance must be first item in pair)"""
			uu = tmp[1]

			for i in self.adjacency[uu]:

			vv = i[0]
			wt = i[1]

			if (dist[vv] > dist[uu] + wt):
"""If the distance of v is not INF, then it must be in our set; therefore, it should be removed and reinserted with an updated shorter distance. We only remove from Set the vertices for which the distance has been determined. Therefore, they would never see us arrive here."""
				if (dist[vv] != INF):
					if ((dist[vv], vv) in setds):
						setds.remove((dist[vv], vv))

			dist[vv] = dist[uu] + wt
			setds.add((dist[vv], vv))

		return dist[v]

		# finding minimum cycle
		def FindMinCycle(self) -> int:

			min_cycle = maxsize
			E = len(self.edge)

			for i in range(E):

			e = self.edge[i]

"""Obtain the edge vertices that we currently delete from the graph, and then use Dijkstra's shortest path technique to discover the shortest path between these two vertices."""
			self.removeEdge(e.u, e.v, e.wt)

			distance = self.minimumPath(e.u, e.v)

"""If this is the shortest cycle, update min cycle; otherwise, add weight to currently deleted edges to create a cycle."""
			min_cycle = min(min_cycle,distance + e.wt)

			# adding current edge back to the graph
			self.addEdge(e.u, e.v, e.wt)

			return min_cycle

# Main Code
if __name__ == "__main__":

        V = 6

        g = Graph(V)

        g.addEdge(0,1,2) 
        g.addEdge(0,2,4)
        g.addEdge(1,4,6)
        g.addEdge(2,3,1)
        g.addEdge(3,4,3)
        g.addEdge(3,5,7)
        g.addEdge(4,5,8)

        print("Minimum weight cycle in the graph is: ",g.FindMinCycle())


Output

Minimum weight cycle in the graph is 16.

Time and Space Complexity

Time Complexity: O( E *(E * log V)), For every edge, we run Dijkstra’s shortest path algorithm so overall time complexity E^2*(logV). Where E is the number of edges and V is the number of vertices in the graph.

Space Complexity: O(V+E) where V denotes the number of vertices and  E is the number of edges in the graph.

Check out this problem - Pair Sum In Array.

Frequently Asked Questions

What is a Graph?

A graph is a non-linear data structure made up of nodes and edges. In a graph, the edges are the lines or arcs that link any two nodes, and the nodes are occasionally referred to as vertices.

What is an Undirected Graph?

Undirected graphs have edges that do not have a direction. Each edge may be traversed in both directions, which indicates a two-way connection.

What is a Directed Graph?

A directed graph is one where all the edges are directed from one vertex to another. There is only a one-way connection between vertices.

What is Dijkstra Algorithm?

Dijkstra's algorithm is used to find the shortest path between any two vertices of a graph.

What is a weighted graph?

A weighted graph is one in which the edges are labelled with numbers (called weights).

Conclusion

In this article, we have extensively discussed how to find the minimum weight cycle in an undirected graph, its algorithm, space and time complexity, and implementation in different programming languages. 

If you want to learn more, check out our articles on Construct the Full K-ary Tree from its Preorder TraversalDetect cycle in an undirected graph, Regular and Bipartite graphs, and Planar and Non-Planar Graphs.

Happy Coding!

Previous article
Find All Possible Words in a Board of Characters
Next article
Find the Shortest Path in a Weighted Graph where the Weight of an Edge is 1 or 2
Live masterclass