Mejor respuesta
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 realizamos 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. ( digamos p1) 2. El orden del ancestro más antiguo que puede alcanzar (digamos p2) Inicialmente ambos son iguales para cada nodo. Mientras que la primera propiedad permanece constante, la segunda puede actualizarse durante llamadas DFS recursivas 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 es parte de ningún ciclo. O 2. Parte de un ciclo y así todos sus descendientes (en el árbol DFS producido) pueden alcanzarlo (no pueden llegar a sus ancestros). En otras palabras, podemos empezar y terminar en este nodo. En el segundo caso, podemos realizar un seguimiento de todos los descendientes para imprimir.
esta animación ayuda a comprender la explicación (el primer número entero es p1, el segundo es p2):
@ Archivo: Algoritmo de animación de Tarjan.gif
Explicación detallada e implementación de C ++: Tarjan «s Algoritmo para encontrar componentes fuertemente conectados – GeeksforGeeks
PD: Este algoritmo es muy similar a encontrar puntos de articulación, puentes y gráficos biconectados. Entonces, aprender estos primero puede ayudarlo a tener una mejor intuición del algoritmo. http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/ http://www.geeksforgeeks.org/bridge-in-a-graph/
Respuesta
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 de salida es 0, o cualquier vértice de un gráfico acíclico.
El La idea básica del algoritmo es la siguiente: una búsqueda en profundidad comienza desde un nodo de inicio arbitrario (y las búsquedas posteriores en profundidad se realizan en cualquier nodo que aún no se haya encontrado). Como es habitual con la búsqueda en profundidad, la búsqueda visita cada nodo del gráfico exactamente una vez y se niega a volver a visitar cualquier nodo que ya haya sido explorado. Por lo tanto, la colección de árboles de búsqueda es un bosque expansivo del 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 puede servir como raíz, si resulta ser el primer nodo del componente que se descubre mediante la búsqueda.