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.
- Incremente el recuento de Nodes visitados en 1.
- Disminuya el grado en 1 para todos sus Nodes vecinos.
- 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)