Given a connected graph, the task is to find the minimum number of edges to cut/remove to make the given graph disconnected.
A graph is disconnected if there exists at least two vertices of the graph that are not connected by a path.
Examples:
Input:
Output: Minimum Number of Edges to Remove = 2
Approach:
The approach to this problem is to find the number of paths in the edge disjoint set of paths from a start vertex to an end vertex in the graph. Edge-disjoint set of paths is a set of paths having no common edge between any two paths.
- Pick one node as start node and another node as end node.
- Start BFS from the start node and check if a path exists from start node to end node.
- If yes, then remove all the edges from that path and run BFS again.
- Repeat step 2 and 3 until there’s no path exists from start node to end node.
- Return the number of times a path is deleted.
Explanation with example:
Code:
Java
// Java Program to Find// Minimum Number of Edges// to Cut to make the// Graph Disconnectedimport java.util.*;public class GFG { // Function to find the min number of edges public static int minEdgesRemoval(int[][] edges, int n) { // Initialize adjacency list for Graph Map<Integer, List<Integer> > graph = new HashMap<Integer, List<Integer> >(); // Initializing starting and ending vertex int start = edges[0][0]; int end = edges[0][1]; // Create adjacency list of the graph for (int i = 0; i < n; i++) { int n1 = edges[i][0]; int n2 = edges[i][1]; List<Integer> li; // Add edges node 1 if (graph.containsKey(n1)) { li = graph.get(n1); } else { li = new ArrayList<Integer>(); } li.add(n2); graph.put(n1, li); // Add edges node 2 if (graph.containsKey(n2)) { li = graph.get(n2); } else { li = new ArrayList<Integer>(); } li.add(n1); graph.put(n2, li); } // Variable to count the number of paths getting // deleted int deleteEdgeCount = 0; while (true) { // bfsTraversalPath is the BFS path from start // to end node It is a map of parent vertex and // child vertex Map<Integer, Integer> bfsTraversalPath = bfs(graph, start); // If end is present on the path from start node // then delete that path and increment // deleteEdgeCount if (bfsTraversalPath.containsKey(end)) { deleteEdgeCount++; int parent = bfsTraversalPath.get(end); int currEnd = end; // Delete all the edges in the current path while (parent != -1) { deleteEdge(graph, parent, currEnd); deleteEdge(graph, currEnd, parent); currEnd = parent; parent = bfsTraversalPath.get(currEnd); } } // If end is not present in the path // then we have a disconnected graph. else { break; } } return deleteEdgeCount; } // Function to delete/remove an edge private static void deleteEdge(Map<Integer, List<Integer> > graph, Integer start, Integer end) { List<Integer> list = graph.get(start); list.remove(end); } // Function for BFS Path private static Map<Integer, Integer> bfs(Map<Integer, List<Integer> > graph, int start) { // Map for BFS Path Map<Integer, Integer> bfsTraversalPath = new HashMap<Integer, Integer>(); // Array for marking visited vertex List<Integer> visited = new ArrayList<Integer>(); // Array for BFS List<Integer> queue = new ArrayList<Integer>(); int qStartIndex = 0; bfsTraversalPath.put(start, -1); queue.add(start); while (qStartIndex < queue.size()) { int curr = queue.get(qStartIndex++); visited.add(curr); for (int k : graph.get(curr)) { if (!visited.contains(k)) { queue.add(k); if (!bfsTraversalPath.containsKey(k)) { bfsTraversalPath.put(k, curr); } } } } return bfsTraversalPath; } // Driver Code public static void main(String[] args) { // Number of edges int n = 7; // Edge List int[][] edges = { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 3, 4 }, { 4, 0 }, { 4, 1 }, { 1, 3 } }; // Run the function System.out.println("Minimum Number of Edges to Remove = " + minEdgesRemoval(edges, n)); }} |
Output
Minimum Number of Edges to Remove = 2
Complexity Analysis :
Time complexity : O(n^2)
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
