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:
Java
// Java implementation of the above approach
import 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));
}
}
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 function
let 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 cycle
graph[4] = [1]
console.log(detectCycle(graph, 4)) // should print 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:
Java
// Java Implementation of the above approach
import 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");
}
}
}
Time complexity: O(E log V)
Auxiliary Space: O(V)