El algoritmo de componentes fuertemente conectados de Tarjan es un algoritmo de 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 de los métodos alternativos, incluido el algoritmo de Kosaraju y el algoritmo de componentes fuertes basado en trayectorias . El algoritmo recibe su nombre de su inventor, Robert Tarjan . [1]
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 en exactamente 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 sea 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 (DFS) comienza desde un nodo de inicio arbitrario (y las búsquedas en profundidad posteriores se realizan en todos los nodos que aún no se han encontrado). Como es habitual en las búsquedas en profundidad, la búsqueda visita cada nodo del grafo exactamente una vez, y se niega a volver a visitar ningún nodo que ya haya sido visitado. Por lo tanto, la colección de árboles de búsqueda es 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 que se descubre mediante la búsqueda.
Los nodos se colocan en una pila en el orden en que se visitan. Cuando la búsqueda en profundidad visita recursivamente un nodo vy sus descendientes, esos nodos no necesariamente se extraen de la pila cuando esta llamada recursiva regresa. 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 recorrido todas sus rutas conectadas. Cuando el DFS retroceda, eliminará los nodos en una sola ruta y regresará a la raíz para comenzar una nueva ruta.
Al final de la llamada que visita vy sus descendientes, sabemos si vtiene una ruta a cualquier nodo anterior en la pila. Si es así, la llamada regresa, saliendo vde la pila para preservar el invariante. Si no, entonces vdebe ser la raíz de su componente fuertemente conectado, que consiste en vjunto con cualquier nodo posterior en la pila que v(dichos nodos tienen rutas de regreso a vpero no a ningún nodo anterior, porque si tuvieran rutas a nodos anteriores, entonces vtambién tendrían rutas a nodos anteriores, lo cual es falso). El componente conectado enraizado en vse extrae de la pila y se devuelve, nuevamente preservando el invariante.
A cada nodo vse le asigna un entero único v.index, que numera los nodos consecutivamente en el orden en que se descubren. También mantiene un valor v.lowlinkque representa el índice más pequeño de cualquier nodo en la pila que se sabe que es accesible desde va través vdel subárbol DFS de , incluido vél mismo. Por lo tanto, vdebe dejarse en la pila si v.lowlink < v.index, mientras que v debe eliminarse como raíz de un componente fuertemente conectado si v.lowlink == v.index. El valor v.lowlinkse calcula durante la búsqueda en profundidad desde v, ya que encuentra los nodos a los que se puede llegar desde v.
El enlace bajo es diferente del punto bajo, que es el índice más pequeño al que se puede llegar vdesde cualquier parte del gráfico. [1] : 156 [2]
El algoritmo tarjan tiene como entrada: grafo G = ( V , E ) salida: conjunto de componentes fuertemente conectados (conjuntos de vértices) índice := 0 S := pila vacía para cada v en V si v .index no está definido entonces strongconnect( v ) función strongconnect( v ) // Establece el índice de profundidad para v en el índice más pequeño no utilizado 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 if w .index is undefined then // El sucesor w aún no ha sido visitado; recurra a él strongconnect( w ) v .lowlink := min( v .lowlink, w .lowlink) else if w .onStack then // 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 // Vea a continuación con respecto a la siguiente línea v .lowlink := min( v .lowlink, w .index) // Si v es un nodo raíz, vacía 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 Agregue w al componente fuertemente conectado actual mientras w ≠ v Salida del componente fuertemente conectado actual
La indexvariable es el contador de número de nodo de búsqueda en profundidad. Ses la pila de nodos, que comienza vacía y almacena el historial de nodos explorados pero aún no asignados a un componente fuertemente conectado. Esta no es la pila de búsqueda en profundidad normal, ya que los nodos no se extraen a medida que la búsqueda vuelve hacia arriba en el árbol; solo se extraen cuando se ha encontrado un componente fuertemente conectado completo.
El bucle más externo busca cada nodo que aún no se haya visitado, lo que garantiza que los nodos a los que no se puede llegar desde el primer nodo se puedan recorrer de todos modos. La función strongconnectrealiza una única búsqueda en profundidad del grafo, encuentra todos los sucesores del nodo ve informa todos los componentes fuertemente conectados de ese subgrafo.
Cuando cada nodo termina de ejecutarse de manera recursiva, si su vínculo inferior aún está establecido en 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 hace que la pila se muestre hasta el nodo actual, incluido, 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 utilizar 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 nodos raíz de 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 sentencia 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, .
Para lograr esta complejidad, la prueba de si westá en la pila debe realizarse en tiempo constante. Esto se puede hacer como en el pseudocódigo anterior: almacenar un indicador en cada nodo que indique si está en la pila y realizar esta prueba examinando el 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 (es decir, cuando el gráfico es un componente gigante). Esto proporciona 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, la de Pearce requiere solo . [5] [6]
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 una clasificación topológica inversa del DAG formado por los componentes fuertemente conectados. [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 entre sí de una manera sorprendentemente hermosa, de modo que las cantidades que necesitas observar mientras exploras un gráfico dirigido siempre están mágicamente a tu alcance. Y su algoritmo también realiza una clasificación topológica como subproducto.
