HomeSoftware DevelopmentVerify if including an edge makes the Undirected Graph cyclic or not

# Verify if including an edge makes the Undirected Graph cyclic or not

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 — F

On 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

// 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
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 = 

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 int[] father or mother;
personal closing int[] rank;

// Perform to create Graph
public Graph(int V)
{

this.V = V;
for (int i = 0; i < V; i++) {
}
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]++;
}
// record
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);

// 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");
}

// 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)

RELATED ARTICLES