El algoritmo de Kosaraju

En ciencias de la computación , el algoritmo de Kosaraju-Sharir (también conocido como algoritmo de Kosaraju ) es un algoritmo de tiempo lineal para encontrar los componentes fuertemente conexos de un grafo dirigido . Aho , Hopcroft y Ullman se lo atribuyen a S. Rao Kosaraju y Micha Sharir . ^{[ 1 ] [ 2 ]} Kosaraju lo sugirió en 1978 pero no lo publicó, mientras que Sharir lo descubrió de forma independiente y lo publicó en 1981. ^{[ 3 ]} Utiliza el hecho de que el grafo transpuesto (el mismo grafo con la dirección de cada arista invertida) tiene exactamente los mismos componentes fuertemente conexos que el grafo original.

Las operaciones básicas que utiliza el algoritmo consisten en enumerar los vértices del grafo, almacenar datos por vértice (si no en la propia estructura de datos del grafo , en una tabla que utilice los vértices como índices), enumerar los vecinos salientes de un vértice (recorriendo las aristas en sentido directo) y enumerar los vecinos entrantes de un vértice (recorriendo las aristas en sentido inverso). Sin embargo, esta última operación puede omitirse, a costa de construir una representación del grafo transpuesto durante la fase de recorrido directo. La única estructura de datos adicional que necesita el algoritmo es una lista ordenada L de vértices del grafo, que crecerá hasta contener cada vértice una sola vez.

Si los componentes fuertes se representan designando un vértice raíz separado para cada componente, y asignando a cada vértice el vértice raíz de su componente, entonces el algoritmo de Kosaraju se puede enunciar de la siguiente manera.

1. Para cada vértice u del grafo, márquelo como no visitado. Sea L un conjunto vacío.
2. Para cada vértice u del grafo, haga Visit(u), donde Visit(u)es la subrutina recursiva:

   Si u no ha sido visitado, entonces:

   1. Marcar como visitado.
   2. Para cada vecino saliente v de u , haga lo siguiente Visit(v):
   3. Anteponga u a L.​

   De lo contrario, no hagas nada.

3. Para cada elemento u de L en orden, haga Assign(u,u)donde Assign(u,root)es la subrutina recursiva:

   Si u no se ha asignado a un componente, entonces:

   1. Asigna u como perteneciente al componente cuya raíz es root .
   2. Para cada vecino entrante v de u , haga lo siguiente Assign(v,root):

   De lo contrario, no hagas nada.

Variantes sencillas consisten en asignar un número de componente a cada vértice o en crear listas de vértices por componente que le pertenecen. La indicación de vértice visitado/no visitado puede compartir ubicación de almacenamiento con la asignación final de raíz para un vértice.

El punto clave del algoritmo es que, durante el primer recorrido (hacia adelante) de las aristas del grafo, los vértices se añaden a la lista L en orden posterior al del árbol de búsqueda que se está explorando. Esto significa que no importa si un vértice v se visitó primero porque apareció en la enumeración de todos los vértices o porque era el vecino saliente de otro vértice u que fue visitado; en cualquier caso, v se añadirá a L antes que u , por lo que si hay un camino hacia adelante de u a v, entonces u aparecerá antes que v en la lista final L (a menos que u y v pertenezcan al mismo componente fuerte, en cuyo caso su orden relativo en L es arbitrario).

