De hecho, ya hay un artículo sobre Habré sobre este algoritmo, pero no cubre la prueba de la corrección y algunos pasos del algoritmo. Decidí crear una versión más de referencia de ese artículo con un análisis completo.
Este post será de utilidad para los estudiantes de la disciplina "Algoritmos y teoría de grafos", así como para aquellos que quieran mejorar / refrescar sus conocimientos de algoritmos sobre grafos.
Para comprender el algoritmo de Kosarayu, necesita conocer algunos conceptos de teoría de grafos
Conceptos básicos
Los vértices u, v se denominan fuertemente conectados si el gráfico G contiene una trayectoria (no necesariamente una línea recta) u → v Y v → u (Denotamos los vértices fuertemente conectados por u↔v)
Los componentes fuertemente conectados son subgrafos fuertemente conectados máximos con respecto a la inclusión.
Invertir el gráfico: cambiar la dirección de todos los bordes en el gráfico al contrario (un borde bidireccional permanece en sí mismo)
Invertir un gráfico: el proceso de girar los bordes en la dirección opuesta (un borde bidireccional seguirá siendo él mismo)
Se pueden citar varios lemas bastante obvios:
1. Un componente fuertemente conectado es el conjunto de vértices incluidos en el conjunto de ciclos que
tienen al menos un vértice común
2.
3. u ↔ v v ↔ w, u ↔ v ↔ w
4.
:
(DFS), «» . «», DFS ( ).
DFS
DFS .
DFS
, : : , :
DFS
( , , )
,
:
1:
'?'
DFS ( 2 , ; , , )
, - ( ) 1
, () ( ) -- DFS -- .
2:
3:
DFS, ,
DFS
3
, :
u v ⇔ DFS
:
⇒
u v G, ( 2), , .
⇐
u v . , r .
r 3 , 1 , u v. 2 :
r . u r v r ( 2). u v ( 3)
r , v. r v , r — ( , v , r, ). ( , ), , v r 3 ( )
, 1 2 , u v
O(V+E)
, , O(V+E) . ( )
, O(V+E)
, — O(V+E)
, O(V+E) .
, .
Por ejemplo: proyectar una red de transporte en un gráfico. El algoritmo ayudará a verificar la red de transporte recién creada para verificar la accesibilidad de cada vértice desde cada vértice (para asegurarse de que haya un camino desde las afueras hasta el centro y viceversa).
Puede probar el sistema de conductos en edificios con un algoritmo; flujo de corriente en dispositivos semiconductores
Puede pensar de manera más amplia: proyectamos el sistema circulatorio de un ser vivo, que se le indicó que creara como parte de un proyecto de ingeniería genética, en algún lugar de 2077). El algoritmo le ayudará a averiguar si la sangre llega del corazón a los órganos y viceversa.