Thursday, February 9, 2023
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


Enhance Article

Save Article

Like Article

Enhance Article

Save Article

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

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

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments