Oi,
Olhando os slides, eu percebi que a pós ordem mencionada no algoritmo para achar os componentes fortemente conexos é igual ao topological sort. É isso mesmo (poderia se dizer isso numa prova)?
Oi Gabriel,
a pós ordem mencionada no algoritmo para achar os componentes fortemente conexos é igual ao topological sort. É isso mesmo
A ordem é pós-ordem reversa.
É meio confuso mesmo.
O algoritmo de Kosaraju tem pré-processamento para encontrar uma numeraçãoda/ordenação pós-pordem.
O primero vértice nessa ordem é o primeiro que foi completamente examinado.
O segundo vértice nessa ordem é o segundo que foi completamente examinado.
...
Esse pré-processamento é feito no início do construtor da classe Kosaraju():
DFS dfs = DFS(G); Essa dfs foi contruída para que tenhamos uma ordenação pós-pordem do vértices.
Na segunda fase temos uma nova busca em profundidade em que os vértices são parâmetros de chamadas dfs(G,v) na ordem inversa a da pós ordem:
primeiro é o último vértice vn-1 que foi completamente examinado durante o pré-processamento;
depois o penúltimo vértice vn-2 que foi completamente examinado (caso ele não seja marcado pela primeira chamada de dfs(vn-1)) pelo pré-processamento;
depois o anti-penúltimo vértice ...
Professor,
Se obtermos o um grafo h, reverso de g, o comportamento para obter pós[] não é o mesmo de uma ordem topológica? (que no caso seria adicionar o vértice ao stack quando todos os caminhos disponíveis estão marcados)
Ois,
o comportamento para obter pós[] não é o mesmo de uma ordem topológica?
Certo.
Para digrafos acíclicos, uma ordenação pós-ordem reversa de seus vértices induz/forma/é uma uma ordenação topológica do digrafo.
Os artigos indefinidos são devidos a:
- a ordenação pós-ordem pode não ser única: a floresta
dfsdepende dos vértices selecionados para serem raizes das árvoresdfse essas dependem da ordem em que os arcos são examinados:for (int w: G.adj(v) { examine arco v-w } - há digrafos que possuem várias ordenações topológica.
Entendi! muito obrigado.