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 fashioned by following totally 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 technique to clear up the issue is as follows:
Use depth-first Search to detect the cycle in the course of 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 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, verify whether it is within the present search path.
- Whether it is, then we have now 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 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 {
// Operate to detect cycle is fashioned
// 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 fashioned
return cycleExists;
}
// Operate 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 record of neighbors
Checklist<Integer> neighbors = graph.get(node);
// Verify all of the neighbors of the
// present node
for (int neighbor : neighbors) {
if (visited.comprises(neighbor)) {
// If the neighbor is already
// visited, verify whether it is
// within the present search path
if (path.comprises(neighbor)) {
// Whether it is, then we have now
// discovered a cycle
return true;
}
}
else {
// If the neighbor shouldn't be
// 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.measurement() - 1);
return false;
}
// Driver code
public static void major(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));
// Operate 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 obligatory
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.contains(neighbor)) {
// Whether it is, then we have now discovered a cycle
return true
}
} else {
// If the neighbor shouldn't be 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 may be optimized based mostly 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() technique is used to search out the basis of the tree representing a given node, and
- the addEdge() technique makes use of the discover() technique 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() technique merges the 2 related parts by attaching the basis of the smaller tree to the basis of the bigger tree.
Beneath 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 closing int V;
non-public closing Checklist<Checklist<Integer> > adj;
non-public closing int[] dad or mum;
non-public closing int[] rank;
// Operate 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<>());
}
dad or mum = new int[V];
rank = new int[V];
for (int i = 0; i < V; i++) {
dad or mum[i] = i;
rank[i] = 0;
}
}
// Operate 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
// identical related element, so
// including the sting (u, v) would create a cycle
return false;
}
// If the roots are totally different, merge
// the 2 related parts by
// attaching the basis of the smaller tree
// to the basis of the bigger tree
if (rank[rootU] < rank[rootV]) {
dad or mum[rootU] = rootV;
}
else if (rank[rootU] > rank[rootV]) {
dad or mum[rootV] = rootU;
}
else {
dad or mum[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;
}
non-public int discover(int u)
{
// Discover the basis of the tree
// representing u
if (dad or mum[u] != u) {
dad or mum[u] = discover(dad or mum[u]);
}
return dad or mum[u];
}
// Driver code
public static void major(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)
