Detectar ciclo en un gráfico dirigido usando BFS

Dado un gráfico dirigido, compruebe si el gráfico contiene un ciclo o no. Su función debería devolver verdadero si el gráfico dado contiene al menos un ciclo, de lo contrario devolverá falso. Por ejemplo, el siguiente gráfico contiene dos ciclos 0->1->2->3->0 y 2->4->2, por lo que su función debe devolver verdadero.

Hemos discutido una solución basada en DFS para detectar ciclos en un gráfico dirigido . En esta publicación, se analiza la solución basada en BFS .
La idea es simplemente usar el algoritmo de Kahn para la clasificación topológica

Pasos involucrados en la detección de ciclos en un gráfico dirigido usando BFS.
Paso 1: calcule el grado de entrada (número de aristas entrantes) para cada uno de los vértices presentes en el gráfico e inicialice el recuento de Nodes visitados como 0.
Paso 2: elija todos los vértices con grado de entrada 0 y agréguelos en una cola (operación Enqueue)
Paso 3: Eliminar un vértice de la cola (operación Dequeue) y luego. 

  1. Incremente el recuento de Nodes visitados en 1.
  2. Disminuya el grado en 1 para todos sus Nodes vecinos.
  3. Si el grado de entrada de un Node vecino se reduce a cero, agréguelo a la cola.

Paso 4: repita el paso 3 hasta que la cola esté vacía.
Paso 5: si el número de Nodes visitados no es igual al número de Nodes en el gráfico tiene ciclo, de lo contrario no.

¿Cómo encontrar el grado de entrada de cada Node?  
Hay 2 formas de calcular el grado de entrada de cada vértice: 
Tome una array de grados de entrada que realizará un seguimiento de 
1) Atraviese la array de bordes y simplemente aumente el contador del Node de destino en 1. 

for each node in Nodes
    indegree[node] = 0;
for each edge(src,dest) in Edges
    indegree[dest]++

Complejidad temporal: O(V+E)

2) Recorra la lista para cada Node y luego incremente el grado de entrada de todos los Nodes conectados a él en 1. 

    for each node in Nodes
        If (list[node].size()!=0) then
        for each dest in list
            indegree[dest]++;

Complejidad de tiempo: el bucle for externo se ejecutará V número de veces y el bucle for interno se ejecutará E número de veces, por lo que la complejidad de tiempo general es O (V + E).

La complejidad temporal general del algoritmo es O(V+E) 

C++

// A C++ program to check if there is a cycle in
// directed graph using BFS.
#include <bits/stdc++.h>
using namespace std;
 
// Class to represent a graph
class Graph {
    int V; // No. of vertices'
 
    // Pointer to an array containing adjacency list
    list<int>* adj;
 
public:
    Graph(int V); // Constructor
 
    // function to add an edge to graph
    void addEdge(int u, int v);
 
    // Returns true if there is a cycle in the graph
    // else false.
    bool isCycle();
};
 
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}
 
void Graph::addEdge(int u, int v)
{
    adj[u].push_back(v);
}
 
// This function returns true if there is a cycle
// in directed graph, else returns false.
bool Graph::isCycle()
{
    // Create a vector to store indegrees of all
    // vertices. Initialize all indegrees as 0.
    vector<int> in_degree(V, 0);
 
    // Traverse adjacency lists to fill indegrees of
    // vertices. This step takes O(V+E) time
    for (int u = 0; u < V; u++) {
        for (auto v : adj[u])
            in_degree[v]++;
    }
 
    // Create an queue and enqueue all vertices with
    // indegree 0
    queue<int> q;
    for (int i = 0; i < V; i++)
        if (in_degree[i] == 0)
            q.push(i);
 
    // Initialize count of visited vertices
    // 1 For src Node
    int cnt = 1;
 
    // Create a vector to store result (A topological
    // ordering of the vertices)
    vector<int> top_order;
 
    // One by one dequeue vertices from queue and enqueue
    // adjacents if indegree of adjacent becomes 0
    while (!q.empty()) {
 
        // Extract front of queue (or perform dequeue)
        // and add it to topological order
        int u = q.front();
        q.pop();
        top_order.push_back(u);
 
        // Iterate through all its neighbouring nodes
        // of dequeued node u and decrease their in-degree
        // by 1
        list<int>::iterator itr;
        for (itr = adj[u].begin(); itr != adj[u].end(); itr++)
 
            // If in-degree becomes zero, add it to queue
            if (--in_degree[*itr] == 0)
            {
              q.push(*itr);
              //while we are pushing elements to the queue we will incrementing the cnt
              cnt++;
            }
 
        
    }
 
    // Check if there was a cycle
    if (cnt != V)
        return true;
    else
        return false;
}
 
