En informática , el algoritmo de Kosaraju-Sharir (también conocido como algoritmo de Kosaraju ) es un algoritmo de tiempo lineal para encontrar los componentes fuertemente conectados de un gráfico dirigido . Aho , Hopcroft y Ullman se lo atribuyen a S. Rao Kosaraju y Micha Sharir . Kosaraju lo sugirió en 1978 pero no lo publicó, mientras que Sharir lo descubrió de forma independiente y lo publicó en 1981. Hace uso del hecho de que el gráfico de transposición (la misma gráfica con la dirección de cada borde invertida) tiene exactamente los mismos componentes fuertemente conectados que la gráfica original.
El algoritmo
Las operaciones gráficas primitivas que utiliza el algoritmo son enumerar los vértices del gráfico, almacenar datos por vértice (si no está en la estructura de datos del gráfico en sí, entonces en alguna tabla que pueda usar vértices como índices), enumerar los vecinos externos de un vértice (bordes transversales en la dirección hacia adelante), y para enumerar los vecinos internos de un vértice (bordes transversales en la dirección hacia atrás); sin embargo, el último se puede hacer sin, al precio de construir una representación del gráfico de transposición durante la fase de recorrido hacia adelante. La única estructura de datos adicional que necesita el algoritmo es una lista ordenada L de vértices de gráficos, que crecerá para contener cada vértice una vez.
Si se van a representar componentes fuertes 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 establecer de la siguiente manera.
- Para cada vértice u del gráfico, marque u como no visitado. Deje que L esté vacío.
- Para cada vértice u del gráfico, haga Visit ( u ), donde Visit ( u ) es la subrutina recursiva:
- Si U se ha visitado a continuación:
- Marcar u como visitado.
- Para cada vecino externo v de u , visite ( v ).
- Anteponer u a l .
- De lo contrario, no hagas nada.
- Si U se ha visitado a continuación:
- Para cada elemento u de L en orden, haga Assign ( u , u ) donde Assign ( u , root ) es la subrutina recursiva:
- Si no se ha asignado u a un componente, entonces:
- Asigne u como perteneciente al componente cuya raíz es root .
- Para cada vecino v de u , haga Asignar ( v , raíz ).
- De lo contrario, no hagas nada.
- Si no se ha asignado u a un componente, entonces:
Las variaciones triviales son, en cambio, asignar un número de componente a cada vértice, o construir listas por componente de los vértices que le pertenecen. La indicación no visitada / visitada puede compartir la 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 los bordes del gráfico, los vértices se anteponen a la lista L en orden posterior en relación con el árbol de búsqueda que se está explorando. Esto significa que no importa si un vértice v fue visitado primero porque apareció en la enumeración de todos los vértices o porque fue el vecino externo de otro vértice u el que fue visitado; de cualquier manera, v se antepondrá a L antes que u , por lo que si hay una ruta hacia adelante de u a v, entonces u aparecerá antes de 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). Como se indicó anteriormente, el algoritmo de simplicidad emplea la búsqueda en profundidad , pero también podría usar la búsqueda en amplitud siempre que se conserve la propiedad posterior al pedido.
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. Escritura para el conjunto de vértices alcanzables desde por recorrido hacia adelante, para el conjunto de vértices alcanzables desde por recorrido hacia atrás, y para el conjunto de vértices que aparecen estrictamente antes en la lista L después de la fase 2 del algoritmo, el componente fuerte que contiene un vértice designado como root es
- .
La intersección de conjuntos es computacionalmente costosa, pero es lógicamente equivalente a una diferencia de conjunto doble , y dado que se vuelve suficiente para probar si un elemento recién encontrado de ya se ha asignado a un componente o no.
Complejidad
Siempre que el gráfico se describa utilizando una lista de adyacencia , el algoritmo de Kosaraju realiza dos recorridos completos del gráfico y, por lo tanto, se ejecuta en un tiempo Θ (V + E) (lineal), que es asintóticamente óptimo porque hay un límite inferior coincidente (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 conectados de Tarjan y el algoritmo de componentes fuertes basado en rutas , que realizan solo un recorrido del gráfico.
Si el gráfico se representa como una matriz de adyacencia , el algoritmo requiere un tiempo Ο (V 2 ) .
Referencias
- Alfred V. Aho , John E. Hopcroft , Jeffrey D. Ullman . Estructuras de datos y algoritmos . Addison-Wesley, 1983.
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein . Introducción a los algoritmos , 3ª edición. The MIT Press, 2009. ISBN 0-262-03384-4 .
- Micha Sharir . Un algoritmo de conectividad fuerte y sus aplicaciones para el análisis del flujo de datos. Computadoras y matemáticas con aplicaciones 7 (1): 67–72, 1981.