En la teoría de grafos , los componentes fuertemente conectados de un grafo dirigido se pueden encontrar usando un algoritmo que usa 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 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 un tiempo lineal . [2]
Descripción
El algoritmo realiza una búsqueda en profundidad del gráfico G dado , 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 alcanza 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 usa un contador C del número de vértices alcanzados hasta ahora, que usa 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:
- Establecer el número de orden previo V a C , y el incremento C .
- Empuje v en S y también sobre P .
- Para cada arista desde v hasta un vértice vecino w :
- Si aún no se ha asignado el número de preorden de w (el borde es un borde de árbol ), busque w de forma recursiva ;
- De lo contrario, si w aún no se ha asignado a un componente fuertemente conectado (el borde es un borde delantero / trasero / transversal):
- Extraer vértices repetidamente desde P hasta que el elemento superior de P tenga un número de preorden menor o igual al número de preorden de w .
- Si v es el elemento superior de P :
- Haga estallar vértices desde S hasta que se haya reventado v , y asigne los vértices reventados 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 tiene un número de preorden asignado.
Algoritmos relacionados
Al igual que este algoritmo, el algoritmo de componentes fuertemente conectados de Tarjan también utiliza la primera 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 usa 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
- ^ Sedgewick (2004) .
- ↑ History of Path-based DFS for Strong Components , 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 la ruta primero para componentes fuertes y biconectados", 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 gráfico 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 gráficos (3ª ed.), Cambridge MA: Addison-Wesley, págs. 205–216.