El algoritmo de componentes fuertemente conectados de Tarjan es un algoritmo en la teoría de grafos para encontrar los componentes fuertemente conectados (SCC) de un grafo dirigido . Se ejecuta en tiempo lineal , coincidiendo con el límite de tiempo para métodos alternativos, incluido el algoritmo de Kosaraju y el algoritmo de componente fuerte basado en ruta . El algoritmo lleva el nombre de su inventor, Robert Tarjan . [1]
Estructura de datos | Grafico |
---|---|
Rendimiento en el peor de los casos |
Descripción general
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.
La idea básica del algoritmo es la siguiente: una búsqueda en profundidad primero (DFS) 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 visitado. 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 podría servir como raíz, si resulta ser el primer nodo de un componente que se descubre mediante una búsqueda.
Pila invariante
Los nodos se colocan en una pila en el orden en que se visitan. Cuando la búsqueda en profundidad primero visita de forma recursiva un nodo v
y sus descendientes, esos nodos no se extraen necesariamente de la pila cuando regresa esta llamada recursiva. La propiedad invariante crucial es que un nodo permanece en la pila después de haber sido visitado si y solo si existe una ruta en el gráfico de entrada desde él hasta algún nodo anterior en la pila. En otras palabras, significa que en el DFS un nodo solo se eliminaría de la pila después de que se hayan atravesado todas sus rutas conectadas. Cuando el DFS retroceda, eliminará los nodos en una sola ruta y volverá a la raíz para comenzar una nueva ruta.
Al final de la llamada que visita v
y sus descendientes, sabemos si él v
mismo tiene una ruta a algún nodo anterior en la pila. Si es así, la llamada regresa, dejando v
en la pila para preservar el invariante. Si no es así, entonces v
debe ser la raíz de su componente fuertemente conectado, que consiste en, v
junto con cualquier nodo posterior en la pila que v
(todos los nodos tienen rutas de regreso v
pero no a ningún nodo anterior, porque si tenían rutas a nodos anteriores, entonces v
también tendría rutas a nodos anteriores, lo cual es falso). El componente conectado enraizado en v
se extrae de la pila y se devuelve, conservando nuevamente el invariante.
Teneduría de libros
A cada nodo v
se le asigna un número entero único v.index
, que numera los nodos consecutivamente en el orden en que se descubren. También mantiene un valor v.lowlink
que representa el índice más pequeño de cualquier nodo conocido para ser alcanzable a partir de v
a través de v
's DFS subárbol, incluyendo v
en sí. Por v
lo tanto, debe dejarse en la pila if v.lowlink < v.index
, mientras que v debe eliminarse como raíz de un componente if fuertemente conectado v.lowlink == v.index
. El valor v.lowlink
se calcula durante la búsqueda en profundidad desde v
, ya que encuentra los nodos desde los que se puede acceder v
.
El algoritmo en pseudocódigo
algoritmo tarjan es entrada: gráfico G = ( V , E ) salida: conjunto de componentes fuertemente conectados (conjuntos de vértices) index : = 0 S : = pila vacía para cada v en V do si v .index no está definido, entonces strongconnect ( v ) end if end for function strongconnect ( v ) // Establecer el índice de profundidad para v al índice no utilizado más pequeño v .index: = index v .lowlink: = index index : = index + 1 S .push ( v ) v .onStack: = true // Considere los sucesores de v para cada ( v , w ) en E do si w .index no está definido, entonces // El sucesor w aún no ha sido visitado; recurse en él strongconnect ( w ) v .lowlink: = min ( v .lowlink, w .lowlink) else if w .onStack then // Sucesor w está en la pila S y por lo tanto en el SCC actual // Si w no está en la pila , entonces ( v , w ) es un borde que apunta a un SCC ya encontrado y debe ignorarse // Nota: La siguiente línea puede parecer extraña, pero es correcta. // Dice w.index no w.lowlink; eso es deliberado y del artículo original v .lowlink: = min ( v .lowlink, w .index) end if end for // Si v es un nodo raíz, abre la pila y genera un SCC si v .lowlink = v .index entonces iniciar un nuevo componente fuertemente conectado repetir w : = S .pop () w .onStack: = falso sumar w al componente de corriente fuertemente conectado mientras w ≠ v salida del componente de corriente fuertemente conectado end if end función
La index
variable es el contador de número de nodo de búsqueda en profundidad. S
es la pila de nodos, que comienza vacía y almacena el historial de los nodos explorados pero aún no comprometidos con un componente fuertemente conectado. Tenga en cuenta que esta no es la pila de búsqueda normal en profundidad, ya que los nodos no aparecen cuando la búsqueda vuelve a subir por el árbol; solo aparecen cuando se ha encontrado un componente completo fuertemente conectado.
El bucle más externo busca en cada nodo que aún no ha sido visitado, asegurando que los nodos que no son accesibles desde el primer nodo aún se atraviesen eventualmente. La función strongconnect
realiza una única búsqueda en profundidad del gráfico, encontrando todos los sucesores del nodo v
e informando todos los componentes fuertemente conectados de ese subgrafo.
Cuando cada nodo termina de recurrir, si su vínculo bajo todavía está establecido en su índice, entonces es el nodo raíz de un componente fuertemente conectado, formado por todos los nodos que están por encima de él en la pila. El algoritmo muestra la pila hasta el nodo actual incluido, y presenta todos estos nodos como un componente fuertemente conectado.
Tenga en cuenta que es la forma correcta de actualizar si está en la pila. Porque ya está en la pila, es un back-edge en el árbol DFS y por lo tanto no está en el subárbol de . Porque tiene en cuenta los nodos accesibles solo a través de los nodos en el subárbol de , debemos detenernos en y usar en lugar de .v.lowlink := min(v.lowlink, w.index)
v.lowlink
w
w
(v, w)
w
v
v.lowlink
v
w
w.index
w.lowlink
Complejidad
Complejidad de tiempo : el procedimiento de Tarjan se llama una vez para cada nodo; la declaración forall considera cada borde como máximo una vez. Por lo tanto, el tiempo de ejecución del algoritmo es lineal en el número de bordes y nodos en G, es decir.
Para lograr esta complejidad, la prueba de si w
está en la pila debe realizarse en un tiempo constante. Esto se puede hacer, por ejemplo, almacenando una bandera en cada nodo que indique si está en la pila y realizando esta prueba examinando la bandera.
Complejidad espacial : el procedimiento de Tarjan requiere dos palabras de datos suplementarios por vértice para los campos index
y lowlink
, junto con un bit para onStack
y otro para determinar cuándo index
no está definido. Además, se requiere una palabra en cada marco de pila para retener v
y otra para la posición actual en la lista de bordes. Finalmente, el tamaño de la pila en el peor de los casos S
debe ser(es decir, cuando el gráfico es un componente gigante). Esto da un análisis final de dónde es el tamaño de la palabra de la máquina. La variación de Nuutila y Soisalon-Soininen redujo esto a y, posteriormente, el de Pearce sólo requiere . [2] [3]
Observaciones adicionales
Si bien no hay nada especial en el orden de los nodos dentro de cada componente fuertemente conectado, una propiedad útil del algoritmo es que ningún componente fuertemente conectado será identificado antes que ninguno de sus sucesores. Por lo tanto, el orden en el que se identifican los componentes fuertemente conectados constituye un tipo topológico inverso del DAG formado por los componentes fuertemente conectados. [4]
Donald Knuth describió el algoritmo SCC de Tarjan como una de sus implementaciones favoritas en el libro The Stanford GraphBase . [5]
También escribió: [6]
Las estructuras de datos que ideó para este problema encajan de una manera asombrosamente hermosa, de modo que las cantidades que necesita mirar mientras explora un gráfico dirigido están siempre mágicamente al alcance de su mano. Y su algoritmo también realiza una clasificación topológica como subproducto.
Referencias
- ^ Tarjan, RE (1972), "Búsqueda en profundidad y algoritmos de gráficos lineales", SIAM Journal on Computing , 1 (2): 146-160, doi : 10.1137 / 0201010
- ^ Nuutila, Esko (1994). "Sobre la búsqueda de los componentes fuertemente conectados en un gráfico dirigido". Cartas de procesamiento de información . 49 (1): 9-14. doi : 10.1016 / 0020-0190 (94) 90047-7 .
- ^ Pearce, David. "Un algoritmo de uso eficiente del espacio para detectar componentes fuertemente conectados". Cartas de procesamiento de información . 116 (1): 47–52. doi : 10.1016 / j.ipl.2015.08.010 .
- ^ Harrison, Paul. "Clasificación topológica robusta y algoritmo de Tarjan en Python" . Consultado el 9 de febrero de 2011 .
- ^ Knuth, The Stanford GraphBase , páginas 512–519.
- ^ Knuth, Donald (20 de mayo de 2014). Veinte preguntas para Donald Knuth .