Un grafo dirigido es fuertemente conexo si existe un camino entre todos los pares de vértices. Un componente fuertemente conectado ( SCC ) de un gráfico dirigido es un subgrafo máximo fuertemente conectado. Por ejemplo, hay 3 SCC en el siguiente gráfico.
Hemos discutido el algoritmo de Kosaraju para componentes fuertemente conectados . El algoritmo discutido anteriormente requiere dos recorridos DFS de un gráfico. En esta publicación, se analiza el algoritmo de Tarjan que requiere solo un recorrido DFS.
El algoritmo de Tarjan se basa en los siguientes hechos:
- La búsqueda DFS produce un árbol/bosque DFS
- Los componentes fuertemente conectados forman subárboles del árbol DFS.
- Si podemos encontrar la cabeza de dichos subárboles, podemos imprimir/almacenar todos los Nodes en ese subárbol (incluida la cabeza) y ese será un SCC.
- No hay borde posterior de un SCC a otro (puede haber bordes cruzados, pero no se usarán bordes cruzados mientras se procesa el gráfico).
Para encontrar la cabeza de un SCC, calculamos el disco y la array baja (como se hizo para el punto de articulación , el puente y el componente biconectado ). Como se discutió en las publicaciones anteriores, low[u] indica el vértice visitado más temprano (el vértice con un tiempo de descubrimiento mínimo) al que se puede llegar desde un subárbol enraizado con u. Un Node u es cabeza si disco[u] = bajo[u].
La siguiente imagen es una ilustración del enfoque:
En la figura anterior, hemos mostrado un gráfico y uno del árbol DFS (puede haber diferentes árboles DFS en el mismo gráfico según el orden en que se recorren los bordes).
En un árbol DFS, las flechas continuas son los bordes del árbol y las flechas discontinuas son los bordes posteriores (bordes del árbol DFS )
Los valores Disco y Bajo se muestran en la Figura para cada Node como (Disco/Bajo).
Disco: este es el momento en que se visita un Node por primera vez durante el recorrido DFS. Para los Nodes A, B, C, .. y J en el árbol DFS, los valores de disco son 1, 2, 3, .., 10.
Bajo: en el árbol DFS, los bordes del árbol nos llevan hacia adelante, desde el Node ancestro hasta uno de sus descendientes. Por ejemplo, desde el Node C, las aristas del árbol nos pueden llevar al Node G, al Node I, etc. Las aristas posteriores nos llevan hacia atrás, desde un Node descendiente hasta uno de sus ancestros.
Por ejemplo, desde el Node G, los bordes posteriores nos llevan a E o C. Si observamos el árbol y el borde posterior juntos, podemos ver que si comenzamos el recorrido desde un Node, podemos descender por el árbol a través de los bordes del árbol y luego sube por los bordes traseros. Por ejemplo, desde el Node E, podemos bajar a G y luego subir a C. De manera similar, desde E, podemos bajar a I o J y luego subir a F. El valor «bajo» de un Node indica la parte superior alcanzable antepasado (con el valor de disco mínimo posible) a través del subárbol de ese Node. Entonces, para cualquier Node, un valor bajo es igual a su valor de disco de todos modos (un Node es el antepasado de sí mismo). Luego buscamos en su subárbol y vemos si hay algún Node que pueda llevarnos a alguno de sus ancestros. Si hay varios bordes posteriores en el subárbol que nos llevan a diferentes ancestros, entonces tomamos el que tiene el valor de disco mínimo (es decir, el que está más arriba). Si observamos el Node F, tiene dos subárboles. El subárbol con el Node G nos lleva a E y C. El otro subárbol nos lleva de regreso a F solamente. Aquí, el ancestro más alto es C, donde F puede alcanzar, por lo que el valor bajo de F es 3 (el valor de disco de C).
Según la discusión anterior, debe quedar claro que los valores bajos de B, C y D son 1 (ya que A es el Node superior al que pueden llegar B, C y D). De la misma manera, los valores bajos de E, F y G son 3, y los valores bajos de H, I y J son 6.
Para cualquier Node u, cuando se inicia DFS, Low se establecerá en su Disco 1 .
Luego, más adelante, se realizará DFS en cada uno de sus hijos v uno por uno. El valor bajo de u puede cambiarlo en dos casos:
- Caso 1 (Borde del árbol): si el Node v aún no se ha visitado, luego de que se complete el DFS de v, un mínimo de low[u] y low[v] se actualizará a low[u].
- Caso 2 (Borde posterior): cuando el niño v ya está visitado, entonces un mínimo de low[u] y Disc[v] se actualizarán a low[u].
En el caso dos, . La respuesta es NO . Si puede pensar por qué la respuesta es NO , probablemente entendió el concepto Low and Disc.
Los mismos valores Low y Disc ayudan a resolver otros problemas gráficos como el punto de articulación , el puente y el componente biconectado .
Para rastrear el subárbol enraizado en la cabeza, podemos usar una pila (siga presionando el Node mientras visita). Cuando se encuentra un Node principal, extraiga todos los Nodes de la pila hasta que saque la cabeza de la pila.
Para asegurarnos, no consideramos los bordes cruzados, cuando llegamos a un Node que ya está visitado, debemos procesar el Node visitado solo si está presente en la pila, de lo contrario, ignorar el Node.
A continuación se muestra la implementación del algoritmo de Tarjan para imprimir todos los SCC.
C++
// A C++ program to find strongly connected components in a given
// directed graph using Tarjan's algorithm (single DFS)
#include<iostream>
#include <list>
#include <stack>
#define NIL -1
using namespace std;
// A class that represents an directed graph
class Graph
{
int V; // No. of vertices
list<int> *adj; // A dynamic array of adjacency lists
// A Recursive DFS based function used by SCC()
void SCCUtil(int u, int disc[], int low[],
stack<int> *st, bool stackMember[]);
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // function to add an edge to graph
void SCC(); // prints strongly connected components
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
}
// A recursive function that finds and prints strongly connected
// components using DFS traversal
// u --> The vertex to be visited next
// disc[] --> Stores discovery times of visited vertices
// low[] -- >> earliest visited vertex (the vertex with minimum
// discovery time) that can be reached from subtree
// rooted with current vertex
// *st -- >> To store all the connected ancestors (could be part
// of SCC)
// stackMember[] --> bit/index array for faster check whether
// a node is in stack
void Graph::SCCUtil(int u, int disc[], int low[], stack<int> *st,
bool stackMember[])
{
// A static variable is used for simplicity, we can avoid use
// of static variable by passing a pointer.
static int time = 0;
// Initialize discovery time and low value
disc[u] = low[u] = ++time;
st->push(u);
stackMember[u] = true;
// Go through all vertices adjacent to this
list<int>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
{
int v = *i; // v is current adjacent of 'u'
// If v is not visited yet, then recur for it
if (disc[v] == -1)
{
SCCUtil(v, disc, low, st, stackMember);
// Check if the subtree rooted with 'v' has a
// connection to one of the ancestors of 'u'
// Case 1 (per above discussion on Disc and Low value)
low[u] = min(low[u], low[v]);
}
// Update low value of 'u' only of 'v' is still in stack
// (i.e. it's a back edge, not cross edge).
// Case 2 (per above discussion on Disc and Low value)
else if (stackMember[v] == true)
low[u] = min(low[u], disc[v]);
}
// head node found, pop the stack and print an SCC
int w = 0; // To store stack extracted vertices
if (low[u] == disc[u])
{
while (st->top() != u)
{
w = (int) st->top();
cout << w << " ";
stackMember[w] = false;
st->pop();
}
w = (int) st->top();
cout << w << "\n";
stackMember[w] = false;
st->pop();
}
}
// The function to do DFS traversal. It uses SCCUtil()
void Graph::SCC()
{
int *disc = new int[V];
int *low = new int[V];
bool *stackMember = new bool[V];
stack<int> *st = new stack<int>();
// Initialize disc and low, and stackMember arrays
for (int i = 0; i < V; i++)
{
disc[i] = NIL;
low[i] = NIL;
stackMember[i] = false;
}
// Call the recursive helper function to find strongly
// connected components in DFS tree with vertex 'i'
for (int i = 0; i < V; i++)
if (disc[i] == NIL)
SCCUtil(i, disc, low, st, stackMember);
}
// Driver program to test above function
int main()
{
cout << "\nSCCs in first graph \n";
Graph g1(5);
g1.addEdge(1, 0);
g1.addEdge(0, 2);
g1.addEdge(2, 1);
g1.addEdge(0, 3);
g1.addEdge(3, 4);
g1.SCC();
cout << "\nSCCs in second graph \n";
Graph g2(4);
g2.addEdge(0, 1);
g2.addEdge(1, 2);
g2.addEdge(2, 3);
g2.SCC();
cout << "\nSCCs in third graph \n";
Graph g3(7);
g3.addEdge(0, 1);
g3.addEdge(1, 2);
g3.addEdge(2, 0);
g3.addEdge(1, 3);
g3.addEdge(1, 4);
g3.addEdge(1, 6);
g3.addEdge(3, 5);
g3.addEdge(4, 5);
g3.SCC();
cout << "\nSCCs in fourth graph \n";
Graph g4(11);
g4.addEdge(0,1);g4.addEdge(0,3);
g4.addEdge(1,2);g4.addEdge(1,4);
g4.addEdge(2,0);g4.addEdge(2,6);
g4.addEdge(3,2);
g4.addEdge(4,5);g4.addEdge(4,6);
g4.addEdge(5,6);g4.addEdge(5,7);g4.addEdge(5,8);g4.addEdge(5,9);
g4.addEdge(6,4);
g4.addEdge(7,9);
g4.addEdge(8,9);
g4.addEdge(9,8);
g4.SCC();
cout << "\nSCCs in fifth graph \n";
Graph g5(5);
g5.addEdge(0,1);
g5.addEdge(1,2);
g5.addEdge(2,3);
g5.addEdge(2,4);
g5.addEdge(3,0);
g5.addEdge(4,2);
g5.SCC();
return 0;
}
Java
// Java program to find strongly connected
// components in a given directed graph
// using Tarjan's algorithm (single DFS)
import java.io.*;
import java.util.*;
// This class represents a directed graph
// using adjacency list representation
class Graph{
// No. of vertices
private int V;
//Adjacency Lists
private LinkedList<Integer> adj[];
private int Time;
// Constructor
@SuppressWarnings("unchecked")
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for(int i = 0; i < v; ++i)
adj[i] = new LinkedList();
Time = 0;
}
// Function to add an edge into the graph
void addEdge(int v,int w)
{
adj[v].add(w);
}
// A recursive function that finds and prints strongly
// connected components using DFS traversal
// u --> The vertex to be visited next
// disc[] --> Stores discovery times of visited vertices
// low[] -- >> earliest visited vertex (the vertex with
// minimum discovery time) that can be reached
// from subtree rooted with current vertex
// st -- >> To store all the connected ancestors (could be part
// of SCC)
// stackMember[] --> bit/index array for faster check
// whether a node is in stack
void SCCUtil(int u, int low[], int disc[],
boolean stackMember[],
Stack<Integer> st)
{
// Initialize discovery time and low value
disc[u] = Time;
low[u] = Time;
Time += 1;
stackMember[u] = true;
st.push(u);
int n;
// Go through all vertices adjacent to this
Iterator<Integer> i = adj[u].iterator();
while (i.hasNext())
{
n = i.next();
if (disc[n] == -1)
{
SCCUtil(n, low, disc, stackMember, st);
// Check if the subtree rooted with v
// has a connection to one of the
// ancestors of u
// Case 1 (per above discussion on
// Disc and Low value)
low[u] = Math.min(low[u], low[n]);
}
else if (stackMember[n] == true)
{
// Update low value of 'u' only if 'v' is
// still in stack (i.e. it's a back edge,
// not cross edge).
// Case 2 (per above discussion on Disc
// and Low value)
low[u] = Math.min(low[u], disc[n]);
}
}
// head node found, pop the stack and print an SCC
// To store stack extracted vertices
int w = -1;
if (low[u] == disc[u])
{
while (w != u)
{
w = (int)st.pop();
System.out.print(w + " ");
stackMember[w] = false;
}
System.out.println();
}
}
// The function to do DFS traversal.
// It uses SCCUtil()
void SCC()
{
// Mark all the vertices as not visited
// and Initialize parent and visited,
// and ap(articulation point) arrays
int disc[] = new int[V];
int low[] = new int[V];
for(int i = 0;i < V; i++)
{
disc[i] = -1;
low[i] = -1;
}
boolean stackMember[] = new boolean[V];
Stack<Integer> st = new Stack<Integer>();
// Call the recursive helper function
// to find articulation points
// in DFS tree rooted with vertex 'i'
for(int i = 0; i < V; i++)
{
if (disc[i] == -1)
SCCUtil(i, low, disc,
stackMember, st);
}
}
// Driver code
public static void main(String args[])
{
// Create a graph given in the above diagram
Graph g1 = new Graph(5);
g1.addEdge(1, 0);
g1.addEdge(0, 2);
g1.addEdge(2, 1);
g1.addEdge(0, 3);
g1.addEdge(3, 4);
System.out.println("SSC in first graph ");
g1.SCC();
Graph g2 = new Graph(4);
g2.addEdge(0, 1);
g2.addEdge(1, 2);
g2.addEdge(2, 3);
System.out.println("\nSSC in second graph ");
g2.SCC();
Graph g3 = new Graph(7);
g3.addEdge(0, 1);
g3.addEdge(1, 2);
g3.addEdge(2, 0);
g3.addEdge(1, 3);
g3.addEdge(1, 4);
g3.addEdge(1, 6);
g3.addEdge(3, 5);
g3.addEdge(4, 5);
System.out.println("\nSSC in third graph ");
g3.SCC();
Graph g4 = new Graph(11);
g4.addEdge(0, 1);
g4.addEdge(0, 3);
g4.addEdge(1, 2);
g4.addEdge(1, 4);
g4.addEdge(2, 0);
g4.addEdge(2, 6);
g4.addEdge(3, 2);
g4.addEdge(4, 5);
g4.addEdge(4, 6);
g4.addEdge(5, 6);
g4.addEdge(5, 7);
g4.addEdge(5, 8);
g4.addEdge(5, 9);
g4.addEdge(6, 4);
g4.addEdge(7, 9);
g4.addEdge(8, 9);
g4.addEdge(9, 8);
System.out.println("\nSSC in fourth graph ");
g4.SCC();
Graph g5 = new Graph (5);
g5.addEdge(0, 1);
g5.addEdge(1, 2);
g5.addEdge(2, 3);
g5.addEdge(2, 4);
g5.addEdge(3, 0);
g5.addEdge(4, 2);
System.out.println("\nSSC in fifth graph ");
g5.SCC();
}
}
// This code is contributed by
// Prateek Gupta (@prateekgupta10)
Python3
# Python program to find strongly connected components in a given
# directed graph using Tarjan's algorithm (single DFS)
#Complexity : O(V+E)
from collections import defaultdict
#This class represents an directed graph
# using adjacency list representation
class Graph:
def __init__(self,vertices):
#No. of vertices
self.V= vertices
# default dictionary to store graph
self.graph = defaultdict(list)
self.Time = 0
# function to add an edge to graph
def addEdge(self,u,v):
self.graph[u].append(v)
'''A recursive function that find finds and prints strongly connected
components using DFS traversal
u --> The vertex to be visited next
disc[] --> Stores discovery times of visited vertices
low[] -- >> earliest visited vertex (the vertex with minimum
discovery time) that can be reached from subtree
rooted with current vertex
st -- >> To store all the connected ancestors (could be part
of SCC)
stackMember[] --> bit/index array for faster check whether
a node is in stack
'''
def SCCUtil(self,u, low, disc, stackMember, st):
# Initialize discovery time and low value
disc[u] = self.Time
low[u] = self.Time
self.Time += 1
stackMember[u] = True
st.append(u)
# Go through all vertices adjacent to this
for v in self.graph[u]:
# If v is not visited yet, then recur for it
if disc[v] == -1 :
self.SCCUtil(v, low, disc, stackMember, st)
# Check if the subtree rooted with v has a connection to
# one of the ancestors of u
# Case 1 (per above discussion on Disc and Low value)
low[u] = min(low[u], low[v])
elif stackMember[v] == True:
'''Update low value of 'u' only if 'v' is still in stack
(i.e. it's a back edge, not cross edge).
Case 2 (per above discussion on Disc and Low value) '''
low[u] = min(low[u], disc[v])
# head node found, pop the stack and print an SCC
w = -1 #To store stack extracted vertices
if low[u] == disc[u]:
while w != u:
w = st.pop()
print (w, end=" ")
stackMember[w] = False
print()
#The function to do DFS traversal.
# It uses recursive SCCUtil()
def SCC(self):
# Mark all the vertices as not visited
# and Initialize parent and visited,
# and ap(articulation point) arrays
disc = [-1] * (self.V)
low = [-1] * (self.V)
stackMember = [False] * (self.V)
st =[]
# Call the recursive helper function
# to find articulation points
# in DFS tree rooted with vertex 'i'
for i in range(self.V):
if disc[i] == -1:
self.SCCUtil(i, low, disc, stackMember, st)
# Create a graph given in the above diagram
g1 = Graph(5)
g1.addEdge(1, 0)
g1.addEdge(0, 2)
g1.addEdge(2, 1)
g1.addEdge(0, 3)
g1.addEdge(3, 4)
print ("SSC in first graph ")
g1.SCC()
g2 = Graph(4)
g2.addEdge(0, 1)
g2.addEdge(1, 2)
g2.addEdge(2, 3)
print ("nSSC in second graph ")
g2.SCC()
g3 = Graph(7)
g3.addEdge(0, 1)
g3.addEdge(1, 2)
g3.addEdge(2, 0)
g3.addEdge(1, 3)
g3.addEdge(1, 4)
g3.addEdge(1, 6)
g3.addEdge(3, 5)
g3.addEdge(4, 5)
print ("nSSC in third graph ")
g3.SCC()
g4 = Graph(11)
g4.addEdge(0, 1)
g4.addEdge(0, 3)
g4.addEdge(1, 2)
g4.addEdge(1, 4)
g4.addEdge(2, 0)
g4.addEdge(2, 6)
g4.addEdge(3, 2)
g4.addEdge(4, 5)
g4.addEdge(4, 6)
g4.addEdge(5, 6)
g4.addEdge(5, 7)
g4.addEdge(5, 8)
g4.addEdge(5, 9)
g4.addEdge(6, 4)
g4.addEdge(7, 9)
g4.addEdge(8, 9)
g4.addEdge(9, 8)
print ("nSSC in fourth graph ")
g4.SCC();
g5 = Graph (5)
g5.addEdge(0, 1)
g5.addEdge(1, 2)
g5.addEdge(2, 3)
g5.addEdge(2, 4)
g5.addEdge(3, 0)
g5.addEdge(4, 2)
print ("nSSC in fifth graph ")
g5.SCC();
#This code is contributed by Neelam Yadav
Javascript
<script>
// Javascript program to find strongly connected
// components in a given directed graph
// using Tarjan's algorithm (single DFS)
// 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] = [];
this.Time = 0;
}
// Function to add an edge into the graph
addEdge(v, w)
{
this.adj[v].push(w);
}
// A recursive function that finds and prints strongly
// connected components using DFS traversal
// u --> The vertex to be visited next
// disc[] --> Stores discovery times of visited vertices
// low[] -- >> earliest visited vertex (the vertex with
// minimum discovery time) that can be reached
// from subtree rooted with current vertex
// st -- >> To store all the connected ancestors (could be
// part of SCC)
// stackMember[] --> bit/index array for faster check
// whether a node is in stack
SCCUtil(u, low, disc, stackMember, st)
{
// Initialize discovery time and low value
disc[u] = this.Time;
low[u] = this.Time;
this.Time += 1;
stackMember[u] = true;
st.push(u);
let n;
// Go through all vertices adjacent to this
for(let i of this.adj[u])
{
n = i;
if (disc[n] == -1)
{
this.SCCUtil(n, low, disc, stackMember, st);
// Check if the subtree rooted with v
// has a connection to one of the
// ancestors of u
// Case 1 (per above discussion on
// Disc and Low value)
low[u] = Math.min(low[u], low[n]);
}
else if (stackMember[n] == true)
{
// Update low value of 'u' only if 'v' is
// still in stack (i.e. it's a back edge,
// not cross edge).
// Case 2 (per above discussion on Disc
// and Low value)
low[u] = Math.min(low[u], disc[n]);
}
}
// Head node found, pop the stack and print an SCC
// To store stack extracted vertices
let w = -1;
if (low[u] == disc[u])
{
while (w != u)
{
w = st.pop();
document.write(w + " ");
stackMember[w] = false;
}
document.write("<br>");
}
}
// The function to do DFS traversal.
// It uses SCCUtil()
SCC()
{
// Mark all the vertices as not visited
// and Initialize parent and visited,
// and ap(articulation point) arrays
let disc = new Array(this.V);
let low = new Array(this.V);
for(let i = 0;i < this.V; i++)
{
disc[i] = -1;
low[i] = -1;
}
let stackMember = new Array(this.V);
let st = [];
// Call the recursive helper function
// to find articulation points
// in DFS tree rooted with vertex 'i'
for(let i = 0; i < this.V; i++)
{
if (disc[i] == -1)
this.SCCUtil(i, low, disc,
stackMember, st);
}
}
}
// Driver code
// Create a graph given in the above diagram
let g1 = new Graph(5);
g1.addEdge(1, 0);
g1.addEdge(0, 2);
g1.addEdge(2, 1);
g1.addEdge(0, 3);
g1.addEdge(3, 4);
document.write("SSC in first graph <br>");
g1.SCC();
let g2 = new Graph(4);
g2.addEdge(0, 1);
g2.addEdge(1, 2);
g2.addEdge(2, 3);
document.write("\nSSC in second graph<br> ");
g2.SCC();
let g3 = new Graph(7);
g3.addEdge(0, 1);
g3.addEdge(1, 2);
g3.addEdge(2, 0);
g3.addEdge(1, 3);
g3.addEdge(1, 4);
g3.addEdge(1, 6);
g3.addEdge(3, 5);
g3.addEdge(4, 5);
document.write("\nSSC in third graph <br>");
g3.SCC();
let g4 = new Graph(11);
g4.addEdge(0, 1);
g4.addEdge(0, 3);
g4.addEdge(1, 2);
g4.addEdge(1, 4);
g4.addEdge(2, 0);
g4.addEdge(2, 6);
g4.addEdge(3, 2);
g4.addEdge(4, 5);
g4.addEdge(4, 6);
g4.addEdge(5, 6);
g4.addEdge(5, 7);
g4.addEdge(5, 8);
g4.addEdge(5, 9);
g4.addEdge(6, 4);
g4.addEdge(7, 9);
g4.addEdge(8, 9);
g4.addEdge(9, 8);
document.write("\nSSC in fourth graph<br> ");
g4.SCC();
let g5 = new Graph (5);
g5.addEdge(0, 1);
g5.addEdge(1, 2);
g5.addEdge(2, 3);
g5.addEdge(2, 4);
g5.addEdge(3, 0);
g5.addEdge(4, 2);
document.write("\nSSC in fifth graph <br>");
g5.SCC();
// This code is contributed by avanitrachhadiya2155
</script>
SCCs in first graph 4 3 1 2 0 SCCs in second graph 3 2 1 0 SCCs in third graph 5 3 4 6 2 1 0 SCCs in fourth graph 8 9 7 5 4 6 3 2 1 0 10 SCCs in fifth graph 4 3 2 1 0
Complejidad de tiempo: el algoritmo anterior llama principalmente a DFS, DFS toma O (V + E) para un gráfico representado mediante una lista de adyacencia.
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