Caminho exclusivo em um gráfico direcionado

9

Eu estou projetando um algoritmo para uma classe que irá determinar se um grafo direcionado é único no que diz respeito a um vértice tal que para qualquer u v existe no máximo um caminho de v para u . Comecei usando o BFS (pesquisa pela primeira vez) para encontrar o caminho mais curto de v para outro vértice u e executando o BFS novamente para verificar se um caminho alternativo pode ser encontrado de v para u. Eu acho que isso é muito demorado no entanto. Alguém tem alguma dica de como a solução pode ser encontrada com um tempo de execução menor?vvocêvvvocê

Juho
fonte

Respostas:

9

Use o BFS para retroceder a partir de v, sinalizando cada vértice como 'visitado' à medida que avança. Se você atingir um vértice visitado anteriormente, seu gráfico não terá a propriedade de exclusividade. Caso contrário, ele faz.


fonte
3

Veja o algoritmo Max Flow Min Cut .

Charlie Martin
fonte
2

É uma modificação simples de qualquer passagem do gráfico: se você encontrar uma aresta para um nó marcado anteriormente, terá vários caminhos.


fonte