Esto significa que cada elemento n de la lista puede corresponder a un bloque L[ i _{n -1} : i _n ] , donde el bloque consta de todos los vértices alcanzables desde el vértice n usando solo aristas salientes en cada nodo del camino. Ningún vértice en el bloque que comienza en n tiene un enlace entrante desde ninguno de los bloques que comienzan en algún vértice a su derecha, es decir, los bloques correspondientes a los vértices i _n , i _{n +1} , … N en la lista. Esto es así porque, de lo contrario, el vértice que tiene el enlace entrante (por ejemplo, desde el bloque que comienza en n' ≥ i _{n +1} ) ya habría sido visitado y antepuesto a L en el bloque de n' , lo cual es una contradicción. Por otro lado, los vértices en el bloque que comienza en n pueden tener aristas que apuntan a los bloques que comienzan en algún vértice en { i _n , i _{n +1} , … N }.

El paso 3 del algoritmo, que comienza en L[0] , asigna a todos los vértices que apuntan a él el mismo componente que L[0] . Cabe destacar que estos vértices solo pueden estar en el bloque que comienza en L[0], ya que los bloques superiores no pueden tener enlaces que apunten a vértices en el bloque de L[0] . Sea In(L[0]) el conjunto de todos los vértices que apuntan a L[0] . Posteriormente, se añaden también todos los vértices que apuntan a estos vértices, In(In(L[0])) , y así sucesivamente hasta que no se puedan añadir más vértices.

Hay un camino a L[0] desde todos los vértices añadidos al componente que contiene L[0] . Y hay un camino a todos los vértices añadidos desde L[0] , ya que todos ellos se encuentran en el bloque que comienza en L[0] (que contiene todos los vértices alcanzables desde L[0] siguiendo las aristas salientes en cada paso del camino). Por lo tanto, todos estos forman un único componente fuertemente conexo. Además, no queda ningún vértice, porque, para estar en este componente fuertemente conexo, un vértice debe ser alcanzable desde L[0] y debe poder alcanzar L[0] . Todos los vértices que pueden alcanzar L[0] , si los hay, se encuentran solo en el primer bloque, y todos los vértices en el primer bloque son alcanzables desde L[0] . Así que el algoritmo elige todos los vértices en el componente conexo de L[0] .

Cuando llegamos al vértice v = L[ i ] , en el bucle del paso 3, y v no ha sido asignado a ningún componente, podemos estar seguros de que todos los vértices a la izquierda han formado sus componentes conexas; que v no pertenece a ninguno de esos componentes; que v no apunta a ninguno de los vértices a su izquierda. Además, como no existe ninguna arista desde bloques superiores al bloque de v , la demostración sigue siendo la misma.

Como se indicó anteriormente, el algoritmo, por simplicidad, emplea una búsqueda en profundidad , pero también podría utilizar una búsqueda en amplitud siempre que se conserve la propiedad de postorden.

El algoritmo puede entenderse como la identificación del componente fuerte de un vértice u como el conjunto de vértices que son alcanzables desde u tanto por recorrido hacia atrás como hacia adelante. Escribiendo F ( u ) para el conjunto de vértices alcanzables desde u por recorrido hacia adelante, B ( u ) para el conjunto de vértices alcanzables desde u por recorrido hacia atrás, y P ( u ) para el conjunto de vértices que aparecen estrictamente antes de u en la lista L después de la fase 2 del algoritmo, el componente fuerte que contiene un vértice u designado como raíz es

${\displaystyle B(u)\cap F(u)=B(u)\setminus (B(u)\setminus F(u))=B(u)\setminus P(u).}$

La intersección de conjuntos es computacionalmente costosa, pero es lógicamente equivalente a una diferencia de conjuntos doble , y dado que${\displaystyle B(u)\setminus F(u)\subseteteq P(u)}$Resulta suficiente comprobar si un elemento recién encontrado de B ( u ) ya ha sido asignado a un componente o no .

Si el grafo se describe mediante una lista de adyacencia , el algoritmo de Kosaraju realiza dos recorridos completos del grafo y, por lo tanto, se ejecuta en tiempo lineal (Θ(V+E)), lo cual es asintóticamente óptimo porque existe una cota inferior correspondiente (cualquier algoritmo debe examinar todos los vértices y aristas). Es el algoritmo eficiente conceptualmente más simple, pero no es tan eficiente en la práctica como el algoritmo de componentes fuertemente conexas de Tarjan y el algoritmo de componentes fuertes basado en caminos , que realizan solo un recorrido del grafo.

Si el gráfico se representa como una matriz de adyacencia , el algoritmo requiere un tiempo de O(V ² ) .

• Matemáticas buenas y matemáticas malas: cálculo de componentes fuertemente conectados