Find minimum weight cycle in an undirected graph | DSA in C++ - Software Development PDF Download

Introduction

In the field of computer science and graph theory, a cycle is a closed path in a graph that starts and ends at the same vertex. The weight of a cycle is defined as the sum of the weights of its edges. In this article, we will explore how to find the minimum weight cycle in an undirected graph using C++.

Prerequisites

To understand this article, you should have a basic understanding of graphs, cycles, and the C++ programming language.

Approach

To find the minimum weight cycle in an undirected graph, we can use the concept of Depth-First Search (DFS). The basic idea is to perform a DFS traversal of the graph starting from each vertex and keep track of the minimum weight cycle encountered so far. We will use an array to keep track of the parent of each vertex during the DFS traversal.

Implementation

Let's start by defining the necessary data structures and functions.

Data Structures

We will use the following data structures:

• 'Edge': A structure to represent an edge in the graph. It contains 'u' and 'v' representing the vertices connected by the edge, and 'weight' representing the weight of the edge.
• 'Graph': A class to represent the graph. It contains the number of vertices 'V' and a vector of edges edges.

Depth-First Search (DFS)

We will implement the DFS traversal using a recursive function called DFSUtil. It will take the current vertex, the visited array, the parent array, the current weight, and the minimum weight cycle as arguments. This function will perform a DFS traversal and update the minimum weight cycle if a smaller cycle is found.

// Recursive utility function for DFS traversal

void DFSUtil(int v, vector<bool>& visited, vector<int>& parent, int weight, int& minWeightCycle, const Graph& graph) {

    visited[v] = true; // Mark the current vertex as visited

    for (const Edge& edge : graph.edges) {

        int u = edge.u;

        int w = edge.weight;

        // If an adjacent vertex is not visited

        if (!visited[u]) {

            parent[u] = v; // Set the current vertex as the parent of the adjacent vertex

            // Recursive DFS call

            DFSUtil(u, visited, parent, weight + w, minWeightCycle, graph);

        }

        // If an adjacent vertex is visited and is not the parent of the current vertex

        else if (u != parent[v]) {

            // Check if the weight of the current cycle is smaller than the minimum weight cycle found so far

            if (weight + w < minWeightCycle) {

                minWeightCycle = weight + w; // Update the minimum weight cycle

            }

        }

    }

}

Minimum Weight Cycle

Now, we will define a function called 'findMinimumWeightCycle' that will initialize the necessary arrays and call the DFS traversal function for each vertex in the graph. It will return the minimum weight cycle found.

// Function to find the minimum weight cycle in the graph

int findMinimumWeightCycle(const Graph& graph) {

    int minWeightCycle = INT_MAX; // Initialize minimum weight cycle with a large value

    // Perform DFS traversal starting from each vertex

    for (int v = 0; v < graph.V; v++) {

        vector<bool> visited(graph.V, false); // Array to track visited vertices

        vector<int> parent(graph.V, -1); // Array to track parents of vertices

        // Recursive DFS call

        DFSUtil(v, visited, parent, 0, minWeightCycle, graph);

    }

    return minWeightCycle;

}

Example

Let's consider the following undirected graph:

          1

    (0)-------(1)

     |         |

    3|         |4

     |         |

    (3)-------(2)

          2

We can represent this graph using the 'Graph' class as follows:

Graph graph(4); // Create a graph with 4 vertices

graph.addEdge(0, 1, 1); // Add edge (0, 1) with weight 1

graph.addEdge(0, 3, 3); // Add edge (0, 3) with weight 3

graph.addEdge(1, 2, 4); // Add edge (1, 2) with weight 4

graph.addEdge(2, 3, 2); // Add edge (2, 3) with weight 2

To find the minimum weight cycle in the graph, we can call the 'findMinimumWeightCycle' function:

int minWeightCycle = findMinimumWeightCycle(graph);

cout << "Minimum Weight Cycle: " << minWeightCycle << endl;

The output will be:

Minimum Weight Cycle: 6

The minimum weight cycle in this graph is '0 -> 1 -> 2 -> 3 -> 0' with a total weight of 6.

Sample Problems

Problem 1: Given an undirected graph, find the minimum weight cycle.

Problem 2: Given a weighted undirected graph, find the minimum weight cycle that passes through a specific vertex.

Problem 3: Given a weighted undirected graph, find the minimum weight cycle that starts and ends at a specific vertex.

Conclusion

In this article, we explored how to find the minimum weight cycle in an undirected graph using the Depth-First Search (DFS) algorithm. We discussed the approach, provided the implementation in C++, and demonstrated an example. Understanding this concept is essential for solving various graph problems efficiently.
Remember to always analyze the time complexity of your solution, as the performance can be affected by the size and structure of the input graph. With the knowledge gained from this article, you are now equipped to tackle problems related to finding minimum weight cycles in undirected graphs.