Algoritmo de componentes fuertes basado en rutas

En teoría de grafos , los componentes fuertemente conectados de un grafo dirigido pueden encontrarse utilizando un algoritmo que emplea una búsqueda en profundidad combinada con dos pilas : una para mantener un registro de los vértices del componente actual y otra para mantener un registro de la ruta de búsqueda actual. ^{[ 1 ]} Purdom (1970) , Munro (1971) , Dijkstra (1976) , Cheriyan y Mehlhorn (1996) y Gabow (2000) propusieron versiones de este algoritmo ; de estas, la versión de Dijkstra fue la primera en alcanzar un tiempo lineal . ^{[ 2 ]}

El algoritmo realiza una búsqueda en profundidad del grafo G dado , manteniendo dos pilas S y P (además de la pila de llamadas habitual para una función recursiva). La pila S contiene todos los vértices que aún no se han asignado a un componente fuertemente conexo, en el orden en que la búsqueda en profundidad los alcanza. La pila P contiene los vértices que aún no se han determinado como pertenecientes a componentes fuertemente conexos diferentes entre sí. También utiliza un contador C del número de vértices alcanzados hasta el momento, que emplea 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:

1. Establezca el número de preorden de v en C , e incremente C.
2. Empuja v sobre S y también sobre P.
3. Para cada arista desde v a un vértice vecino w :
   • Si aún no se ha asignado el número de preorden de w (la arista es una arista de árbol ), busque w recursivamente ;
   • De lo contrario, si w aún no se ha asignado a un componente fuertemente conectado (la arista es una arista hacia adelante/atrás/cruzada):
     • Extraiga repetidamente vértices de P hasta que el elemento superior de P tenga un número de preorden menor o igual al número de preorden de w .
4. Si v es el elemento superior de P :
   • Extrae vértices de S hasta que se haya extraído vértices , y asigna los vértices extraídos a un nuevo componente.
   • Pop v de P.​

El algoritmo general consiste en un bucle que recorre los vértices del grafo, realizando una búsqueda recursiva en cada vértice al que aún no se le ha asignado un número de preorden.

Al igual que este algoritmo, el algoritmo de componentes fuertemente conectados de Tarjan también utiliza una búsqueda en profundidad junto con una pila para llevar un registro 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 último vértice de su componente. Sin embargo, en lugar de la pila P , el algoritmo de Tarjan utiliza una matriz de números de preorden indexada por vértice , asignada en el orden en que los vértices se visitan por primera vez en la búsqueda en profundidad . La matriz de preorden se utiliza para llevar un registro de cuándo formar un nuevo componente.

• Cheriyan, J.; Mehlhorn, K. (1996), "Algoritmos para grafos y redes densas en la computadora de acceso aleatorio", Algorithmica , 15 (6): 521– 549, doi : 10.1007/BF01940880 , S2CID 8930091 .
• Dijkstra, Edsger (1976), Una disciplina de programación , NJ: Prentice Hall, Cap.  25.
• Gabow, Harold N. (2000), "Búsqueda en profundidad basada en rutas para componentes fuertes y biconectadas" (PDF) , Information Processing Letters , 74 ( 3–4 ): 107–114 , doi : 10.1016/S0020-0190(00)00051-X , MR 1761551 .
• Munro, Ian (1971), "Determinación eficiente del cierre transitivo de un grafo dirigido", Information Processing Letters , 1 (2): 56– 58, doi : 10.1016/0020-0190(71)90006-8.
• Purdom, P. Jr. (1970), "Un algoritmo de cierre transitivo" , BIT , 10 : 76–94 , doi : 10.1007/bf01940892 , S2CID 20818200 .
• Sedgewick, R. (2004), "19.8 Componentes fuertes en digrafos", Algoritmos en Java, Parte 5 – Algoritmos de grafos (3.ª  ed.), Cambridge, MA: Addison-Wesley, págs . 205–216 .