Na verdade, já existe um artigo de Habré sobre esse algoritmo, mas ele não cobre a prova da correção e alguns passos do algoritmo. Decidi criar uma versão mais de referência desse artigo com análise completa.
Este post será útil para alunos da disciplina "Algoritmos e Teoria de Grafos", bem como para aqueles que desejam aprimorar / atualizar seus conhecimentos sobre algoritmos em gráficos.
Para entender o algoritmo de Kosarayu, você precisa conhecer alguns conceitos da teoria dos grafos
Conceitos Básicos
Os vértices u, v são chamados de fortemente conectados se o grafo G contém um caminho (não necessariamente uma linha reta) u → v E v → u (Denotamos vértices fortemente conectados por u↔v)
Componentes fortemente conectados são subgráficos fortemente conectados máximos em relação à inclusão.
Inverter o gráfico - mudar a direção de todas as arestas no gráfico para o oposto (uma aresta bidirecional permanece ela mesma)
Inverter um gráfico - o processo de virar as bordas na direção oposta (uma borda bidirecional permanecerá ela mesma)
Vários lemas bastante óbvios podem ser citados:
1. Um componente fortemente conectado é o conjunto de vértices incluídos no conjunto de ciclos que
têm pelo menos um vértice comum
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 exemplo: projetar uma rede de transporte em um grafo. O algoritmo ajudará a verificar a rede de transporte recém-criada para a acessibilidade de cada vértice de cada vértice (para ter certeza de que há um caminho da periferia para o centro e vice-versa).
Você pode testar o sistema de dutos em edifícios com um algoritmo; fluxo atual em dispositivos semicondutores
Você pode pensar de forma mais ampla: nós projetamos o sistema circulatório de um ser vivo, que você foi instruído a criar como parte de um projeto de engenharia genética, em algum lugar em 2077). O algoritmo o ajudará a descobrir se o sangue está chegando do coração aos órgãos e vice-versa.