Algoritmo de Tarjan

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 14 de junio de 2022; las comprobaciones requieren 5 ediciones .

El algoritmo de Tarjan  es un algoritmo para encontrar componentes fuertemente conectados en un dígrafo que se ejecuta en tiempo lineal.


Este algoritmo se basa en:

  1. Los vértices se consideran en orden topológico inverso, por lo que al final de la función recursiva para el vértice original, no se encontrará ningún vértice del mismo componente fuertemente conectado, ya que todos los vértices alcanzables desde el vértice original ya han sido procesados.
  2. Las retroalimentaciones en un árbol dan una segunda ruta de un vértice a otro y conectan los componentes fuertemente conectados en uno.

Descripción informal del algoritmo

El algoritmo de Tarjan se puede entender como una variación del algoritmo de búsqueda primero en profundidad , en el que se realizan pasos adicionales cuando se visita un nodo y se completa el procesamiento del nodo. Una visita a un vértice se produce al pasar de la raíz a las hojas, y el final del procesamiento del vértice se produce en el camino de regreso. Cuando se visita un vértice, se empuja a la pila auxiliar; cuando se procesa un componente fuertemente conectado, todos sus vértices se empujan fuera de esta pila [1] .

Algoritmo en pseudocódigo

// datos de entrada: gráfico dirigido G = (V, A) // datos de salida: conjunto de componentes fuertemente conectados index  := 0 stack  := [] para cada v en V do if v .index = null then strongconnect( v ) function strongconnect( v ) // En index almacenamos el número de vértices previamente procesados, v.index es el "tiempo de entrada" al vértice v v .index := index v .lowlink := index index  := index + 1 stack .push( v ) // El campo onStack es necesario para verificar si la parte superior pertenece a la pila en O(1) v .onStack := true // Iterar sobre los arcos que salen de v para cada ( v , w ) en A do if w .index = null then // El vértice w no ha sido visitado antes; ejecutar recursivamente desde él strongconnect( w ) v .lowlink := min( v .lowlink, w .lowlink) else if w .onStack then // El vértice w está en la pila, por lo que pertenece al mismo componente fuertemente conectado que v / / Si w no está en la pila, entonces el arco ( v , w ) conduce al componente fuertemente conectado previamente procesado y debe ignorarse // Nota: la siguiente línea usa deliberadamente w.index en lugar de w.lowlink - esto se refiere a Artículo original de Tarjan // Si reemplazamos w.index con w.lowlink, el algoritmo sigue siendo correcto v .lowlink := min( v .lowlink, w .index) // El vértice v es la raíz del componente fuertemente conectado actual, todos los vértices en la pila desde v y superiores forman este componente si v .lowlink = v .index luego crear un nuevo componente fuertemente conectado repetir w  := pila .pop() w .onStack := falso agregue w al componente fuertemente conectado actual mientras que w ≠ v salida del componente fuertemente conectado actual

Horario de apertura

El algoritmo tiene complejidad temporal , donde  es el número de arcos y  son los vértices del grafo [1] .

Véase también

El algoritmo de búsqueda de componentes de dos pilas fuertemente conectados  es un algoritmo similar que utiliza la búsqueda primero en profundidad.

Notas

  1. ↑ 1 2 Jeremy Sik y otros, 2006 .

Enlaces

Literatura