Dada una gráfica dirigida, averigüe si la gráfica es fuertemente conexa o no. Un grafo dirigido es fuertemente conexo si hay un camino entre dos pares cualesquiera de vértices. Por ejemplo, el siguiente es un gráfico fuertemente conectado.
Es fácil para gráficos no dirigidos , solo podemos hacer un BFS y DFS comenzando desde cualquier vértice. Si BFS o DFS visita todos los vértices, entonces el gráfico no dirigido dado está conectado. Este enfoque no funcionará para un gráfico dirigido. Por ejemplo, considere el siguiente gráfico que no está fuertemente conectado. Si comenzamos DFS (o BFS) desde el vértice 0, podemos llegar a todos los vértices, pero si comenzamos desde cualquier otro vértice, no podemos llegar a todos los vértices.
¿Cómo hacer para el gráfico dirigido?
Una idea simple es usar un algoritmo de ruta más corta de todos los pares como Floyd Warshall o encontrar el cierre transitivo del gráfico. La complejidad temporal de este método sería O(v 3 ).
También podemos hacer tiempos DFS V comenzando desde cada vértice. Si algún DFS no visita todos los vértices, entonces el gráfico no está fuertemente conectado. Este algoritmo toma el tiempo O(V*(V+E)) que puede ser el mismo que el cierre transitivo para un gráfico denso.
Una mejor idea puede ser el algoritmo de componentes fuertemente conectados (SCC) . Podemos encontrar todos los SCC en tiempo O(V+E). Si el número de SCC es uno, entonces el gráfico está fuertemente conectado. El algoritmo para SCC realiza un trabajo adicional ya que encuentra todos los SCC.
El siguiente es el algoritmo simple basado en DFS de Kosaraju que realiza dos recorridos de gráfico DFS:
- Inicializar todos los vértices como no visitados.
- Realice un recorrido DFS del gráfico a partir de cualquier vértice arbitrario v. Si el recorrido DFS no visita todos los vértices, devuelva falso.
- Invierta todos los arcos (o encuentre la transposición o el reverso del gráfico)
- Marque todos los vértices como no visitados en el gráfico invertido.
- Realice un recorrido DFS del gráfico invertido a partir del mismo vértice v (igual que el paso 2). Si el recorrido DFS no visita todos los vértices, devuelve falso. De lo contrario, devuelve verdadero.
La idea es que si se puede llegar a cada Node desde un vértice v, y cada Node puede llegar a v, entonces el grafo está fuertemente conectado. En el paso 2, verificamos si todos los vértices son accesibles desde v. En el paso 4, verificamos si todos los vértices pueden alcanzar v (en el gráfico invertido, si todos los vértices son accesibles desde v, entonces todos los vértices pueden alcanzar v en el gráfico original).
A continuación se muestra la implementación del algoritmo anterior.
Implementación:
C++
// C++ program to check if a given directed
// graph is strongly connected or not
#include <iostream>
#include <list>
#include <stack>
using namespace std;
class Graph
{
int V; // No. of vertices
list<int> *adj; // An array of adjacency lists
// A recursive function to print DFS
// starting from v
void DFSUtil(int v, bool visited[]);
public:
// Constructor and Destructor
Graph(int V) { this->V = V; adj = new list<int>[V];}
~Graph() { delete [] adj; }
// Method to add an edge
void addEdge(int v, int w);
// The main function that returns true if the
// graph is strongly connected, otherwise false
bool isSC();
// Function that returns reverse (or transpose)
// of this graph
Graph getTranspose();
};
// A recursive function to print DFS starting from v
void Graph::DFSUtil(int v, bool visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
// Function that returns reverse (or transpose) of this graph
Graph Graph::getTranspose()
{
Graph g(V);
for (int v = 0; v < V; v++)
{
// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
{
g.adj[*i].push_back(v);
}
}
return g;
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
// The main function that returns true if graph
// is strongly connected
bool Graph::isSC()
{
// St1p 1: Mark all the vertices as not visited
// (For first DFS)
bool visited[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// Step 2: Do DFS traversal starting from first vertex.
DFSUtil(0, visited);
// If DFS traversal doesn’t visit all vertices,
// then return false.
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
// Step 3: Create a reversed graph
Graph gr = getTranspose();
// Step 4: Mark all the vertices as not visited
// (For second DFS)
for(int i = 0; i < V; i++)
visited[i] = false;
// Step 5: Do DFS for reversed graph starting from
// first vertex. Starting Vertex must be same starting
// point of first DFS
gr.DFSUtil(0, visited);
// If all vertices are not visited in second DFS, then
// return false
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
return true;
}
// Driver program to test above functions
int main()
{
// Create graphs given in the above diagrams
Graph g1(5);
g1.addEdge(0, 1);
g1.addEdge(1, 2);
g1.addEdge(2, 3);
g1.addEdge(3, 0);
g1.addEdge(2, 4);
g1.addEdge(4, 2);
g1.isSC()? cout << "Yes\n" : cout << "No\n";
Graph g2(4);
g2.addEdge(0, 1);
g2.addEdge(1, 2);
g2.addEdge(2, 3);
g2.isSC()? cout << "Yes\n" : cout << "No\n";
return 0;
}
Java
// Java program to check if a given directed graph is strongly
// connected or not
import java.io.*;
import java.util.*;
import java.util.LinkedList;
// This class represents a directed graph using adjacency
// list representation
class Graph
{
private int V; // No. of vertices
private LinkedList<Integer> adj[]; //Adjacency List
//Constructor
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
//Function to add an edge into the graph
void addEdge(int v,int w) { adj[v].add(w); }
// A recursive function to print DFS starting from v
void DFSUtil(int v,Boolean visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
int n;
// Recur for all the vertices adjacent to this vertex
Iterator<Integer> i = adj[v].iterator();
while (i.hasNext())
{
n = i.next();
if (!visited[n])
DFSUtil(n,visited);
}
}
// Function that returns transpose of this graph
Graph getTranspose()
{
Graph g = new Graph(V);
for (int v = 0; v < V; v++)
{
// Recur for all the vertices adjacent to this vertex
Iterator<Integer> i = adj[v].listIterator();
while (i.hasNext())
g.adj[i.next()].add(v);
}
return g;
}
// The main function that returns true if graph is strongly
// connected
Boolean isSC()
{
// Step 1: Mark all the vertices as not visited
// (For first DFS)
Boolean visited[] = new Boolean[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// Step 2: Do DFS traversal starting from first vertex.
DFSUtil(0, visited);
// If DFS traversal doesn't visit all vertices, then
// return false.
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
// Step 3: Create a reversed graph
Graph gr = getTranspose();
// Step 4: Mark all the vertices as not visited (For
// second DFS)
for (int i = 0; i < V; i++)
visited[i] = false;
// Step 5: Do DFS for reversed graph starting from
// first vertex. Starting Vertex must be same starting
// point of first DFS
gr.DFSUtil(0, visited);
// If all vertices are not visited in second DFS, then
// return false
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
return true;
}
public static void main(String args[])
{
// Create graphs given in the above diagrams
Graph g1 = new Graph(5);
g1.addEdge(0, 1);
g1.addEdge(1, 2);
g1.addEdge(2, 3);
g1.addEdge(3, 0);
g1.addEdge(2, 4);
g1.addEdge(4, 2);
if (g1.isSC())
System.out.println("Yes");
else
System.out.println("No");
Graph g2 = new Graph(4);
g2.addEdge(0, 1);
g2.addEdge(1, 2);
g2.addEdge(2, 3);
if (g2.isSC())
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Aakash Hasija
Python3
# Python program to check if a given directed graph is strongly
# connected or not
from collections import defaultdict
# This class represents a directed graph using adjacency list representation
class Graph:
def __init__(self, vertices):
self.V = vertices # No. of vertices
self.graph = defaultdict(list) # default dictionary to store graph
# function to add an edge to graph
def addEdge(self, u, v):
self.graph[u].append(v)
# A function used by isSC() to perform DFS
def DFSUtil(self, v, visited):
# Mark the current node as visited
visited[v] = True
# Recur for all the vertices adjacent to this vertex
for i in self.graph[v]:
if visited[i] == False:
self.DFSUtil(i, visited)
# Function that returns reverse (or transpose) of this graph
def getTranspose(self):
g = Graph(self.V)
# Recur for all the vertices adjacent to this vertex
for i in self.graph:
for j in self.graph[i]:
g.addEdge(j, i)
return g
# The main function that returns true if graph is strongly connected
def isSC(self):
# Step 1: Mark all the vertices as not visited (For first DFS)
visited =[False]*(self.V)
# Step 2: Do DFS traversal starting from first vertex.
self.DFSUtil(0,visited)
# If DFS traversal doesnt visit all vertices, then return false
if any(i == False for i in visited):
return False
# Step 3: Create a reversed graph
gr = self.getTranspose()
# Step 4: Mark all the vertices as not visited (For second DFS)
visited =[False]*(self.V)
# Step 5: Do DFS for reversed graph starting from first vertex.
# Starting Vertex must be same starting point of first DFS
gr.DFSUtil(0,visited)
# If all vertices are not visited in second DFS, then
# return false
if any(i == False for i in visited):
return False
return True
# Create a graph given in the above diagram
g1 = Graph(5)
g1.addEdge(0, 1)
g1.addEdge(1, 2)
g1.addEdge(2, 3)
g1.addEdge(3, 0)
g1.addEdge(2, 4)
g1.addEdge(4, 2)
print ("Yes" if g1.isSC() else "No")
g2 = Graph(4)
g2.addEdge(0, 1)
g2.addEdge(1, 2)
g2.addEdge(2, 3)
print ("Yes" if g2.isSC() else "No")
# This code is contributed by Neelam Yadav
Javascript
<script>
// Javascript program to check if a given directed graph is strongly
// connected or not
// This class represents a directed graph using adjacency
// list representation
class Graph
{
// Constructor
constructor(v)
{
this.V = v;
this.adj = new Array(v);
for (let i = 0; i < v; ++i)
this.adj[i] = [];
}
// Function to add an edge into the graph
addEdge(v,w)
{
this.adj[v].push(w);
}
// A recursive function to print DFS starting from v
DFSUtil(v,visited)
{
// Mark the current node as visited and print it
visited[v] = true;
let n;
// Recur for all the vertices adjacent to this vertex
for(let i of this.adj[v].values())
{
n = i;
if (!visited[n])
this.DFSUtil(n,visited);
}
}
// Function that returns transpose of this graph
getTranspose()
{
let g = new Graph(this.V);
for (let v = 0; v < this.V; v++)
{
// Recur for all the vertices adjacent to this vertex
for(let i of this.adj[v].values())
g.adj[i].push(v);
}
return g;
}
// The main function that returns true if graph is strongly
// connected
isSC()
{
// Step 1: Mark all the vertices as not visited
// (For first DFS)
let visited = new Array(this.V);
for (let i = 0; i < this.V; i++)
visited[i] = false;
// Step 2: Do DFS traversal starting from first vertex.
this.DFSUtil(0, visited);
// If DFS traversal doesn't visit all vertices, then
// return false.
for (let i = 0; i < this.V; i++)
if (visited[i] == false)
return false;
// Step 3: Create a reversed graph
let gr = this.getTranspose();
// Step 4: Mark all the vertices as not visited (For
// second DFS)
for (let i = 0; i < this.V; i++)
visited[i] = false;
// Step 5: Do DFS for reversed graph starting from
// first vertex. Starting Vertex must be same starting
// point of first DFS
gr.DFSUtil(0, visited);
// If all vertices are not visited in second DFS, then
// return false
for (let i = 0; i < this.V; i++)
if (visited[i] == false)
return false;
return true;
}
}
// Create graphs given in the above diagrams
let g1 = new Graph(5);
g1.addEdge(0, 1);
g1.addEdge(1, 2);
g1.addEdge(2, 3);
g1.addEdge(3, 0);
g1.addEdge(2, 4);
g1.addEdge(4, 2);
if (g1.isSC())
document.write("Yes<br>");
else
document.write("No<br>");
let g2 = new Graph(4);
g2.addEdge(0, 1);
g2.addEdge(1, 2);
g2.addEdge(2, 3);
if (g2.isSC())
document.write("Yes");
else
document.write("No");
// This code is contributed by avanitrachhadiya2155
</script>
Yes No
Complejidad de tiempo: la complejidad de tiempo de la implementación anterior es la misma que la búsqueda en profundidad primero , que es O (V + E) si el gráfico se representa mediante una representación de lista de adyacencia.
¿Podemos mejorar más?
El enfoque anterior requiere dos recorridos del gráfico. Podemos encontrar si un gráfico está fuertemente conectado o no en un recorrido utilizando el algoritmo de Tarjan para encontrar componentes fuertemente conectados .
Ejercicio:
¿Podemos usar BFS en lugar de DFS en el algoritmo anterior? Mira esto .
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA