En teoría de grafos , los componentes fuertemente conectados de un gráfico dirigido se pueden encontrar usando un algoritmo que utiliza búsqueda en profundidad en combinación con dos pilas , una para realizar un seguimiento de los vértices en el componente actual y la segunda para realizar un seguimiento del componente actual. ruta de búsqueda. [1] Purdom (1970), Munro (1971), Dijkstra (1976), Cheriyan & Mehlhorn (1996) y Gabow (2000) han propuesto versiones de este algoritmo; De estos, la versión de Dijkstra fue la primera en lograr el tiempo lineal . [2]
El algoritmo realiza una búsqueda en profundidad del gráfico dado G , manteniendo al mismo tiempo dos pilas S y P (además de la pila de llamadas normal para una función recursiva). La pila S contiene todos los vértices que aún no se han asignado a un componente fuertemente conectado, en el orden en que la búsqueda en profundidad llega a los vértices. La pila P contiene vértices que aún no se ha determinado que pertenezcan a componentes fuertemente conectados entre sí. También utiliza un contador C del número de vértices alcanzados hasta el momento, que utiliza para calcular los números de preorden de los vértices.
Cuando la búsqueda en profundidad alcanza un vértice v , el algoritmo realiza los siguientes pasos:
El algoritmo general consiste en un bucle a través de los vértices del gráfico, llamando a esta búsqueda recursiva en cada vértice que aún no tiene asignado un número de preorden.
Al igual que este algoritmo, el algoritmo de componentes fuertemente conectados de Tarjan también utiliza la búsqueda en profundidad junto con una pila para realizar un seguimiento de los vértices que aún no se han asignado a un componente, y mueve estos vértices a un nuevo componente cuando termina de expandir el vértice final de su componente. Sin embargo, en lugar de la pila P , el algoritmo de Tarjan utiliza una matriz indexada por vértices de números de preorden, asignados en el orden en que se visitan por primera vez los vértices en la búsqueda en profundidad . La matriz de pedido anticipado se utiliza para realizar un seguimiento de cuándo formar un nuevo componente.