Given an undirected graph, the task is to if adding an edge makes the graph cyclic or not.
In an Undirected graph, a cycle is a path of edges that connects a sequence of vertices back to itself. In other words, a cycle is a closed loop of edges that allows you to traverse the graph and return to the starting vertex.
For example:
A — B
/ \
C D
\ /
E — FIn this graph, there are several cycles that can be formed by following different sequences of edges. For example, the sequence of edges A-B-D-F-E-C-A forms a cycle, as does the sequence B-D-F-E-C-A-B.
Naive approach: The basic way to solve the problem is as follows:
Use depth-first Search to detect the cycle during the insertion of the nodes. If while traversing we reach a node that is already visited. This indicates that cycle is formed.
Follow the steps below to solve the problem:
- Create a detect cycle function that takes a graph and a new node as input.
- Define a dfs function that takes a graph, a node, a set of visited nodes, and a search path array as input.
- In the detectCycle function, initialize an empty set of visited nodes and an empty search path array.
- Call the dfs function, starting from the new node, and passing the graph, visited nodes, and search path array as arguments.
- Return the result of the dfs function.
- In the dfs function, mark the current node as visited and add it to the search path array.
- Check all the neighbors of the current node.
- For each neighbor:
- If the neighbor is already visited, check if it is in the current search path.
- If it is, then we have found a cycle, so return true.
- If it is not visited, continue the DFS from that node. If the DFS returns true, then return true as well.
- Remove the current node from the search path array.
- Return false.
Below is the implementation of the above approach:Recommended Practice
Please try your approach on IDE first, before moving on to the solution.
Try It!
C++
//C++ implementation for the above approach#include <bits/stdc++.h>using namespace std;// Function to traversing over the graphbool dfs(map<int, vector<int> > graph, int node, set<int> visited, vector<int> path){ // Mark the current node as visited visited.insert(node); path.push_back(node); // Check if the node has any neighbors if (graph.count(node) > 0) { // Get the list of neighbors vector<int> neighbors = graph[node]; // Check all the neighbors of the // current node for (int neighbor : neighbors) { if (visited.count(neighbor) > 0) { // If the neighbor is already // visited, check if it is // in the current search path if (std::find(path.begin(), path.end(), neighbor) != path.end()) { // If it is, then we have // found a cycle return true; } } else { // If the neighbor is not // visited, continue the DFS // from that node if (dfs(graph, neighbor, visited, path)) { return true; } } } } // Remove the current node from // the search path path.pop_back(); return false;}// Function to detect cycle is formed// by adding an edgebool detectCycle(map<int, vector<int> > graph, int newNode){ // Perform a DFS starting from the // new node set<int> visited; vector<int> path; bool cycleExists = dfs(graph, newNode, visited, path); // Return true, if cycle formed return cycleExists;}int main(){ // Test the detectCycle function map<int, vector<int> > graph; graph[1] = { 2, 3 }; graph[2] = { 1, 3 }; graph[3] = { 1, 2 }; // Function call if (detectCycle(graph, 4)) { cout << "true" << endl; } else { cout << "false" << endl; } // Add a new node to the graph // that creates a cycle graph[4] = { 1 }; if (detectCycle(graph, 4)) { cout << "true" << endl; } else { cout << "false" << endl; } return 0;}//This code is contributed by Potta Lokesh |
Java
// Java implementation of the above approachimport java.io.*;import java.util.ArrayList;import java.util.Arrays;import java.util.HashMap;import java.util.HashSet;import java.util.List;import java.util.Map;import java.util.Set;public class GraphCycleDetector { // Function to detect cycle is formed // by adding an edge public static boolean detectCycle(Map<Integer, List<Integer> > graph, int newNode) { // Perform a DFS starting from the // new node Set<Integer> visited = new HashSet<>(); List<Integer> path = new ArrayList<>(); boolean cycleExists = dfs(graph, newNode, visited, path); // Return true, if cycle formed return cycleExists; } // Function to traversing over the graph private static boolean dfs(Map<Integer, List<Integer> > graph, int node, Set<Integer> visited, List<Integer> path) { // Mark the current node as visited visited.add(node); path.add(node); // Check if the node has any neighbors if (graph.containsKey(node)) { // Get the list of neighbors List<Integer> neighbors = graph.get(node); // Check all the neighbors of the // current node for (int neighbor : neighbors) { if (visited.contains(neighbor)) { // If the neighbor is already // visited, check if it is // in the current search path if (path.contains(neighbor)) { // If it is, then we have // found a cycle return true; } } else { // If the neighbor is not // visited, continue the DFS // from that node if (dfs(graph, neighbor, visited, path)) { return true; } } } } // Remove the current node from // the search path path.remove(path.size() - 1); return false; } // Driver code public static void main(String[] args) { // Test the detectCycle function Map<Integer, List<Integer> > graph = new HashMap<>(); graph.put(1, Arrays.asList(2, 3)); graph.put(2, Arrays.asList(1, 3)); graph.put(3, Arrays.asList(1, 2)); // Function call System.out.println( detectCycle(graph, 4)); // Add a new node to the graph // that creates a cycle graph.put(4, Arrays.asList(1)); System.out.println( detectCycle(graph, 4)); }} |
Python3
# Python3 implementation of the above approachfrom collections import defaultdict# Function to traversing over the graphdef dfs(graph, node, visited, path): # Mark the current node as visited visited.add(node) path.append(node) # Check if the node has any neighbors if node in graph: # Get the list of neighbors neighbors = graph[node] # Check all the neighbors of the # current node for neighbor in neighbors: if neighbor in visited: # If the neighbor is already # visited, check if it is # in the current search path if neighbor in path: # If it is, then we have # found a cycle return True else: # If the neighbor is not # visited, continue the DFS # from that node if dfs(graph, neighbor, visited, path): return True # Remove the current node from # the search path path.pop() return False# Function to detect cycle is formed# by adding an edgedef detect_cycle(graph, new_node): # Perform a DFS starting from the # new node visited = set() path = [] cycle_exists = dfs(graph, new_node, visited, path) # Return true, if cycle formed return cycle_exists# Test the detect_cycle functiongraph = defaultdict(list)graph[1] = [2, 3]graph[2] = [1, 3]graph[3] = [1, 2]# Function callif detect_cycle(graph, 4): print("true")else: print("false")# Add a new node to the graph# that creates a cyclegraph[4] = [1]if detect_cycle(graph, 4): print("true")else: print("false") # This code is contributed by poojaagarwal2. |
Javascript
function detectCycle(graph, newNode) { // Perform a DFS starting from the new node let visited = new Set() let path = [] let cycleExists = dfs(graph, newNode, visited, path) return cycleExists}function dfs(graph, node, visited, path) { // Mark the current node as visited visited.add(node) path.push(node) // Check if the node has any neighbors if (graph[node]) { // Convert the neighbors to an array if necessary let neighbors = Array.isArray(graph[node]) ? graph[node] : [graph[node]] // Check all the neighbors of the current node for (let neighbor of neighbors) { if (visited.has(neighbor)) { // If the neighbor is already visited, check if it is in the current search path if (path.includes(neighbor)) { // If it is, then we have found a cycle return true } } else { // If the neighbor is not visited, continue the DFS from that node if (dfs(graph, neighbor, visited, path)) { return true } } } } // Remove the current node from the search path path.pop() return false}// Test the detectCycle functionlet graph = { 1: [2, 3], 2: [1, 3], 3: [1, 2],}console.log(detectCycle(graph, 4)) // should print false// Add a new node to the graph that creates a cyclegraph[4] = [1]console.log(detectCycle(graph, 4)) // should print true |
C#
// C# code implementation for the above approachusing System;using System.Collections.Generic;public class GFG { // Function to detect cycle is formed by adding an edge public static bool DetectCycle(Dictionary<int, List<int> > graph, int newNode) { // Perform a DFS starting from the new node var visited = new HashSet<int>(); var path = new List<int>(); var cycleExists = Dfs(graph, newNode, visited, path); // Return true, if cycle formed return cycleExists; } // Function to traversing over the graph private static bool Dfs(Dictionary<int, List<int> > graph, int node, HashSet<int> visited, List<int> path) { // Mark the current node as visited visited.Add(node); path.Add(node); // Check if the node has any neighbors if (graph.ContainsKey(node)) { // Get the list of neighbors var neighbors = graph[node]; // Check all the neighbors of the current node foreach(var neighbor in neighbors) { if (visited.Contains(neighbor)) { // If the neighbor is already visited, // check if it is in the current search // path if (path.Contains(neighbor)) { // If it is, then we have found a // cycle return true; } } else { // If the neighbor is not visited, // continue the DFS from that node if (Dfs(graph, neighbor, visited, path)) { return true; } } } } // Remove the current node from the search path path.RemoveAt(path.Count - 1); return false; } static public void Main() { // Code // Test the DetectCycle function var graph = new Dictionary<int, List<int> >{ { 1, new List<int>{ 2, 3 } }, { 2, new List<int>{ 1, 3 } }, { 3, new List<int>{ 1, 2 } } }; // Function call Console.WriteLine(DetectCycle(graph, 4)); // Add a new node to the graph that creates a cycle graph.Add(4, new List<int>{ 1 }); Console.WriteLine(DetectCycle(graph, 4)); }}// This code is contributed by sankar. |
Output
false true
Time complexity: O(V+E), where V is the number of vertices (or nodes) in the graph, and E is the number of edges in the graph.
Auxiliary Space: O(V)
Efficient Approach: The above approach can be optimized based on the following idea:
- The approach used in the above code is a union-find-based approach to detect cycles in the graph.
- The find() method is used to find the root of the tree representing a given node, and
- the addEdge() method uses the find() method to find the roots of the trees representing the two nodes being connected by the edge.
- If the roots are the same, it means that the two nodes are already in the same connected component, and adding the edge would create a cycle in the graph.
- If the roots are different, the addEdge() method merges the two connected components by attaching the root of the smaller tree to the root of the larger tree.
Below is the implementation of the above approach:
C++
#include <iostream>#include <vector>using namespace std;class Graph { private: int V; // Number of vertices in the graph vector<vector<int> > adj; // Vector of vectors to store the adjacency list of each vertex int *parent; // Array to store the parent of each vertex in the disjoint set int *rank; // Array to store the rank of each vertex in the disjoint set public: Graph(int V) { this->V = V; // Set the number of vertices in the graph adj.resize(V); // Resize the adjacency list to accommodate V vertices parent = new int[V]; // Allocate memory for the parent array rank = new int[V]; // Allocate memory for the rank array for (int i = 0; i < V; i++) { parent[i] = i; // Set the initial parent of each vertex to itself rank[i] = 0; // Set the initial rank of each vertex to 0 } } bool addEdge(int u, int v) { int rootU = find(u); // Find the root of the disjoint set containing vertex u int rootV = find(v); // Find the root of the disjoint set containing vertex v if (rootU == rootV) { // If u and v are already in the same disjoint set, there is no need to add the edge return false; // Return false to indicate that the edge was not added } if (rank[rootU] < rank[rootV]) { // If the rank of the disjoint set containing u is less than the rank of the disjoint set containing v parent[rootU] = rootV; // Make v the parent of u } else if (rank[rootU] > rank[rootV]) { // If the rank of the disjoint set containing u is greater than the rank of the disjoint set containing v parent[rootV] = rootU; // Make u the parent of v } else { // If the rank of the disjoint set containing u is equal to the rank of the disjoint set containing v parent[rootV] = rootU; // Make u the parent of v rank[rootU]++; // Increment the rank of the disjoint set containing u } adj[u].push_back(v); // Add v to the adjacency list of u adj[v].push_back(u); // Add u to the adjacency list of v return true; // Return true to indicate that the edge was added } int find(int u) { if (parent[u] != u) { // If the parent of u is not u, i.e., u is not the root of its disjoint set parent[u] = find(parent[u]); // Recursively find the root of the disjoint set containing u and update the parent of u to point directly to the root } return parent[u]; // Return the root of the disjoint set containing u }};// driver code // Create a graph with 4 verticesint main() { Graph graph(4); graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(1, 2); if (graph.addEdge(2, 3)) { cout << "false" << endl; } else { cout << "true" << endl; } if (graph.addEdge(3, 0)) { cout << "false" << endl; } else { cout << "true" << endl; } return 0;}// this code is contributed by devendrasalunke |
Java
// Java Implementation of the above approachimport java.io.*;import java.util.ArrayList;import java.util.List;public class Graph { private final int V; private final List<List<Integer> > adj; private final int[] parent; private final int[] rank; // Function to create Graph public Graph(int V) { this.V = V; adj = new ArrayList<>(V); for (int i = 0; i < V; i++) { adj.add(new ArrayList<>()); } parent = new int[V]; rank = new int[V]; for (int i = 0; i < V; i++) { parent[i] = i; rank[i] = 0; } } // Function to add edge in graph public boolean addEdge(int u, int v) { // Find the roots of the trees // representing u and v int rootU = find(u); int rootV = find(v); if (rootU == rootV) { // If the roots are the same, // then u and v are already in the // same connected component, so // adding the edge (u, v) would create a cycle return false; } // If the roots are different, merge // the two connected components by // attaching the root of the smaller tree // to the root of the larger tree if (rank[rootU] < rank[rootV]) { parent[rootU] = rootV; } else if (rank[rootU] > rank[rootV]) { parent[rootV] = rootU; } else { parent[rootV] = rootU; rank[rootU]++; } // Add the edge (u, v) to the adjacency // list adj.get(u).add(v); adj.get(v).add(u); return true; } private int find(int u) { // Find the root of the tree // representing u if (parent[u] != u) { parent[u] = find(parent[u]); } return parent[u]; } // Driver code public static void main(String[] args) { Graph graph = new Graph(4); graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(1, 2); // graph.addEdge(2, 3); if (graph.addEdge(2, 3)) { // adding edge(2,3) would not // create a cycle System.out.println("false"); } else { // adding edge (2, 3) would // create a cycle System.out.println("true"); } if (graph.addEdge(3, 0)) { // adding edge(3,0) would not // create a cycle System.out.println("false"); } else { // adding edge (3, 0) would // create a cycle System.out.println("true"); } }} |
Python3
class Graph: def __init__(self, V): self.V = V # Number of vertices in the graph # List of lists to store the adjacency list of each vertex self.adj = [[] for _ in range(V)] # List to store the parent of each vertex in the disjoint set self.parent = list(range(V)) # List to store the rank of each vertex in the disjoint set self.rank = [0] * V def addEdge(self, u, v): # Find the root of the disjoint set containing vertex u rootU = self.find(u) # Find the root of the disjoint set containing vertex v rootV = self.find(v) if rootU == rootV: # If u and v are already in the same disjoint set, there is no need to add the edge return False # Return False to indicate that the edge was not added # If the rank of the disjoint set containing u is less than the rank of the disjoint set containing v if self.rank[rootU] < self.rank[rootV]: self.parent[rootU] = rootV # Make v the parent of u # If the rank of the disjoint set containing u is greater than the rank of the disjoint set containing v elif self.rank[rootU] > self.rank[rootV]: self.parent[rootV] = rootU # Make u the parent of v else: # If the rank of the disjoint set containing u is equal to the rank of the disjoint set containing v self.parent[rootV] = rootU # Make u the parent of v # Increment the rank of the disjoint set containing u self.rank[rootU] += 1 self.adj[u].append(v) # Add v to the adjacency list of u self.adj[v].append(u) # Add u to the adjacency list of v return True # Return True to indicate that the edge was added def find(self, u): # If the parent of u is not u, i.e., u is not the root of its disjoint set if self.parent[u] != u: # Recursively find the root of the disjoint set containing u and update the parent of u to point directly to the root self.parent[u] = self.find(self.parent[u]) # Return the root of the disjoint set containing u return self.parent[u]# driver code# Create a graph with 4 verticesif __name__ == '__main__': graph = Graph(4) graph.addEdge(0, 1) graph.addEdge(0, 2) graph.addEdge(1, 2) if graph.addEdge(2, 3): print("false") else: print("true") if graph.addEdge(3, 0): print("false") else: print("true") |
Javascript
// Define a class called Graphclass Graph { // Constructor takes in number of vertices and initializes necessary properties constructor(V) { // Store the number of vertices this.V = V; // Create an array of arrays to store the adjacency list this.adj = new Array(V); // Initialize each adjacency list to be empty for (let i = 0; i < V; i++) { this.adj[i] = []; } // Initialize the parent array for each vertex to be itself this.parent = new Array(V); for (let i = 0; i < V; i++) { this.parent[i] = i; } // Initialize the rank array for each vertex to be 0 this.rank = new Array(V); for (let i = 0; i < V; i++) { this.rank[i] = 0; } } // Method to add an undirected edge between two vertices addEdge(u, v) { // Find the root of the set that u belongs to let rootU = this.find(u); // Find the root of the set that v belongs to let rootV = this.find(v); // If both vertices belong to the same set, then adding an edge between them will create a cycle if (rootU === rootV) { // Return false to indicate that the edge was not added return false; } // If the rank of the set that u belongs to is smaller than the rank of the set that v belongs to if (this.rank[rootU] < this.rank[rootV]) { // Set the parent of u's root to be v's root this.parent[rootU] = rootV; } // If the rank of the set that v belongs to is smaller than the rank of the set that u belongs to else if (this.rank[rootU] > this.rank[rootV]) { // Set the parent of v's root to be u's root this.parent[rootV] = rootU; } // If the ranks of the sets that u and v belong to are the same else { // Set the parent of v's root to be u's root this.parent[rootV] = rootU; // Increment the rank of the set that u belongs to by 1 this.rank[rootU]++; } // Add v to u's adjacency list this.adj[u].push(v); // Add u to v's adjacency list this.adj[v].push(u); // Return true to indicate that the edge was added return true; } // Method to find the root of the set that a vertex belongs to find(u) { // If the parent of u is not itself (i.e. u is not the root of its set) if (this.parent[u] !== u) { // Recursively find the root of the set that u belongs to this.parent[u] = this.find(this.parent[u]); } // Return the root of the set that u belongs to return this.parent[u]; }}// Create a new graph with 4 verticeslet graph = new Graph(4);// Add edges between verticesgraph.addEdge(0, 1);graph.addEdge(0, 2);graph.addEdge(1, 2);// Try to add an edge between vertices that already belong to the same setif (graph.addEdge(2, 3)) { console.log("false");}else { console.log("true");}if (graph.addEdge(3, 0)) { console.log("false");}else { console.log("true");} |
C#
// C# Implementation of the above approachusing System;using System.Collections.Generic;public class Graph { private List<List<int> > adj; private int[] parent; private int[] rank; // Function to create Graph public Graph(int V) { adj = new List<List<int> >(V); for (int i = 0; i < V; i++) { adj.Add(new List<int>()); } parent = new int[V]; rank = new int[V]; for (int i = 0; i < V; i++) { parent[i] = i; rank[i] = 0; } } // Function to add edge in graph public bool AddEdge(int u, int v) { // Find the roots of the trees representing u and v int rootU = Find(u); int rootV = Find(v); if (rootU == rootV) { // If the roots are the same, then u and v are // already in the same connected component, so // adding the edge (u, v) would create a cycle return false; } // If the roots are different, merge the two // connected components by attaching the root of the // smaller tree to the root of the larger tree if (rank[rootU] < rank[rootV]) { parent[rootU] = rootV; } else if (rank[rootU] > rank[rootV]) { parent[rootV] = rootU; } else { parent[rootV] = rootU; rank[rootU]++; } // Add the edge (u, v) to the adjacency list adj[u].Add(v); adj[v].Add(u); return true; } private int Find(int u) { // Find the root of the tree representing u if (parent[u] != u) { parent[u] = Find(parent[u]); } return parent[u]; } static public void Main() { // Code Graph graph = new Graph(4); graph.AddEdge(0, 1); graph.AddEdge(0, 2); graph.AddEdge(1, 2); // graph.AddEdge(2, 3); if (graph.AddEdge(2, 3)) { // adding edge(2,3) would not create a cycle Console.WriteLine("false"); } else { // adding edge (2, 3) would create a cycle Console.WriteLine("true"); } if (graph.AddEdge(3, 0)) { // adding edge(3,0) would not create a cycle Console.WriteLine("false"); } else { // adding edge (3, 0) would create a cycle Console.WriteLine("true"); } }}// This code is contributed by karthik. |
Output
false true
Time complexity: O(E log V)
Auxiliary Space: O(V)
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!
