Algoritmo de Kosaraju (en honor al científico estadounidense de origen indio Sambasiva Rao Kosaraju) es un algoritmo para encontrar regiones fuertemente conectadas en un gráfico dirigido . Para encontrar áreas de fuerte conectividad, primero se realiza la búsqueda en profundidad (DFS) en la inversión del gráfico original (es decir, contra los arcos), calculando el orden de salida de los vértices. Luego usamos esta inversión de orden para realizar una búsqueda en profundidad en el gráfico original (nuevamente, tomamos el vértice con el número máximo obtenido durante el paso hacia atrás). Los árboles del bosque DFS que se seleccionan como resultado son componentes fuertes.
Un gráfico acíclico dirigido es un gráfico dirigido que no contiene ciclos dirigidos.
El método de Kosaraju proporciona una búsqueda de componentes fuertemente conectados de un gráfico en tiempo lineal y memoria.
Prueba: Este método consta de dos rutinas de profundidad primero-primero-primero-primero-primero-primero-primero-primero-primero-primero-primero-primero-primer-conjunto, con modificaciones menores para que su tiempo de ejecución sea proporcional a V² en el caso de gráficos saturados y V + E en el caso de gráficos dispersos (si los gráficos se representan como listas de vértices adyacentes).
A continuación se muestra un ejemplo del funcionamiento del algoritmo de Kosaraju.
Para calcular los componentes fuertes de un gráfico dirigido de abajo a la izquierda, primero hacemos una búsqueda en profundidad en su reverso (arriba a la izquierda), calculando el vector de orden transversal inverso (Orden). Este orden es equivalente al orden inverso de atravesar el bosque DFS. Usando la inversión de este orden, realizamos un recorrido primero en profundidad en el gráfico original. Es decir, comenzamos en el nodo 3. Los árboles del bosque DFS que se seleccionan como resultado de este proceso son componentes sólidos. El contenido del vector id es el número del componente, los números de la izquierda son el número del vértice.