BFS (breadth-first search) i DFS (depth-first search) to dwa fundamentalne wzorce przeszukiwania drzew i grafów na rozmowie technicznej. BFS odwiedza węzły poziomami (najpierw root, potem wszystkie sąsiady, potem sąsiadów sąsiadów), używając kolejki FIFO. DFS schodzi w głąb jednej gałęzi przed wycofaniem się, używając stosu LIFO (rekurencyjnie lub jawnie).
W tym artykule pokazuję oba wzorce na drzewach i grafach: BFS dla najkrótszej ścieżki unweighted, DFS dla cycle detection i topological sort, kiedy która technika wygrywa, i klasyczne pułapki (brak visited w grafie z cyklami, mylenie call stack z explicit stack). Implementacje w Pythonie dla zwięzłości — wzorce są language-agnostic.
Pozostaję w obrębie podstawowych BFS/DFS. Algorytmy ważone (Dijkstra, A*) i zaawansowane traversale (Tarjan SCC) to powiązane ale osobne tematy.
Czym jest BFS i DFS — definicje + ASCII
BFS, czyli Breadth-First Search, i DFS, czyli Depth-First Search, to podstawowe wzorce przeszukiwania drzew i grafów. BFS odwiedza strukturę poziomami, używając kolejki FIFO. DFS schodzi jak najgłębiej jedną gałęzią, używając stosu LIFO: jawnej listy albo naturalnego call stacka rekurencji. Dla grafu oba wzorce mają złożoność O(V + E), gdzie V to wierzchołki, a E krawędzie. Dla drzewa jest to O(N), bo drzewo ma N węzłów i N - 1 krawędzi.
Intuicja jest prosta: BFS zachowuje się jak fala rozchodząca się od startu, a DFS jak zejście korytarzem do końca i cofanie się. Na tym samym drzewie kolejność może wyglądać tak:
A
/ \
B C
/ \ \
D E F
BFS: A, B, C, D, E, F
DFS preorder: A, B, D, E, C, F
Na rozmowie rekrutacyjnej sygnałem jest pytanie o „przejście po strukturze”, „najbliższy element”, „poziomy”, „ścieżkę”, „cykl” albo „zależności”. BFS i DFS są często nie celem samym w sobie, lecz szkieletem rozwiązania: do BFS dokładasz dystans, do DFS stan rekurencji, visited, wykrywanie cyklu lub wynik z poddrzewa.
tree = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"]}
bfs_order = ["A", "B", "C", "D", "E", "F"]
dfs_order = ["A", "B", "D", "E", "C", "F"]
print(bfs_order)
# expected_output: ['A', 'B', 'C', 'D', 'E', 'F']
print(dfs_order)
# expected_output: ['A', 'B', 'D', 'E', 'C', 'F']
Trace step-by-step: startujesz w A. BFS wkłada dzieci B i C do kolejki, więc odwiedza oba węzły poziomu 1 przed zejściem do D, E, F. DFS wybiera B, potem natychmiast schodzi do D, wraca do E, dopiero później przechodzi do gałęzi C.
Pułapka: mylenie „odwiedzania” z „dodaniem do struktury pomocniczej”. W BFS w grafach często oznaczasz wierzchołek jako odwiedzony już przy dodaniu do kolejki, żeby nie włożyć go kilka razy. W DFS iteracyjnym możesz oznaczać przy zdjęciu ze stosu, ale wtedy musisz obsłużyć duplikaty.
BFS — queue, poziomami
BFS to wzorzec, w którym trzymasz front przeszukiwania w kolejce FIFO. W Pythonie standardowym wyborem jest collections.deque, bo popleft() usuwa element z lewej strony w czasie O(1). Lista z pop(0) działa semantycznie podobnie, ale przesuwa elementy i jest gorszym wyborem.
Intuicja: kolejka pilnuje sprawiedliwej kolejności. Najpierw przetwarzasz wszystko, co jest najbliżej startu, potem wszystko o jeden krok dalej. Przejście poziomami wygląda tak:
level 0: A
/ \
level 1: B C
/ \ / \
level 2: D E F G
queue:
[A] -> [B, C] -> [C, D, E] -> [D, E, F, G]
Sygnały rozpoznawcze: „level-order traversal”, „minimum number of moves”, „shortest path in unweighted graph”, „nearest exit”, „nodes at distance k”, „rotting oranges”, „word ladder”. Jeśli koszt każdego przejścia jest taki sam, BFS daje najkrótszą ścieżkę liczoną w liczbie krawędzi.
from collections import deque
tree = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": [], "E": [], "F": []}
queue = deque(["A"])
order = []
while queue:
node = queue.popleft()
order.append(node)
queue.extend(tree[node])
print(order)
# expected_output: ['A', 'B', 'C', 'D', 'E', 'F']
Trace step-by-step: queue = [A], zdejmujesz A, dodajesz B, C. Potem zdejmujesz B, dodajesz D, E. Potem zdejmujesz C, dodajesz F. Dopiero po całym poziomie 1 zaczynasz poziom 2. To jest sedno BFS.
Pułapka: użycie list.pop(0) w kodzie rekrutacyjnym. Dla małego przykładu przejdzie, ale pokazuje brak precyzji w doborze struktury. BFS wymaga kolejki FIFO; w Pythonie najczytelniejsze jest deque z popleft().
DFS rekurencyjny — call stack
DFS rekurencyjny to przejście w głąb, w którym stos wywołań funkcji przechowuje ścieżkę od korzenia do aktualnego węzła. Nie musisz ręcznie tworzyć stosu: każde wywołanie funkcji odkłada na call stacku lokalne zmienne i miejsce powrotu. To naturalny model dla drzew.
Intuicja: funkcja mówi „rozwiąż moje lewe poddrzewo, potem prawe, potem oddaj wynik”. Dlatego DFS pasuje do problemów rekurencyjnych: walidacja BST, path sum, wysokość drzewa, średnica drzewa, porównanie poddrzew, liczenie wartości w poddrzewie.
call dfs(A)
call dfs(B)
call dfs(D)
return D
call dfs(E)
return E
return B
call dfs(C)
call dfs(F)
return F
return A
Sygnał na rozmowie: problem ma lokalną definicję rekurencyjną. Jeśli odpowiedź dla węzła zależy od odpowiedzi dla dzieci, DFS jest pierwszym kandydatem. Dla drzewa bez cykli nie potrzebujesz visited, bo każdy węzeł ma jednego rodzica i nie wracasz do niego przez inną krawędź.
tree = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": [], "E": [], "F": []}
order = []
def dfs(node):
order.append(node)
for child in tree[node]:
dfs(child)
dfs("A")
print(order)
# expected_output: ['A', 'B', 'D', 'E', 'C', 'F']
Trace step-by-step: dfs("A") zapisuje A, potem woła dfs("B"). B woła D, D nie ma dzieci i wraca. Następnie E wraca. Dopiero po zakończeniu całego B funkcja przechodzi do C i F.
Pułapka: brak warunku bazowego albo zbyt głęboka rekurencja. W drzewie warunkiem bazowym bywa None albo pusta lista dzieci. W Pythonie bardzo głębokie drzewo może przekroczyć limit rekurencji, nawet jeśli algorytm logicznie jest poprawny.
DFS iteracyjny — explicit stack
DFS iteracyjny robi to samo co rekurencyjny, ale zamiast call stacka używa jawnego stosu LIFO, zwykle listy z append() i pop(). To przydatne, gdy chcesz uniknąć limitu rekurencji, kontrolować stan ręcznie albo przetwarzać graf bez ryzyka przepełnienia stosu wywołań.
Intuicja: stos trzyma węzły, do których masz wrócić. Ostatnio dodany element jest zdjęty jako pierwszy, więc algorytm idzie w głąb. Jeśli chcesz zachować kolejność jak w rekurencyjnym DFS od lewej do prawej, często dodajesz dzieci w odwróconej kolejności.
tree children: A -> B, C
stack [A]
pop A, push C, B
stack [C, B]
pop B, push E, D
stack [C, E, D]
pop D
Sygnały rozpoznawcze: bardzo głęboka struktura, środowisko bez wygodnej rekurencji, potrzeba kontroli nad momentem oznaczania visited, albo zadanie, w którym stan ramki rekurencji trzeba jawnie rozszerzyć, np. o etap wejścia i wyjścia z węzła.
tree = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": [], "E": [], "F": []}
stack = ["A"]
order = []
while stack:
node = stack.pop()
order.append(node)
stack.extend(reversed(tree[node]))
print(order)
# expected_output: ['A', 'B', 'D', 'E', 'C', 'F']
Trace step-by-step: startujesz ze stosem [A]. Zdejmujesz A, dodajesz C, potem B, żeby B było na górze. Zdejmujesz B, dodajesz E, potem D. Zdejmujesz D, następnie E, potem wracasz do C i F.
Pułapka: dodanie dzieci w naturalnej kolejności i oczekiwanie identycznego wyniku jak z rekurencji. Stos odwraca kolejność, bo ostatni dodany element wychodzi pierwszy. To nie zawsze psuje poprawność, ale może zmienić trace i wynik, jeśli zadanie zależy od kolejności.
BFS vs DFS na drzewie — kiedy która
Na drzewie BFS i DFS odwiedzą wszystkie węzły w czasie O(N), ale dają inne własności. BFS jest dobry, gdy ważny jest poziom, minimalna liczba krawędzi od korzenia albo pierwszy najpłytszy wynik. DFS jest dobry, gdy problem ma strukturę „policz coś z poddrzewa” albo „sprawdź warunek wzdłuż ścieżki”.
Intuicja: BFS widzi drzewo warstwami, DFS widzi je ścieżkami. Jeśli pytanie brzmi „jaki jest pierwszy węzeł na najmniejszej głębokości?”, BFS trafia naturalnie. Jeśli pytanie brzmi „czy istnieje ścieżka od korzenia do liścia o sumie X?”, DFS naturalnie niesie akumulowany stan ścieżki.
5
/ \
3 8
/ \ \
1 4 9
BFS levels: [5], [3, 8], [1, 4, 9]
DFS path: 5 -> 3 -> 1, then backtrack
Sygnał rozpoznawczy: słowa „minimum depth”, „level average”, „right side view” sugerują BFS. Słowa „valid BST”, „path sum”, „same tree”, „subtree”, „lowest common ancestor” zwykle sugerują DFS. Na drzewie nie ma cykli, więc visited nie jest potrzebny, jeśli masz klasyczne referencje rodzic-dziecko.
tree = {5: [3, 8], 3: [1, 4], 8: [9], 1: [], 4: [], 9: []}
def has_path_sum(node, target):
if not tree[node]:
return node == target
return any(has_path_sum(child, target - node) for child in tree[node])
print(has_path_sum(5, 9))
# expected_output: True
Trace step-by-step: startujesz w 5 i szukasz sumy 9. Schodzisz do 3, zostaje 4. Schodzisz do 1, zostaje 1, liść 1 spełnia warunek. DFS może natychmiast zwrócić True, bez oglądania całego poziomu.
Pułapka: wybór BFS tylko dlatego, że „szuka najkrótszej ścieżki”. W drzewie najkrótsza ścieżka od korzenia do najbliższego liścia faktycznie pasuje do BFS, ale walidacja własności drzewa, sumy ścieżek i problemy poddrzew zwykle są prostsze jako DFS.
BFS na grafie — visited set i najkrótsza ścieżka unweighted
BFS na grafie to BFS z obowiązkowym visited set, jeśli graf może mieć cykle. Startujesz z wierzchołka, wkładasz go do kolejki FIFO i odwiedzasz sąsiadów poziomami. W grafie nieważonym BFS daje najkrótszą ścieżkę liczoną w liczbie krawędzi, ponieważ pierwszy raz docierasz do wierzchołka najmniejszą możliwą liczbą kroków.
Intuicja: wszystkie ścieżki długości 1 są sprawdzane przed ścieżkami długości 2, wszystkie długości 2 przed długościami 3. Dlatego jeśli cel zostanie odkryty, żadna krótsza ścieżka nie mogła zostać pominięta.
A -- B -- D
| |
C -- E
BFS from A:
distance 0: A
distance 1: B, C
distance 2: D, E
Sygnały rozpoznawcze: graf nieważony, minimalna liczba przejść, „fewest transformations”, „nearest zero”, „minimum knight moves”, „shortest path in maze” bez kosztów pól. Wtedy trzymasz także distance albo parent, jeśli trzeba odtworzyć trasę.
from collections import deque
graph = {"A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "E"], "D": ["B"], "E": ["B", "C"]}
queue = deque([("A", 0)])
visited = {"A"}
while queue:
node, dist = queue.popleft()
if node == "D":
print(dist)
# expected_output: 2
break
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, dist + 1))
Trace step-by-step: A ma dystans 0. Do kolejki trafiają B i C z dystansem 1. Zdejmujesz B, odkrywasz D i E z dystansem 2. Gdy zdejmiesz lub odkryjesz D, wynik 2 jest najkrótszy w liczbie krawędzi.
Pułapka: brak visited w grafie z cyklem. W przykładzie A prowadzi do B, a B z powrotem do A. Bez visited kolejka będzie stale dostawać już widziane wierzchołki, co może prowadzić do nieskończonej pętli albo eksplozji duplikatów.
DFS na grafie — visited set, cycle detection, topological sort
DFS na grafie używa stosu LIFO lub rekurencji, ale w odróżnieniu od drzewa musi kontrolować odwiedzone wierzchołki. W grafie z cyklami visited set jest kluczowy, żeby nie wracać bez końca do tych samych miejsc. DFS jest też bazą do wykrywania cykli i sortowania topologicznego w grafach skierowanych.
Intuicja: DFS widzi aktywną ścieżkę. Jeśli podczas zejścia trafisz na wierzchołek, który już jest na aktualnym stosie rekurencji, znalazłeś cykl. Jeśli wierzchołek jest już w pełni przetworzony, nie musisz go liczyć drugi raz.
A -> B -> C
^ |
|____|
visiting B, then C, then edge C -> B
B is still on recursion stack: cycle
Sygnały rozpoznawcze: „detect cycle”, „can finish courses”, „dependency order”, „topological sort”, „connected components”, „clone graph”. DFS jest mocny, gdy ważna jest relacja przodek-potomek w trakcie przejścia, a nie minimalna liczba kroków.
graph = {"A": ["B"], "B": ["C"], "C": ["B"]}
visiting, visited = set(), set()
def has_cycle(node):
if node in visiting:
return True
if node in visited:
return False
visiting.add(node)
found = any(has_cycle(next_node) for next_node in graph[node])
visiting.remove(node)
visited.add(node)
return found
print(has_cycle("A"))
# expected_output: True
Trace step-by-step: zaczynasz w A, dodajesz A do visiting, potem B, potem C. Z C widzisz krawędź do B. B nadal jest w visiting, czyli leży na aktywnej ścieżce rekurencji. To oznacza cykl skierowany.
Pułapka: użycie tylko jednego visited do wykrywania cyklu w grafie skierowanym. Sam fakt, że wierzchołek był kiedyś odwiedzony, nie musi oznaczać cyklu. Potrzebujesz rozróżnić stan „aktualnie na stosie” od „już całkowicie przetworzony”.
Sygnały rozpoznawcze: kiedy BFS, kiedy DFS
Wzorzec BFS wybierasz, gdy rozwiązanie zależy od odległości poziomami albo minimalnej liczby ruchów w grafie nieważonym. Wzorzec DFS wybierasz, gdy rozwiązanie zależy od zejścia ścieżką, poddrzewa, rekurencyjnej walidacji albo wykrywania zależności. To nie jest kwestia gustu, tylko własności danych.
Intuicja: na rozmowie często najpierw rozpoznajesz „kształt” problemu, dopiero potem piszesz kod. BFS odpowiada na pytanie „co jest najbliżej?”. DFS odpowiada na pytanie „co wynika z tej gałęzi?”. Mapping wygląda tak:
minimum edges / levels -> BFS
tree validation / path state -> DFS
unweighted shortest path -> BFS
cycle in directed graph -> DFS
topological order -> DFS
Sygnały problem → algorytm: level-order traversal → BFS. minimum depth → BFS. shortest path in unweighted graph → BFS. rotting oranges → multi-source BFS. valid BST → DFS. path sum → DFS. subtree of another tree → DFS. course schedule → DFS albo BFS z indegree, ale klasyczny cykl w grafie skierowanym często omawia się przez DFS.
hints = {
"minimum moves": "BFS",
"level order": "BFS",
"path sum": "DFS",
"cycle detection": "DFS",
"subtree": "DFS",
}
print(hints["minimum moves"])
# expected_output: BFS
print(hints["path sum"])
# expected_output: DFS
Trace step-by-step: czytasz treść. Jeśli pojawia się „minimum”, pytasz: czy wszystkie krawędzie mają ten sam koszt? Jeśli tak, BFS. Jeśli pojawia się „dla każdego poddrzewa” albo „ścieżka od korzenia do liścia”, wybierasz DFS. Jeśli pojawia się graf z cyklami, od razu planujesz visited.
Pułapka: zapamiętywanie listy zadań bez rozumienia mechanizmu. „Shortest path” nie zawsze oznacza BFS, bo BFS działa jako najkrótsza ścieżka tylko w grafie nieważonym albo równokosztowym. „Graph traversal” nie zawsze oznacza DFS, bo pytanie o najbliższy wynik zwykle faworyzuje BFS.
Kiedy NIE BFS/DFS — anti-przykład
BFS i DFS nie są uniwersalnymi algorytmami optymalizacji. Jeśli graf ma wagi, a pytanie dotyczy najtańszej ścieżki, zwykły BFS nie wystarcza, bo minimalna liczba krawędzi nie musi oznaczać minimalnego kosztu. DFS też nie gwarantuje optymalnej ścieżki, bo może wejść głęboko w drogą gałąź.
Intuicja: BFS liczy kroki, nie sumę wag. Jeśli jedna trasa ma jedną krawędź o koszcie 100, a druga ma dwie krawędzie o kosztach 1 + 1, BFS wybierze trasę jednokrawędziową jako krótszą w liczbie krawędzi, choć kosztowo jest gorsza.
A --100--> B
A --1--> C --1--> B
BFS by edges: A -> B, cost 100
Cheaper path: A -> C -> B, cost 2
Sygnały rozpoznawcze, że nie powinieneś używać zwykłego BFS/DFS jako głównego rozwiązania: krawędzie mają różne koszty, pola planszy mają różne opłaty, pytanie mówi o minimalnym czasie, cenie, ryzyku albo energii. Wtedy wspominasz, że potrzebny jest algorytm dla grafu ważonego, na przykład Dijkstra dla nieujemnych wag. To tylko kontrast, nie główny temat.
paths = {
("A", "B"): 100,
("A", "C", "B"): 2,
}
bfs_choice = ("A", "B")
best_choice = min(paths, key=paths.get)
print(paths[bfs_choice])
# expected_output: 100
print(best_choice)
# expected_output: ('A', 'C', 'B')
Trace step-by-step: BFS z A widzi B jako sąsiada na dystansie jednej krawędzi, więc uzna, że dotarł najkrótszą ścieżką w sensie liczby krawędzi. Nie analizuje, że krawędź kosztuje 100. Trasa przez C ma dwie krawędzie, więc BFS zobaczy ją później, mimo że koszt całkowity to tylko 2.
Pułapka: powiedzenie „BFS znajduje najkrótszą ścieżkę” bez dopowiedzenia warunku. Precyzyjna wersja brzmi: BFS znajduje najkrótszą ścieżkę w grafie nieważonym, liczoną liczbą krawędzi. Przy wagach potrzebujesz innego narzędzia.
Źródła: Wikipedia: Breadth-first search, Wikipedia: Depth-first search, Python docs: collections.deque, Real Python: queues, BFS i DFS.
Najczęstsze błędy
Brak visited w BFS/DFS na grafie z cyklami. Algorytm dodaje już odwiedzone wierzchołki w kółko — pętla nieskończona lub stack overflow. Mechanizm błędu: A → B → A powoduje że A ląduje w queue/stack drugi raz; bez visited set algorytm nie wykrywa że już tam był. Naprawa: visited = set(), if neighbor not in visited: przed dodaniem do queue/stack. Drzewo (bez cykli) działa bez visited, graf zwykle wymaga.
BFS dla najkrótszej ścieżki w grafie ważonym. BFS daje najkrótszą ścieżkę liczoną w liczbie krawędzi (każda krawędź = 1). Dla wag ≠ 1 nie działa — ścieżka z mniej krawędzi może mieć większą sumarą wagę. Mechanizm błędu: A → B (waga 10), A → C → B (wagi 1+1=2) — BFS odwiedzi B przez bezpośrednią krawędź A→B, ignoruje krótszą wagowo. Naprawa: dla weighted graph użyj Dijkstra (priority queue + greedy).
DFS rekurencyjny na bardzo głębokim drzewie. Python ma domyślny sys.getrecursionlimit() = 1000. Drzewo o głębokości 10⁴ rzuca RecursionError. Mechanizm: każde wywołanie tworzy ramkę stosu, limit chroni przed C stack overflow. Naprawa: konwertuj na iteracyjny DFS z explicit stack — szczegóły Rekurencja vs Iteracja. Limit można podnieść sys.setrecursionlimit(10000), ale to obejście, nie rozwiązanie.
list.pop(0) jako kolejka w BFS. Wynik logicznie poprawny, ale każde pop(0) to O(n) (przesunięcie wszystkich elementów). Total dla n operacji: O(n²) zamiast O(n). Mechanizm błędu: dla 10⁵ węzłów algorytm działa 10¹⁰ kroków zamiast 10⁵. Naprawa: from collections import deque; queue.popleft() w O(1) — szczegóły Stos i Kolejka.
DFS iteracyjny: dodanie dzieci na stack w złej kolejności. Stack to LIFO — ostatnie wrzucone wychodzi pierwsze. Dla preorder z lewa-do-prawa wrzucasz prawe dziecko PRZED lewym, żeby lewe wyszło pierwsze. Mechanizm błędu: dla drzewa 1 → (2, 3) kolejność „push 2, push 3" daje [1, 3, 2] zamiast [1, 2, 3]. Naprawa: dla DFS preorder iteracyjnie zawsze stack.append(right) przed stack.append(left).
FAQ
BFS czy DFS — jak wybrać na rozmowie?
Pytaj o co algorytm ma znaleźć. Najkrótsza ścieżka w unweighted graph / level-order traversal / „najmniejsza liczba kroków" → BFS. Walidacja niezmienników rekurencyjnych / path sum / cycle detection / topological sort → DFS. Jeśli możesz — pisz oba i wytłumacz wybór. Często rozmówca akceptuje rozumowanie nawet jeśli wybierzesz nieoptymalny.
Czemu BFS zawsze daje najkrótszą ścieżkę unweighted?
Bo odwiedza węzły w kolejności rosnącej odległości od startu. Pierwszy poziom = odległość 1, drugi = odległość 2, itd. Pierwsze trafienie na cel oznacza minimalną liczbę krawędzi. DFS może znaleźć cel przez długą gałąź zanim sprawdzi krótszą — bez gwarancji minimum. Dla weighted graph BFS przestaje gwarantować minimum (potrzeba Dijkstra).
DFS rekurencyjny czy iteracyjny — kiedy który?
Rekurencyjny gdy: drzewo niskiej-średniej głębokości (< 1000), kod krótki i czytelny, problem naturalnie rekurencyjny (validate BST, max depth, path sum). Iteracyjny gdy: bardzo głębokie struktury (przekraczające sys.getrecursionlimit()), kontrola pamięci (explicit stack pozwala batch'ować, persistować), debugowanie (jawne kroki). Większość zadań rekrutacyjnych = rekurencyjny.
Jak BFS/DFS poradzą sobie z disconnected graph?
BFS/DFS startując od jednego wierzchołka odwiedzą tylko jego komponentę spójną. Dla disconnected graph: pętla po wszystkich wierzchołkach, jeśli nie odwiedzony — start nowy BFS/DFS. Wzorzec: for v in graph: if v not in visited: bfs(v). To podstawa znajdowania liczby komponent spójnych.
Czy BFS może być rekurencyjny?
Technicznie tak, ale rzadko praktyczne. BFS naturalnie używa kolejki, a rekurencja używa stosu wywołań — implementacja BFS rekurencyjnie wymaga jawnego przekazywania queue jako parametru, co traci elegancję. Standardowy zapis BFS to pętla while + deque. Jeśli ktoś prosi o rekurencyjny BFS, pewnie testuje czy rozumiesz że to nienaturalne.
Topological sort — który algorytm?
DFS jest klasyczny: rekurencyjnie odwiedzaj sąsiadów, dodawaj wierzchołek do stacku gdy wszyscy potomkowie odwiedzeni. Final reversed(stack) daje topological order. Alternatywa: Kahn's algorithm używa BFS z indegree counting — start od wierzchołków z indegree=0, redukuj indegree sąsiadów. Oba O(V+E), oba akceptowalne na rozmowie.
Powiązane tematy
- Drzewa Binarne — Wzorzec Rekurencyjny — DFS naturalnie pasuje do drzew (pre/in/post-order); BFS dla level-order traversal.
- Stos i Kolejka — LIFO i FIFO — DFS = stack LIFO (jawnie lub jako call stack), BFS = queue FIFO (
collections.deque). - Rekurencja vs Iteracja — DFS rekurencyjny vs iteracyjny z explicit stack; trade-off czytelność vs kontrola głębokości.
Sprawdź swoją wiedzę quizem
Przerób ten artykuł w 15-pytaniowy quiz testujący BFS vs DFS, queue vs stack, najkrótszą ścieżkę i cycle detection: https://odpytywarka.pl/q/aytf5v.
Masz własne notatki na rozmowę? Wgraj PDF lub wklej tekst na stworz-quiz-z-pdf — pierwsze 3 strony PDF i 15 pytań jednokrotnego wyboru za darmo, generowanie 30-60 sekund.
Źródła
- Breadth-first search — Wikipedia — formalna definicja, złożoność, zastosowania
- Depth-first search — Wikipedia — DFS, topological sort, cycle detection
- Python
collections.deque—O(1)kolejka FIFO dla BFS - Topological sorting — Wikipedia — Kahn's algorithm i DFS-based