Algorytm Kahna: sortowanie topologiczne za pomocą BFS
Obliczać stopnie wejściowe wszystkich wierzchołków, umieszczać w kolejce wierzchołki o zerowym stopniu wejściowym i przetwarzać kolejkę, aby uzyskać porządek topologiczny oraz wykrywać cykle
Algorytm Kahna: sortowanie topologiczne za pomocą BFS to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 1 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 DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Czym jest sortowanie topologiczne?
Sortowanie topologiczne skierowanego grafu acyklicznego (DAG) to takie uporządkowanie jego węzłów, w którym każda skierowana krawędź u → v oznacza, że u występuje w kolejności przed v. Reprezentuje ono poprawną kolejność wykonywania zadań z zależnościami, na przykład w systemach budowania, harmonogramowaniu kursów lub zarządzaniu pakietami. Tylko grafy acykliczne mają poprawne uporządkowania topologiczne; cykl sprawia, że jest to niemożliwe.
Algorytm Kahna: główna idea
Algorytm Kahna to podejście do sortowania topologicznego oparte na BFS. Kluczowa obserwacja jest następująca: węzeł o stopniu wejściowym równym 0 (bez wymagań wstępnych) może zostać umieszczony na początku uporządkowania. Po jego umieszczeniu należy go usunąć i zmniejszyć stopień wejściowy jego sąsiadów. W ten sposób pojawiają się nowe węzły o zerowym stopniu wejściowym. Należy powtarzać te kroki, aż wszystkie węzły zostaną umieszczone w kolejności albo zostanie wykryty cykl (pozostaną węzły o niezerowym stopniu wejściowym).
Obliczanie stopni wejściowych
Najpierw należy utworzyć listę sąsiedztwa i obliczyć stopień wejściowy (liczbę krawędzi wchodzących) każdego węzła. Węzły o stopniu wejściowym równym 0 są punktami początkowymi — nie mają żadnych zależności. Dla grafu o krawędziach [(0,1),(0,2),(1,3),(2,3)] stopnie wejściowe wynoszą: 0→0, 1→1, 2→1, 3→2. Tylko węzeł 0 ma początkowo stopień wejściowy równy 0.
from collections import deque, defaultdict
def compute_in_degree(n, edges):
in_degree = [0] * n
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
return graph, in_degree
graph, ind = compute_in_degree(4, [(0,1),(0,2),(1,3),(2,3)])
print('In-degrees:', ind) # [0, 1, 1, 2]Implementacja algorytmu Kahna
Należy umieścić wszystkie węzły o zerowym stopniu wejściowym w kolejce. Przetwarzając każdy węzeł, dodaj go do wyniku, a następnie zmniejsz stopień wejściowy każdego sąsiada i dodaj go do kolejki, jeśli jego stopień osiągnie 0. Jeśli lista wynikowa zawiera mniej węzłów niż graf, istnieje cykl — niektórych węzłów nie można było usunąć z kolejki.
from collections import deque, defaultdict
def kahn_topological_sort(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque(i for i in range(n) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
if len(order) == n:
return order # valid topological sort
return [] # cycle detected
print(kahn_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))Wykrywanie cykli za pomocą algorytmu Kahna
Algorytm Kahna zapewnia automatyczne wykrywanie cykli: jeśli len(order) < n, niektóre węzły nigdy nie zostały dodane do kolejki, ponieważ ich stopień wejściowy nie osiągnął 0 — należą one do cyklu. Jest to prostsze niż utrzymywanie tablicy odwiedzin oznaczonej kolorami. Aby zasygnalizować istnienie cyklu, należy zwrócić pustą listę.
# Cyclic graph: 0->1->2->0
edges_cycle = [(0,1),(1,2),(2,0)]
result = kahn_topological_sort(3, edges_cycle)
print(result) # [] (cycle detected)
# Acyclic graph
edges_dag = [(0,1),(1,2)]
result = kahn_topological_sort(3, edges_dag)
print(result) # [0, 1, 2]Złożoność czasowa i pamięciowa
Algorytm Kahna przetwarza każdy węzeł raz (każdy jest raz usuwany z kolejki) oraz każdą krawędź raz (jej stopień wejściowy jest zmniejszany raz). Złożoność czasowa wynosi O(V + E). Złożoność pamięciowa to O(V + E) na listę sąsiedztwa i tablicę stopni wejściowych oraz dodatkowo O(V) na kolejkę. Jest to rozwiązanie optymalne — aby utworzyć poprawne uporządkowanie, trzeba przynajmniej odczytać wszystkie węzły i krawędzie.
Leksikograficznie najmniejsze uporządkowanie topologiczne
Algorytm Kahna z kopcem minimum zamiast kolejki tworzy leksykograficznie najmniejsze uporządkowanie topologiczne. Należy zastąpić deque przez heapq: dodawać (node) i zawsze najpierw przetwarzać najmniejszy dostępny węzeł. Gwarantuje to leksykograficznie najmniejsze poprawne uporządkowanie spośród wszystkich możliwych sortowań topologicznych.
import heapq
from collections import defaultdict
def kahn_lex_order(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
heap = [i for i in range(n) if in_degree[i] == 0]
heapq.heapify(heap)
order = []
while heap:
node = heapq.heappop(heap)
order.append(node)
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
heapq.heappush(heap, nxt)
return order if len(order) == n else []
print(kahn_lex_order(6, [(5,2),(5,0),(4,0),(4,1),(2,3),(3,1)]))Zastosowanie: Course Schedule I
Course Schedule (LeetCode 207): mając n kursów i wymagania wstępne, należy sprawdzić, czy można ukończyć wszystkie kursy. Wymagania wstępne należy zamodelować jako skierowane krawędzie i sprawdzić, czy istnieje poprawne sortowanie topologiczne (czyli czy nie ma cyklu). Zwróć True, jeśli algorytm Kahna tworzy uporządkowanie o długości n, oraz False, jeśli wykryty zostanie cykl.
from collections import deque, defaultdict
def canFinish(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites: # b must be taken before a
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
count = 0
while queue:
node = queue.popleft()
count += 1
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return count == numCourses
print(canFinish(2, [[1,0]])) # True
print(canFinish(2, [[1,0],[0,1]])) # False (cycle)Zastosowanie: Course Schedule II
Course Schedule II (LeetCode 210): należy zwrócić rzeczywistą kolejność, w której trzeba odbyć kursy. Rozwiązanie jest takie samo jak powyżej, ale zamiast wartości logicznej należy zwrócić listę order. Jeśli istnieje cykl, należy zwrócić pustą listę. Odpowiedzią jest bezpośrednio wynik algorytmu Kahna.
from collections import deque, defaultdict
def findOrder(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))Równoległe planowanie zadań
Bardziej zaawansowane zastosowanie polega na znalezieniu minimalnej liczby „rund” potrzebnych do wykonania zadań, jeśli zadania bez zależności mogą być uruchamiane równolegle. Należy przetwarzać algorytm Kahna poziomami, podobnie jak BFS poziomami: dodać do kolejki wszystkie węzły o zerowym stopniu wejściowym, przetworzyć całą bieżącą kolejkę jako jedną rundę, a następnie dodać nowo udostępnione węzły jako następną rundę. Na koniec należy policzyć rundy.
from collections import deque, defaultdict
def min_rounds(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque(i for i in range(n) if in_degree[i] == 0)
rounds = 0
while queue:
rounds += 1
for _ in range(len(queue)): # process current level
node = queue.popleft()
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return rounds
print(min_rounds(4, [(0,2),(1,2),(2,3)])) # 3Sortowanie topologiczne i programowanie dynamiczne w DAG-ach
Sortowanie topologiczne umożliwia zastosowanie programowania dynamicznego w DAG-ach: należy przetwarzać węzły w kolejności topologicznej, dzięki czemu podczas obliczania dp[v] wszystkie wartości dp[u] dla poprzedników są już ostateczne. Łączy to sortowanie topologiczne z programowaniem dynamicznym w problemach takich jak najdłuższa ścieżka w DAG-u, minimalny koszt dotarcia do wszystkich węzłów czy maksymalny zysk z łańcucha zależności. Uporządkowanie gwarantuje, że wartość programowania dynamicznego każdego węzła zostanie obliczona dokładnie raz, po przetworzeniu wszystkich jego zależności.
from collections import deque, defaultdict
def longest_path_dag(V, edges):
graph = defaultdict(list)
in_degree = [0] * V
for u, v, w in edges:
graph[u].append((v, w))
in_degree[v] += 1
queue = deque(i for i in range(V) if in_degree[i] == 0)
dp = [0] * V
while queue:
u = queue.popleft()
for v, w in graph[u]:
dp[v] = max(dp[v], dp[u] + w)
in_degree[v] -= 1
if in_degree[v] == 0: queue.append(v)
return max(dp)
print(longest_path_dag(4, [(0,1,3),(0,2,2),(1,3,4),(2,3,1)])) # 7Szybkie sprawdzenie
Proszę sprawdzić swoją znajomość zagadnień dotyczących struktur danych i algorytmów — przygotowania do rozmów kwalifikacyjnych z programowania — omówionych w tej lekcji.
Podsumowanie lekcji
W tej lekcji poznali Państwo: algorytm Kahna oblicza sortowanie topologiczne przez iteracyjne usuwanie węzłów o zerowym stopniu wejściowym za pomocą BFS, wykrywanie cykli odbywa się automatycznie — jeśli len(order) < n, istnieje cykl, a także że zastąpienie kolejki kopcem minimum daje leksykograficznie najmniejsze uporządkowanie topologiczne. Następnie poznamy sortowanie topologiczne oparte na DFS i porządku post-order jako alternatywę dla algorytmu Kahna.
Często zadawane pytania
Czy lekcja „Algorytm Kahna: sortowanie topologiczne za pomocą BFS” jest bezpłatna?
Tak — pełny tekst „Algorytm Kahna: sortowanie topologiczne za pomocą BFS” 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 DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Algorytm Kahna: sortowanie topologiczne za pomocą BFS”?
Obliczać stopnie wejściowe wszystkich wierzchołków, umieszczać w kolejce wierzchołki o zerowym stopniu wejściowym i przetwarzać kolejkę, aby uzyskać porządek topologiczny oraz wykrywać cykle Ćwiczysz DSA 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ąć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA 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 1 z 4.
Ile czasu zajmuje lekcja „Algorytm Kahna: sortowanie topologiczne za pomocą BFS”?
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 DSA Interview Prep?
Tak. Każda lekcja DSA 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