Algoritmo de componentes fuertemente conectadas de Tarjan

El algoritmo de componentes fuertemente conexas de Tarjan es un algoritmo de teoría de grafos para encontrar las componentes fuertemente conexas (CFC) de un grafo dirigido . Se ejecuta en tiempo lineal , igualando el límite de tiempo de métodos alternativos como el algoritmo de Kosaraju y el algoritmo de componentes fuertes basado en caminos . El algoritmo recibe su nombre de su inventor, Robert Tarjan . ^{[ 1 ]}

El algoritmo toma como entrada un grafo dirigido y produce una partición de sus vértices en sus componentes fuertemente conexas. Cada vértice del grafo aparece en exactamente una de estas componentes. Cualquier vértice que no esté en un ciclo dirigido forma una componente fuertemente conexa por sí mismo; es decir, cualquier vértice cuyo grado de entrada o de salida sea 0, o cualquier vértice de un grafo dirigido acíclico .

La idea básica del algoritmo es la siguiente: una búsqueda en profundidad (DFS) comienza desde un nodo inicial arbitrario (y las búsquedas en profundidad subsiguientes se realizan en cualquier nodo que aún no se haya encontrado). Como es habitual en la búsqueda en profundidad, la búsqueda visita cada nodo del grafo exactamente una vez, sin volver a visitar ningún nodo que ya haya sido visitado. De este modo, el conjunto de árboles de búsqueda constituye un bosque de expansión del grafo. 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 puede servir como raíz, si resulta ser el primer nodo de un componente descubierto mediante la búsqueda.

El algoritmo Tarjan recibe como entrada: grafo G = ( V , E ) y como salida: conjunto de componentes fuertemente conectadas (conjuntos de vértices). índice := 0 S := pila vacía para cada v en V hacer si v .index no está definido entonces strongconnect( v ) function strongconnect( v ) // Establece 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 // Considerar sucesores de v para cada ( v , w ) en E hacer si w .index no está definido entonces // El sucesor w aún no ha sido visitado; recursión en él strongconnect( w ) v .lowlink := min( v .lowlink, w .lowlink) sino si w .onStack entonces // El 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 una arista que apunta a un SCC ya encontrado y debe ignorarse // Ver más abajo con respecto a la siguiente línea v .lowlink := min( v .lowlink, w .index) // Si v es un nodo raíz, extraiga la pila y genere un SCC si v .lowlink = v .index entonces iniciar un nuevo componente fuertemente conectado repetir w := S .pop() w .onStack := false Sumar w al componente fuertemente conectado actual mientras w ≠ v generar el componente fuertemente conectado actual

La indexvariable es el contador de nodos de la búsqueda en profundidad. Ses la pila de nodos, que comienza vacía y almacena el historial de nodos explorados pero aún no incorporados a un componente fuertemente conectado. Esta no es la pila de búsqueda en profundidad habitual, ya que los nodos no se extraen a medida que la búsqueda avanza en el árbol; solo se extraen cuando se ha encontrado un componente fuertemente conectado completo.

El bucle más externo busca en cada nodo que aún no se ha visitado, asegurando que los nodos que no son accesibles desde el primer nodo se recorran finalmente. La función strongconnectrealiza una única búsqueda en profundidad del grafo, encontrando todos los sucesores del nodo vy reportando todos los componentes fuertemente conectados de ese subgrafo.

Cuando cada nodo finaliza su recursión, si su enlace inferior (lowlink) aún apunta a su índice, entonces es el nodo raíz de un componente fuertemente conectado, formado por todos los nodos que se encuentran por encima de él en la pila. El algoritmo extrae elementos de la pila hasta el nodo actual inclusive, y presenta todos estos nodos como un componente fuertemente conectado.

En el artículo de Tarjan, cuando westá en la pila, v.lowlinkse actualiza con la asignación . ^{[ 1 ] : 157} Una variación común es usar en su lugar . ^{[ 3 ] [ 4 ]} Este algoritmo modificado no calcula los números de enlace bajo como los definió Tarjan, pero la prueba aún identifica los nodos raíz de los componentes fuertemente conectados y, por lo tanto, el algoritmo general sigue siendo válido. ^{[ 2 ]}v.lowlink := min(v.lowlink, w.index)v.lowlink := min(v.lowlink, w.lowlink)v.lowlink = v.index

Complejidad temporal : El procedimiento Tarjan se llama una vez por cada nodo; la instrucción forall considera cada arista como máximo una vez. Por lo tanto, el tiempo de ejecución del algoritmo es lineal en el número de aristas y nodos en G, es decir${\displaystyle O(|V|+|E|)}$.

Para lograr esta complejidad, la comprobación de si un elemento westá en la pila debe realizarse en tiempo constante. Esto se puede hacer como en el pseudocódigo anterior: se almacena un indicador en cada nodo que señala si está en la pila y se realiza la comprobación examinando dicho indicador.

Complejidad espacial : El procedimiento Tarjan requiere dos palabras de datos suplementarios por vértice para los campos indexy lowlink, junto con un bit para onStacky otro para determinar cuándo indexno está definido. Además, se requiere una palabra en cada marco de pila para contener vy otra para la posición actual en la lista de aristas. Finalmente, el tamaño de la pila en el peor de los casos Sdebe ser${\displaystyle |V|}$(es decir, cuando el gráfico es un componente gigante). Esto proporciona un análisis final de${\displaystyle O(|V|\cdot (2+5w))}$dónde${\displaystyle w}$es el tamaño de palabra de la máquina. La variación de Nuutila y Soisalon-Soininen lo redujo a${\displaystyle O(|V|\cdot (1+4w))}$y, posteriormente, la de Pearce solo requiere${\displaystyle O(|V|\cdot (1+3w))}$. ^{[ 5 ] [ 6 ]}

Si bien el orden de los nodos dentro de cada componente fuertemente conexa no tiene nada de especial, una propiedad útil del algoritmo es que ningún componente fuertemente conexo se identificará antes que ninguno de sus sucesores. Por lo tanto, el orden en que se identifican los componentes fuertemente conexos constituye una ordenación topológica inversa del DAG formado por dichos componentes. ^{[ 7 ]}

Donald Knuth describió el algoritmo SCC de Tarjan como una de sus implementaciones favoritas en el libro The Stanford GraphBase . ^{[ 8 ]}

También escribió: ^{[ 9 ]}

Las estructuras de datos que ideó para este problema encajan a la perfección, de modo que las cantidades que necesitas consultar al explorar un grafo dirigido están siempre a tu alcance. Además, su algoritmo realiza una ordenación topológica como resultado secundario.

• Código Rosetta , que muestra implementaciones en diferentes lenguajes.
• Implementación en PHP del algoritmo de componentes fuertemente conectadas de Tarjan.
• Implementación en JavaScript del algoritmo de componentes fuertemente conectadas de Tarjan.