Sortowanie topologiczne DFS w kolejności postorder
Uruchamiać DFS i umieszczać każdy wierzchołek na stosie po pełnym odwiedzeniu jego sąsiadów, a następnie zdejmować elementy ze stosu, aby uzyskać poprawny porządek topologiczny
Sortowanie topologiczne DFS w kolejności postorder to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Idea sortowania topologicznego opartego na DFS
Drugi klasyczny algorytm sortowania topologicznego wykorzystuje DFS z przetwarzaniem w porządku postorder. Po całkowitym przeanalizowaniu wszystkich sąsiadów wierzchołka (oraz ich potomków) odłóż wierzchołek na stos. Po przetworzeniu wszystkich wierzchołków zdejmuj elementy ze stosu, aby odczytać porządek topologiczny. Wierzchołek odłożony na stos po przeanalizowaniu wszystkich jego zależności powinien znaleźć się pierwszy w porządku — dlatego odwrócony porządek postorder jest sortowaniem topologicznym.
Intuicja stojąca za porządkiem postorder
Rozważmy graf zależności, w którym kurs A wymaga ukończenia kursu B. Gdy DFS odwiedza A, najpierw rekurencyjnie przechodzi do B. B nie ma żadnych wymagań wstępnych, więc kończy się jako pierwszy i jako pierwszy zostaje odłożony na stos. Następnie kończy się A i również zostaje odłożony. Zdejmowanie elementów ze stosu daje w wyniku A przed B — ale na końcu odwracamy kolejność, otrzymując B przed A: najpierw należy ukończyć B, a potem A. Porządek postorder odkłada zależności przed elementami, które od nich zależą, dlatego odwrócony stos jest poprawnym porządkiem topologicznym.
DFS z trzema kolorami do wykrywania cykli
Do oznaczania odwiedzonych wierzchołków użyj trzech stanów: WHITE (0) = nieodwiedzony, GREY (1) = obecnie przetwarzany (znajduje się na stosie wywołań DFS), BLACK (2) = całkowicie przetworzony. Krawędź wsteczna — krawędź prowadząca do wierzchołka GREY — wskazuje na cykl. Krawędzie prowadzące do wierzchołków BLACK są bezpieczne (zostały już w pełni przeanalizowane). Ten schemat trzech kolorów poprawnie wykrywa wszystkie cykle w grafach skierowanych.
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n # n = number of nodes
# During DFS:
# color[node] = GREY (entering node)
# recurse into neighbours
# if neighbour is GREY: cycle found!
# color[node] = BLACK (leaving node, push to stack)Pełna implementacja sortowania topologicznego z użyciem DFS
Użyj rekurencyjnego DFS, który koloruje wierzchołki, odkłada je na stos w porządku postorder i zwraca False po wykryciu cyklu. Po odwiedzeniu wszystkich wierzchołków stos (odczytany od końca) daje porządek topologiczny.
from collections import defaultdict
def dfs_topological_sort(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
stack = []
def dfs(node):
color[node] = GREY
for nxt in graph[node]:
if color[nxt] == GREY:
return False # cycle
if color[nxt] == WHITE:
if not dfs(nxt):
return False
color[node] = BLACK
stack.append(node)
return True
for i in range(n):
if color[i] == WHITE:
if not dfs(i):
return [] # cycle
return stack[::-1]
print(dfs_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))Iteracyjny DFS pozwalający uniknąć przepełnienia stosu
Limit rekurencji w Pythonie (domyślnie 1000) może stanowić problem w przypadku dużych grafów. Można go uniknąć, używając iteracyjnego DFS z jawnym stosem. Sztuczka polega na początkowym odłożeniu (node, False); po zdjęciu elementu z wartością False odłóż (node, True) (co oznacza „wrócę tutaj po przeanalizowaniu sąsiadów”), a następnie odłóż wszystkich nieodwiedzonych sąsiadów z wartością False. Po zdjęciu elementu z wartością True oznacz go kolorem BLACK i odłóż na stos wynikowy.
from collections import defaultdict
def dfs_topo_iterative(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
result = []
for start in range(n):
if color[start] != WHITE:
continue
stack = [(start, False)]
while stack:
node, returning = stack.pop()
if returning:
color[node] = BLACK
result.append(node)
elif color[node] == WHITE:
color[node] = GREY
stack.append((node, True)) # will return here
for nxt in graph[node]:
if color[nxt] == WHITE:
stack.append((nxt, False))
return result[::-1]DFS i algorytm Kahna: porównanie
Oba algorytmy działają w czasie O(V + E). Najważniejsze różnice: algorytm Kahna (BFS) w naturalny sposób zwraca wierzchołki w kolejności od najwcześniejszych zależności i ma prostsze wykrywanie cykli (sprawdzenie długości). DFS w porządku postorder działa rekurencyjnie i jawnie wykrywa krawędzie wsteczne. Algorytm Kahna jest preferowany, gdy wynik ma być od razu podany w kolejności właściwej, bez odwracania. DFS jest preferowany, gdy potrzebują Państwo pełnego porządku postorder do innych celów (na przykład do wykrywania SCC). Oba podejścia są akceptowane podczas rozmów rekrutacyjnych.
Porządek postorder w drzewie a w DAG-u
W drzewie porządek postorder odwiedza lewe poddrzewo → prawe poddrzewo → korzeń. W DAG-u DFS w porządku postorder odwiedza wszystkie zależności wierzchołka przed przetworzeniem samego wierzchołka — to ta sama idea uogólniona na wielu poprzedników i dowolną strukturę grafu. Korzeń drzewa DFS (wierzchołek początkowy) jest odkładany jako ostatni spośród swoich potomków, dlatego w odwróconym stosie pojawia się jako pierwszy — na właściwej pozycji topologicznej dla wierzchołka bez poprzedników.
Alien Dictionary (LeetCode 269)
Alien Dictionary: mając posortowaną listę słów w obcym języku, należy wyznaczyć kolejność znaków. Porównuj sąsiednie słowa znak po znaku, aby znaleźć pierwszą różnicę — daje ona krawędź c1 → c2, oznaczającą, że c1 występuje przed c2. Zbierz wszystkie takie krawędzie i uruchom sortowanie topologiczne, aby utworzyć kolejność znaków obcego języka. Jeśli istnieje cykl, kolejność jest niepoprawna.
from collections import defaultdict
def alienOrder(words):
graph = defaultdict(set)
all_chars = set(c for w in words for c in w)
for i in range(len(words)-1):
w1, w2 = words[i], words[i+1]
if len(w1) > len(w2) and w1.startswith(w2):
return '' # invalid (prefix comes after)
for c1, c2 in zip(w1, w2):
if c1 != c2:
graph[c1].add(c2)
break
# DFS topological sort on character graph
WHITE, GREY, BLACK = 0, 1, 2
color = {c: WHITE for c in all_chars}
result = []
def dfs(c):
color[c] = GREY
for nxt in graph[c]:
if color[nxt] == GREY: return False
if color[nxt] == WHITE and not dfs(nxt): return False
color[c] = BLACK
result.append(c)
return True
for c in all_chars:
if color[c] == WHITE:
if not dfs(c): return ''
return ''.join(result[::-1])
print(alienOrder(['wrt','wrf','er','ett','rftt'])) # 'wertf'Sortowanie topologiczne z ograniczeniami
Niektóre zadania wymagają sortowania topologicznego spełniającego dodatkowe ograniczenia, na przykład zachowania względnej kolejności elementów z oryginalnej listy. Połącz algorytm Kahna z niestandardową kolejką priorytetową lub wstępnym sortowaniem: zachowuj oryginalną kolejność względną, używając sortowania stabilnego zawartości kolejki na każdym kroku. Takie warianty z ograniczeniami sprawdzają głębsze rozumienie elastyczności algorytmu.
Rozpoznawanie problemów sortowania topologicznego
Zwroty często pojawiające się w zadaniach rekrutacyjnych, które wskazują na sortowanie topologiczne, to: „podane zależności”, „wymagania wstępne”, „kolejność zadań”, „kolejność budowania”, „czy można ukończyć wszystkie zadania?”, „znajdź poprawną sekwencję”. Jeśli zadanie dotyczy uporządkowania elementów, z których niektóre muszą wystąpić przed innymi, należy zbudować graf skierowany i zastosować sortowanie topologiczne algorytmem Kahna lub DFS. Wykrywanie cykli jest często dodatkowym wymaganiem w tym samym zadaniu.
Porównanie wyników DFS i algorytmu Kahna
DFS i algorytm Kahna mogą utworzyć różne poprawne porządki topologiczne dla tego samego grafu. Oba wyniki są poprawne — DAG może mieć wiele poprawnych porządków topologicznych. Aby zweryfikować poprawność, sprawdź, czy dla każdej krawędzi u → v w grafie u występuje przed v w wynikowym porządku. W zadaniach rekrutacyjnych wymagających konkretnego porządku (na przykład najmniejszego leksykograficznie) użyj algorytmu Kahna z kopcem minimalnym — DFS w porządku postorder nie tworzy naturalnie porządku leksykograficznie najmniejszego.
Szybki test
Sprawdź swoją wiedzę z zagadnień Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyli się Państwo, że: sortowanie topologiczne DFS w porządku postorder odkłada wierzchołki dopiero po przeanalizowaniu wszystkich ich zależności, oznaczanie trzema kolorami (WHITE/GREY/BLACK) wykrywa cykle za pomocą krawędzi wstecznych prowadzących do wierzchołków GREY, a odwrócenie stosu w porządku postorder daje poprawny porządek topologiczny. Następnie zastosujemy sortowanie topologiczne bezpośrednio do problemów Course Schedule I i II.
Często zadawane pytania
Czy lekcja „Sortowanie topologiczne DFS w kolejności postorder” jest bezpłatna?
Tak — pełny tekst „Sortowanie topologiczne DFS w kolejności postorder” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Sortowanie topologiczne DFS w kolejności postorder”?
Uruchamiać DFS i umieszczać każdy wierzchołek na stosie po pełnym odwiedzeniu jego sąsiadów, a następnie zdejmować elementy ze stosu, aby uzyskać poprawny porządek topologiczny Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „Sortowanie topologiczne DFS w kolejności postorder”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Algorytm Kahna: sortowanie topologiczne za pomocą BFS
- Sortowanie topologiczne DFS w kolejności postorder
- Course Schedule I i II
- Silnie spójne składowe za pomocą algorytmu Kosaraju