Given an undirected graph, the duty is to if including 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 again to itself. In different phrases, a cycle is a closed loop of edges that lets you traverse the graph and return to the beginning vertex.
For instance:
  A — B
 /     Â
C Â Â Â Â Â Â D
      /
  E — FOn this graph, there are a number of cycles that may be fashioned by following totally different sequences of edges. For instance, the sequence of edges A-B-D-F-E-C-A kinds a cycle, as does the sequence   B-D-F-E-C-A-B.
Naive strategy: The fundamental method to resolve the issue is as follows:
Use depth-first Search to detect the cycle through the insertion of the nodes. If whereas traversing we attain a node that’s already visited. This means that cycle is fashioned.Â
Observe the steps beneath to unravel the issue:
- Create a detect cycle operate that takes a graph and a brand new node as enter.
- Outline a dfs operate that takes a graph, a node, a set of visited nodes, and a search path array as enter.
- Within the detectCycle operate, initialize an empty set of visited nodes and an empty search path array.
- Name the dfs operate, ranging from the brand new node, and passing the graph, visited nodes, and search path array as arguments.
- Return the results of the dfs operate.
- Within the dfs operate, mark the present node as visited and add it to the search path array.
- Verify all of the neighbors of the present node.
- For every neighbor:
- If the neighbor is already visited, verify whether it is within the present search path.
- Whether it is, then we’ve discovered a cycle, so return true.
- If it isn’t visited, proceed the DFS from that node. If the DFS returns true, then return true as nicely.
- Take away the present node from the search path array.
- Return false.
Beneath is the implementation of the above strategy:
Java
// Java implementation of the above strategy
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Listing;
import java.util.Map;
import java.util.Set;
public class GraphCycleDetector {
// Perform to detect cycle is fashioned
// by including an edge
public static boolean
detectCycle(Map<Integer, Listing<Integer> > graph,
int newNode)
{
// Carry out a DFS ranging from the
// new node
Set<Integer> visited = new HashSet<>();
Listing<Integer> path = new ArrayList<>();
boolean cycleExists
= dfs(graph, newNode, visited, path);
// Return true, if cycle fashioned
return cycleExists;
}
// Perform to traversing over the graph
personal static boolean
dfs(Map<Integer, Listing<Integer> > graph, int node,
Set<Integer> visited, Listing<Integer> path)
{
// Mark the present node as visited
visited.add(node);
path.add(node);
// Verify if the node has any neighbors
if (graph.containsKey(node)) {
// Get the record of neighbors
Listing<Integer> neighbors = graph.get(node);
// Verify all of the neighbors of the
// present node
for (int neighbor : neighbors) {
if (visited.accommodates(neighbor)) {
// If the neighbor is already
// visited, verify whether it is
// within the present search path
if (path.accommodates(neighbor)) {
// Whether it is, then we've
// discovered a cycle
return true;
}
}
else {
// If the neighbor just isn't
// visited, proceed the DFS
// from that node
if (dfs(graph, neighbor, visited,
path)) {
return true;
}
}
}
}
// Take away the present node from
// the search path
path.take away(path.dimension() - 1);
return false;
}
// Driver code
public static void fundamental(String[] args)
{
// Take a look at the detectCycle operate
Map<Integer, Listing<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));
// Perform name
System.out.println(
detectCycle(graph, 4));
// Add a brand new node to the graph
// that creates a cycle
graph.put(4, Arrays.asList(1));
System.out.println(
detectCycle(graph, 4));
}
}
Javascript
operate detectCycle(graph, newNode) {
// Carry out a DFS ranging from the brand new node
let visited = new Set()
let path = []
let cycleExists = dfs(graph, newNode, visited, path)
return cycleExists
}
operate dfs(graph, node, visited, path) {
// Mark the present node as visited
visited.add(node)
path.push(node)
// Verify if the node has any neighbors
if (graph[node]) {
// Convert the neighbors to an array if mandatory
let neighbors = Array.isArray(graph[node]) ? graph[node] : [graph[node]]
// Verify all of the neighbors of the present node
for (let neighbor of neighbors) {
if (visited.has(neighbor)) {
// If the neighbor is already visited, verify whether it is within the present search path
if (path.consists of(neighbor)) {
// Whether it is, then we've discovered a cycle
return true
}
} else {
// If the neighbor just isn't visited, proceed the DFS from that node
if (dfs(graph, neighbor, visited, path)) {
return true
}
}
}
}
// Take away the present node from the search path
path.pop()
return false
}
// Take a look at the detectCycle operate
let graph = {
1: [2, 3],
2: [1, 3],
3: [1, 2],
}
console.log(detectCycle(graph, 4)) // ought to print false
// Add a brand new node to the graph that creates a cycle
graph[4] = [1]
console.log(detectCycle(graph, 4)) // ought to print true
Time complexity:Â O(V+E), the place V is the variety of vertices (or nodes) within the graph, and E is the variety of edges within the graph.
Auxiliary Area: Â O(V)
Environment friendly Strategy: The above strategy could be optimized based mostly on the next concept:
- The strategy used within the above code is a union-find-based strategy to detect cycles within the graph.Â
- The discover() methodology is used to search out the foundation of the tree representing a given node, andÂ
- the addEdge() methodology makes use of the discover() methodology to search out the roots of the timber representing the 2 nodes being related by the sting.Â
- If the roots are the identical, it signifies that the 2 nodes are already in the identical related element, and including the sting would create a cycle within the graph.Â
- If the roots are totally different, the addEdge() methodology merges the 2 related elements by attaching the foundation of the smaller tree to the foundation of the bigger tree.
Beneath is the implementation of the above strategy:
Java
// Java Implementation of the above strategy
import java.io.*;
import java.util.ArrayList;
import java.util.Listing;
public class Graph {
personal closing int V;
personal closing Listing<Listing<Integer> > adj;
personal closing int[] father or mother;
personal closing int[] rank;
// Perform 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<>());
}
father or mother = new int[V];
rank = new int[V];
for (int i = 0; i < V; i++) {
father or mother[i] = i;
rank[i] = 0;
}
}
// Perform so as to add edge in graph
public boolean addEdge(int u, int v)
{
// Discover the roots of the timber
// representing u and v
int rootU = discover(u);
int rootV = discover(v);
if (rootU == rootV) {
// If the roots are the identical,
// then u and v are already within the
// similar related element, so
// including the sting (u, v) would create a cycle
return false;
}
// If the roots are totally different, merge
// the 2 related elements by
// attaching the foundation of the smaller tree
// to the foundation of the bigger tree
if (rank[rootU] < rank[rootV]) {
father or mother[rootU] = rootV;
}
else if (rank[rootU] > rank[rootV]) {
father or mother[rootV] = rootU;
}
else {
father or mother[rootV] = rootU;
rank[rootU]++;
}
// Add the sting (u, v) to the adjacency
// record
adj.get(u).add(v);
adj.get(v).add(u);
return true;
}
personal int discover(int u)
{
// Discover the foundation of the tree
// representing u
if (father or mother[u] != u) {
father or mother[u] = discover(father or mother[u]);
}
return father or mother[u];
}
// Driver code
public static void fundamental(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)) {
// including edge(2,3) wouldn't
// create a cycle
System.out.println("false");
}
else {
// including edge (2, 3) would
// create a cycle
System.out.println("true");
}
if (graph.addEdge(3, 0)) {
// including edge(3,0) wouldn't
// create a cycle
System.out.println("false");
}
else {
// including edge (3, 0) would
// create a cycle
System.out.println("true");
}
}
}
Time complexity: O(E log V)
Auxiliary Area: O(V)
