Używanie silnie połączonego komponentu Algo do sprawdzenia, czy wierzchołek jest osiągalny

Question

Chciałbym zobaczyć, czy dany wierzchołek, na przykład V0, może być osiągalny dla wszystkich innych wierzchołków na wykresie G.
Wiem, że mogę przechodzić przez każdy z nich wierzchołka na wykresie i wykonaj BFS/DFS, aby sprawdzić, czy V0 jest osiągalny.
Jednak wydaje się to bardzo nieefektywne.

Zastanawiam się, czy robię SCC algo na wykresie, a jeśli v0 jest częścią całego SCC, to mogę spokojnie stwierdzić, że v0 jest osiągalny przez wszystkie wierzchołki? Byłoby świetnie, ponieważ koszt SCC jest tylko O ​​(V + E) z Tarjanem i sprawdzenie, czy v0 jest częścią scc, również kosztowałoby czas liniowy.

Myślę, że to ma sens, ponieważ SCC oznacza, że ​​wierzchołki są osiągalne. Jakiekolwiek potwierdzenie tej logiki?

lub inne skuteczne podejście do tego?

Answer 1

V0 może nie należeć do SCC, ale nadal być osiągalne dla wszystkich innych wierzchołków. Na przykład wierzchołek wierzchołka d na diagramie jest osiągalny dla wszystkich innych wierzchołków, ale jedyny nietrywialny SCC zawiera wierzchołki i nie zawiera wierzchołka .

Aby sprawdzić, czy V0 dotrzeć pozostałych wierzchołkach, można odwrócić kierunek każdej krawędzi (w czasie liniowej), a następnie za pomocą BFS/DFS, od V0, w celu sprawdzenia, czy co drugi wierzchołek znajduje się osiągalny z V0 (również w czasie liniowym).

Answer 2

Zadzwońmy do wierzchołka, z którego są osiągalne wszystkie inne wierzchołki, wierzchołek wierzchołka. Jeśli na wykresie znajduje się wierzchołek wierzchołka, to musi on mieć tylko jedno źródło SCC (ponieważ dwa źródłowe kody SCC nie są osiągalne od siebie), które muszą zawierać wierzchołek wierzchołka (jeśli jest on w jakimkolwiek innym SCC, nie ma ścieżki od wierzchołka vista do źródła SCC). Ponadto w tym przypadku każdy wierzchołek w źródłowym SCC będzie wierzchołkiem wierzchołka. Algorytm jest po prostu na DFS zaczynając od dowolnego węzła i oznaczając wierzchołek najwyższym czasem wykańczania . To musi być w źródłowym SCC. Teraz ponownie uruchomimy DFS z tego wierzchołka , aby sprawdzić, czy możemy dotrzeć do wszystkich węzłów. Ponieważ algorytm po prostu używa dekompozycji w kodzie SCC i DFS , czas działania jest liniowy. Algorytm jest poprawny. Zauważ, że wierzchołek wierzchołka będzie istniał wtedy i tylko wtedy, gdy istnieje tylko jeden źródłowy SCC z . Każdy wierzchołek w źródłowym SCC jest osiągalny tylko przez inne wierzchołki w tym samym SCC, , więc żaden wierzchołek nie może osiągnąć wierzchołków w dwóch różnych źródłowych SCC. Ponadto, jeśli istnieje tylko jeden źródłowy SCC, każdy wierzchołek tego SCC jest wierzchołkiem wierzchołka, ponieważ wszystkie one są osiągalne z każdego innego innego. Zauważ, że DFS, który rozpoczyna się w dowolnym określonym SCC, nie zostanie zakończony, dopóki wszystkie dostępne SCC nie zostaną znalezione. Oznacza to, że ostatni węzeł do zakończenia jest w SCC , który nie jest osiągalny z jakichkolwiek innych SCC, to znaczy SCC źródła. Tak więc w pierwszej części naszego algorytmu znajdujemy węzeł w źródłowym SCC. Wykonując DFS, poprawnie określimy, czy jest to wierzchołek wierzchołka, czy nie jest wierzchołkiem perspektywy, a jeśli nie jest to wierzchołek wierzchołka, wiemy, że żaden nie istnieje na naszym wykresie w postaci .