Algoritmo de componentes fuertes basado en rutas

Algoritmo gráfico

En teoría de grafos , los componentes fuertemente conectados de un grafo dirigido pueden encontrarse utilizando un algoritmo que utiliza la 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 de la ruta de búsqueda actual. ^[1] Purdom (1970), Munro (1971), Dijkstra (1976), Cheriyan & Mehlhorn (1996) y Gabow (2000) propusieron versiones de este algoritmo; de estas, la versión de Dijkstra fue la primera en lograr un tiempo lineal . ^[2]

Descripción

El algoritmo realiza una búsqueda en profundidad del grafo dado G , manteniendo 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 diferentes 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:

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 hasta un vértice vecino w :
   • Si el número de preorden de w aún no ha sido asignado (el borde es un borde de árbol ), busque w recursivamente ;
   • De lo contrario, si w aún no se ha asignado a un componente fuertemente conectado (el borde es un borde delantero/trasero/transversal):
     • Haga estallar repetidamente los 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 :
   • Eliminar los vértices desde S hasta v y asignar los vértices eliminados a un nuevo componente.
   • Pop v de P.​

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 tenga un número de preorden asignado.

Algoritmos relacionados

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 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 los vértices se visitan por primera vez en la búsqueda en profundidad . La matriz de preorden se utiliza para realizar un seguimiento de cuándo formar un nuevo componente.

Notas

1. Sedgewick (2004).
2. Historia del DFS basado en rutas para componentes fuertes, Harold N. Gabow, consultado el 24 de abril de 2012.

Referencias

• Cheriyan, J.; Mehlhorn, K. (1996), "Algoritmos para gráficos densos y redes 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 , Nueva Jersey: Prentice Hall, cap. 25.
• Gabow, Harold N. (2000), "Búsqueda en profundidad basada en rutas para componentes fuertes y biconectados" (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 dígrafos", Algoritmos en Java, Parte 5 – Algoritmos de grafos (3.ª ed.), Cambridge MA: Addison-Wesley, págs. 205–216.