Unikalna ścieżka na ukierunkowanym wykresie

9

Projektuję algorytm dla klasy, który określi, czy skierowany wykres jest unikalny w odniesieniu do wierzchołka v tak, że dla każdego uv jest co najwyżej jedna ścieżka z v do u. Zacząłem od użycia BFS (wyszukiwanie szerokości), aby znaleźć najkrótszą ścieżkę od v do innego wierzchołka u, a następnie ponownie uruchomiłem BFS, aby sprawdzić, czy można znaleźć alternatywną ścieżkę od v do u. Myślę jednak, że jest to zbyt czasochłonne. Czy ktoś ma jakieś wskazówki, jak znaleźć rozwiązanie przy krótszym czasie realizacji?

Juho
źródło

Odpowiedzi:

9

Użyj BFS, aby pracować wstecz od v, oznaczając każdy wierzchołek jako „odwiedzany” podczas pracy. Jeśli kiedykolwiek trafisz na wierzchołek, który wcześniej odwiedziłeś, twój wykres nie ma właściwości unikatowości. W przeciwnym razie tak jest.


źródło
2

Jest to prosta modyfikacja dowolnego przejścia przez wykres: jeśli znajdziesz krawędź do wcześniej zaznaczonego węzła, masz wiele ścieżek.


źródło