// Driver program to test above functions
int main()
{
    // Create a graph given in the above diagram
    Graph g(6);
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(3, 4);
    g.addEdge(4, 5);
 
    if (g.isCycle())
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

Java

// Java program to check if there is a cycle in
// directed graph using BFS.
import java.io.*;
import java.util.*;
 
class GFG
{
 
    // Class to represent a graph
    static class Graph
    {
        int V; // No. of vertices'
 
        // Pointer to an array containing adjacency list
        Vector<Integer>[] adj;
 
        @SuppressWarnings("unchecked")
        Graph(int V)
        {
            // Constructor
            this.V = V;
            this.adj = new Vector[V];
            for (int i = 0; i < V; i++)
                adj[i] = new Vector<>();
        }
 
        // function to add an edge to graph
        void addEdge(int u, int v)
        {
            adj[u].add(v);
        }
 
        // Returns true if there is a cycle in the graph
        // else false.
 
        // This function returns true if there is a cycle
        // in directed graph, else returns false.
        boolean isCycle()
        {
 
            // Create a vector to store indegrees of all
            // vertices. Initialize all indegrees as 0.
            int[] in_degree = new int[this.V];
            Arrays.fill(in_degree, 0);
 
            // Traverse adjacency lists to fill indegrees of
            // vertices. This step takes O(V+E) time
            for (int u = 0; u < V; u++)
            {
                for (int v : adj[u])
                    in_degree[v]++;
            }
 
            // Create an queue and enqueue all vertices with
            // indegree 0
            Queue<Integer> q = new LinkedList<Integer>();
            for (int i = 0; i < V; i++)
                if (in_degree[i] == 0)
                    q.add(i);
 
            // Initialize count of visited vertices
            int cnt = 0;
 
            // Create a vector to store result (A topological
            // ordering of the vertices)
            Vector<Integer> top_order = new Vector<>();
 
            // One by one dequeue vertices from queue and enqueue
            // adjacents if indegree of adjacent becomes 0
            while (!q.isEmpty())
            {
 
                // Extract front of queue (or perform dequeue)
                // and add it to topological order
                int u = q.poll();
                top_order.add(u);
 
                // Iterate through all its neighbouring nodes
                // of dequeued node u and decrease their in-degree
                // by 1
                for (int itr : adj[u])
                    if (--in_degree[itr] == 0)
                        q.add(itr);
                cnt++;
            }
 
            // Check if there was a cycle
            if (cnt != this.V)
                return true;
            else
                return false;
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Create a graph given in the above diagram
        Graph g = new Graph(6);
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(3, 4);
        g.addEdge(4, 5);
 
        if (g.isCycle())
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
 
// This code is contributed by
// sanjeev2552

Python3

# A Python3 program to check if there is a cycle in 
# directed graph using BFS.
import math
import sys
from collections import defaultdict
 
# Class to represent a graph
class Graph:
    def __init__(self,vertices):
        self.graph=defaultdict(list)
        self.V=vertices # No. of vertices'
     
    # function to add an edge to graph
    def addEdge(self,u,v):
        self.graph[u].append(v)
 
# This function returns true if there is a cycle
# in directed graph, else returns false.
def isCycleExist(n,graph):
 
    # Create a vector to store indegrees of all
    # vertices. Initialize all indegrees as 0.
    in_degree=[0]*n
 
    # Traverse adjacency lists to fill indegrees of
    # vertices. This step takes O(V+E) time
    for i in range(n):
        for j in graph[i]:
            in_degree[j]+=1
     
    # Create an queue and enqueue all vertices with
    # indegree 0
    queue=[]
    for i in range(len(in_degree)):
        if in_degree[i]==0:
            queue.append(i)
     
    # Initialize count of visited vertices
    cnt=0
 
    # One by one dequeue vertices from queue and enqueue
    # adjacents if indegree of adjacent becomes 0
    while(queue):
 
        # Extract front of queue (or perform dequeue)
        # and add it to topological order
        nu=queue.pop(0)
 
        # Iterate through all its neighbouring nodes
        # of dequeued node u and decrease their in-degree
        # by 1
        for v in graph[nu]:
            in_degree[v]-=1
 
            # If in-degree becomes zero, add it to queue
            if in_degree[v]==0:
                queue.append(v)
        cnt+=1
 
    # Check if there was a cycle
    if cnt==n:
        return False
    else:
        return True
         
 
# Driver program to test above functions
if __name__=='__main__':
 
    # Create a graph given in the above diagram
    g=Graph(6)
    g.addEdge(0,1)
    g.addEdge(1,2)
    g.addEdge(2,0)
    g.addEdge(3,4)
    g.addEdge(4,5)
     
    if isCycleExist(g.V,g.graph):
        print("Yes")
    else:
        print("No")
 
# This Code is Contributed by Vikash Kumar 37

C#

// C# program to check if there is a cycle in
// directed graph using BFS.
using System;
using System.Collections.Generic;
 
class GFG{
     
// Class to represent a graph
public class Graph
{
     
    // No. of vertices'
    public int V;
     
    // Pointer to an array containing
    // adjacency list
    public List<int>[] adj;
     
    public Graph(int V)
    {
         
        // Constructor
        this.V = V;
        this.adj = new List<int>[V];
        for (int i = 0; i < V; i++)
        adj[i] = new List<int>();
    }
     
    // Function to add an edge to graph
    public void addEdge(int u, int v)
    {
        adj[u].Add(v);
    }
     
    // Returns true if there is a cycle in the
    // graph else false.
     
    // This function returns true if there is
    // a cycle in directed graph, else returns
    // false.
    public bool isCycle()
    {
         
        // Create a vector to store indegrees of all
        // vertices. Initialize all indegrees as 0.
        int[] in_degree = new int[this.V];
         
        // Traverse adjacency lists to fill indegrees
        // of vertices. This step takes O(V+E) time
        for(int u = 0; u < V; u++)
        {
            foreach(int v in adj[u])
                in_degree[v]++;
        }
         
        // Create an queue and enqueue all
        // vertices with indegree 0
        Queue<int> q = new Queue<int>();
        for(int i = 0; i < V; i++)
            if (in_degree[i] == 0)
                q.Enqueue(i);
         
        // Initialize count of visited vertices
        int cnt = 0;
         
        // Create a vector to store result
        // (A topological ordering of the
        // vertices)
        List<int> top_order = new List<int>();
         
        // One by one dequeue vertices from
        // queue and enqueue adjacents if
        // indegree of adjacent becomes 0
        while (q.Count != 0)
        {
         
            // Extract front of queue (or perform
            // dequeue) and add it to topological
            // order
            int u = q.Peek();
            q.Dequeue();
            top_order.Add(u);
             
            // Iterate through all its neighbouring
            // nodes of dequeued node u and decrease
            // their in-degree by 1
            foreach(int itr in adj[u])
                if (--in_degree[itr] == 0)
                    q.Enqueue(itr);
                     
            cnt++;
        }
         
        // Check if there was a cycle
        if (cnt != this.V)
            return true;
        else
            return false;
    }
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Create a graph given in the above diagram
    Graph g = new Graph(6);
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(3, 4);
    g.addEdge(4, 5);
 
    if (g.isCycle())
        Console.WriteLine("Yes");
    else
        Console.WriteLine("No");
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
 
// JavaScript program to check if there is a cycle in
// directed graph using BFS.
 
// Class to represent a graph
// No. of vertices'
var V = 0;
 
// Pointer to an array containing
// adjacency list
var adj ;
 
function initialize(v)
{
     
    // Constructor
    V = v;
    adj = Array.from(Array(V), ()=>Array(V));
}
 
// Function to add an edge to graph
function addEdge(u, v)
{
    adj[u].push(v);
}
 
// Returns true if there is a cycle in the
// graph else false.
 
// This function returns true if there is
// a cycle in directed graph, else returns
// false.
function isCycle()
{
     
    // Create a vector to store indegrees of all
    // vertices. Initialize all indegrees as 0.
    var in_degree = Array(V).fill(0);
     
    // Traverse adjacency lists to fill indegrees
    // of vertices. This step takes O(V+E) time
    for(var u = 0; u < V; u++)
    {
        for(var v of adj[u])
            in_degree[v]++;
    }
     
    // Create an queue and enqueue all
    // vertices with indegree 0
    var q = [];
    for(var i = 0; i < V; i++)
        if (in_degree[i] == 0)
            q.push(i);
     
    // Initialize count of visited vertices
    var cnt = 0;
     
    // Create a vector to store result
    // (A topological ordering of the
    // vertices)
    var top_order = [];
     
    // One by one dequeue vertices from
    // queue and enqueue adjacents if
    // indegree of adjacent becomes 0
    while (q.length != 0)
    {
     
        // Extract front of queue (or perform
        // dequeue) and add it to topological
        // order
        var u = q[0];
        q.shift();
        top_order.push(u);
         
        // Iterate through all its neighbouring
        // nodes of dequeued node u and decrease
        // their in-degree by 1
        for(var itr of adj[u])
            if (--in_degree[itr] == 0)
                q.push(itr);
                 
        cnt++;
    }
     
    // Check if there was a cycle
    if (cnt != V)
        return true;
    else
        return false;
}
 
// Create a graph given in the above diagram
initialize(6)
addEdge(0, 1);
addEdge(1, 2);
addEdge(2, 0);
addEdge(3, 4);
addEdge(4, 5);
if (isCycle())
    document.write("Yes");
else
    document.write("No");
 
 
</script>
Producción: 

Yes

 

Complejidad temporal: O(V+E)
 

Publicación traducida automáticamente

Artículo escrito por kartik y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *