¿Cuál es una buena explicación para el algoritmo de componentes fuertemente conectados de Tarjan?

Answer 1

Un componente fuertemente conectado (SCC) en un gráfico dirigido es un ciclo o un vértice individual.

Aplicamos DFS en el gráfico y hacemos un seguimiento de dos propiedades para cada nodo en el árbol DFS producido:
1. Su tiempo (u orden) de ser descubierto por primera vez en DFS (por ejemplo, p1)
2. El orden del ancestro más antiguo que puede alcanzar (por ejemplo, p2)
Inicialmente, ambos son iguales para cada nodo.
Mientras que la primera propiedad permanece constante, la segunda puede actualizarse durante las llamadas recursivas DFS y usarse para encontrar bordes posteriores a los antepasados.
Para cualquier vértice si ambos son iguales después de llamadas DFS recursivas a todos sus vértices adyacentes, entonces es
1. Un vértice individual que no forma parte de ningún ciclo.
O
2. Parte de un ciclo y, por lo tanto, todo su descendiente (en el árbol DFS producido) puede alcanzarlo (no puede llegar a sus antepasados). En otras palabras, podemos comenzar y terminar en este nodo.
En el segundo caso, podemos hacer un seguimiento de todos los descendientes para imprimir.

esta animación ayuda a entender la explicación
(el primer entero es p1, el segundo es p2):

@File: Animación del algoritmo de Tarjan.gif

Explicación detallada e implementación de c ++:
El algoritmo de Tarjan para encontrar componentes fuertemente conectados – GeeksforGeeks

PD: este algoritmo es muy similar a encontrar puntos de articulación, puentes y gráficos biconéctados. Entonces, aprender esto primero puede ayudarlo a obtener una mejor intuición para el algoritmo.
http://www.geeksforgeeks.org/art…
http://www.geeksforgeeks.org/bri…

Answer 2

El algoritmo toma un gráfico dirigido como entrada y produce una partición de los vértices del gráfico en los componentes fuertemente conectados del gráfico. Cada vértice del gráfico aparece exactamente en uno de los componentes fuertemente conectados. Cualquier vértice que no esté en un ciclo dirigido forma un componente fuertemente conectado por sí mismo: por ejemplo, un vértice cuyo grado de entrada o salida es 0, o cualquier vértice de un gráfico acíclico.

La idea básica del algoritmo es esta: una búsqueda de profundidad primero comienza desde un nodo de inicio arbitrario (y las búsquedas de profundidad primero posteriores se realizan en cualquier nodo que aún no se haya encontrado). Como es habitual con la búsqueda de profundidad primero, la búsqueda visita cada nodo del gráfico exactamente una vez, y rechaza volver a visitar cualquier nodo que ya haya sido explorado. Por lo tanto, la colección de árboles de búsqueda es un bosque que abarca el gráfico. Los componentes fuertemente conectados se recuperarán como ciertos subárboles de este bosque. Las raíces de estos subárboles se denominan “raíces” de los componentes fuertemente conectados. Cualquier nodo de un componente fuertemente conectado podría servir como raíz, si resulta ser el primer nodo del componente descubierto por la búsqueda.

Algoritmo de componentes fuertemente conectados de Tarjan