Jeśli sortowanie topologiczne korzysta z systemu plików DFS, w jaki sposób może odnieść sukces na odłączonych wykresach?

Question

W mojej wiedzy jest luka, ale nie jestem pewien, gdzie dokładnie. Sortowanie topologiczne można wykonać za pomocą pierwszego wyszukiwania w głębi, jako wikipedia explains. Jednak widziałem tylko pierwsze wyszukiwanie w głębszych drzewach, gdzie sortowanie topologiczne jest dla DAG.

1. jest drzewem szczególnym przypadkiem DAG gdzie implikowana kierunek krawędzi wynosi od węzła głównego w dół
2. jest algorytm stosowany do topologicznej rodzaju naprawdę nie robi DFS, tylko coś bardzo podobny do tego?

Na przykład sortowanie topologiczne może obsłużyć rozłączone wykresy, w przypadku gdy system DFS nie może przejść przez węzeł bez żadnych krawędzi łączących go ... czy to możliwe?

Answer 1

Ponieważ przy sortowaniu topologicznym robisz DFS na dla każdego węzła. Jeśli jedno z dzieci jest już odwiedzone przez poprzednią DFS (kolor czarny). Następnie jest już wciśnięty w wektor wyjściowy, więc zależność już jest zrobiona.

Cytowanie linku (Kopalnia nacisk):

Algorytm pętle przez każdy węzeł wykresu, w dowolnej kolejności, inicjowanie głębokość pierwszego wyszukiwania ...

w artykule wikipedia jest nieco mylące (moim zdaniem) postaram się lepiej opisać algorytm:

 V: set of vertices 
    E: set of edges 
    E.adj(v): set of vertices adjacent to vertex v 

0 function topological_sort(V,E): 
1 for v in V: 
2  paint v white 
3 
4 for v in V: 
5  if v is white: 
6  dfs(v) 

7 function dfs(v): 
8 paint v grey 
9 for child in E.adj(v) 
10  if child is white: 
11  dfs(child) 
12 paint v black 
13 push v to output 

Możemy łatwo obliczyć złożoności:

• Malujemy wierzchołek białe, szare i czarne raz na wierzchołku: O(V)
• Sprawdzimy kolor wierzchołka na linii 5 raz na wierzchołku: O(V)
• Sprawdzimy kolor wierzchołka na linii 10 raz na krawędzi: O(E)
• Mamy przesunąć wierzchołek do wyjścia na linię 13 raz na wierzchołku: O(V)

Ostateczna złożoność to: O(V+E). Jest dość wydajny.

Jedną z zalet tego algorytmu jest to, że nie trzeba modyfikować wykresu wejściowego. Możemy łatwo zaimplementować kolorowanie za pomocą tymczasowego hashtable o rozmiarze w O(V). Niektóre inne algorytmy sortowania topologicznego wymagają zniszczenia wykresu, gdy są kontynuowane (przez usunięcie krawędzi). Wymagałoby to skopiowania wykresu przed uruchomieniem sortowania toplogicznego, jeśli nadal potrzebujesz sortowania według tego wykresu.

Answer 2

Możesz chcieć dodać nowy "źródłowy" węzeł do swojego wykresu i połączyć go z każdym innym węzłem o skierowanym brzegu. Następnie rozpocznij wyszukiwanie/przechodzenie z tego nowego węzła. Takie podejście może, ale nie musi odpowiadać twoim potrzebom.