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 permits you to 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 shaped by following completely different sequences of edges. For instance, the sequence of edges A-B-D-F-E-C-A varieties a cycle, as does the sequence   B-D-F-E-C-A-B.
Naive method: The essential option to remedy the issue is as follows:
Use depth-first Search to detect the cycle throughout the insertion of the nodes. If whereas traversing we attain a node that’s already visited. This means that cycle is shaped.Â
Observe the steps under to resolve 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, examine whether it is within the present search path.
- Whether it is, then now we have 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.
Under is the implementation of the above method:
Java
// Java implementation of the above method
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Checklist;
import java.util.Map;
import java.util.Set;
public class GraphCycleDetector {
// Perform to detect cycle is shaped
// by including an edge
public static boolean
detectCycle(Map<Integer, Checklist<Integer> > graph,
int newNode)
{
// Carry out a DFS ranging from the
// new node
Set<Integer> visited = new HashSet<>();
Checklist<Integer> path = new ArrayList<>();
boolean cycleExists
= dfs(graph, newNode, visited, path);
// Return true, if cycle shaped
return cycleExists;
}
// Perform to traversing over the graph
non-public static boolean
dfs(Map<Integer, Checklist<Integer> > graph, int node,
Set<Integer> visited, Checklist<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 checklist of neighbors
Checklist<Integer> neighbors = graph.get(node);
// Verify all of the neighbors of the
// present node
for (int neighbor : neighbors) {
if (visited.incorporates(neighbor)) {
// If the neighbor is already
// visited, examine whether it is
// within the present search path
if (path.incorporates(neighbor)) {
// Whether it is, then now we have
// 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 principal(String[] args)
{
// Check the detectCycle operate
Map<Integer, Checklist<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 needed
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, examine whether it is within the present search path
if (path.contains(neighbor)) {
// Whether it is, then now we have 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
}
// Check 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 Method: The above method might be optimized primarily based on the next concept:
- The method used within the above code is a union-find-based method to detect cycles within the graph.Â
- The discover() methodology is used to seek out the basis of the tree representing a given node, andÂ
- the addEdge() methodology makes use of the discover() methodology to seek out the roots of the bushes representing the 2 nodes being linked by the sting.Â
- If the roots are the identical, it implies that the 2 nodes are already in the identical linked part, and including the sting would create a cycle within the graph.Â
- If the roots are completely different, the addEdge() methodology merges the 2 linked elements by attaching the basis of the smaller tree to the basis of the bigger tree.
Under is the implementation of the above method:
Java
// Java Implementation of the above method
import java.io.*;
import java.util.ArrayList;
import java.util.Checklist;
public class Graph {
non-public ultimate int V;
non-public ultimate Checklist<Checklist<Integer> > adj;
non-public ultimate int[] mother or father;
non-public ultimate 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<>());
}
mother or father = new int[V];
rank = new int[V];
for (int i = 0; i < V; i++) {
mother or father[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 bushes
// 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
// identical linked part, so
// including the sting (u, v) would create a cycle
return false;
}
// If the roots are completely different, merge
// the 2 linked elements by
// attaching the basis of the smaller tree
// to the basis of the bigger tree
if (rank[rootU] < rank[rootV]) {
mother or father[rootU] = rootV;
}
else if (rank[rootU] > rank[rootV]) {
mother or father[rootV] = rootU;
}
else {
mother or father[rootV] = rootU;
rank[rootU]++;
}
// Add the sting (u, v) to the adjacency
// checklist
adj.get(u).add(v);
adj.get(v).add(u);
return true;
}
non-public int discover(int u)
{
// Discover the basis of the tree
// representing u
if (mother or father[u] != u) {
mother or father[u] = discover(mother or father[u]);
}
return mother or father[u];
}
// Driver code
public static void principal(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)
