W głąb, czyli jak najdalej

Przeszukiwanie grafu w głąb i składowe spójności - Informatyka - liceum klasa 3, zakres rozszerzony (Python)

**Przeszukiwanie w głąb** (DFS) idzie od wierzchołka do pierwszego nieodwiedzonego sąsiada, od niego dalej, i dopiero gdy nie ma dokąd iść, **wraca** i próbuje innej drogi. Najprościej zapisać je rekurencyjnie: odwiedź wierzchołek, potem przeszukaj w głąb każdego nieodwiedzonego sąsiada.

graph = {0: [1, 2], 1: [0, 3], 2: [0, 3, 4], 3: [1, 2, 5], 4: [2, 5], 5: [3, 4], 6: []}
visited = []

def dfs(v):
    visited.append(v)
    for u in graph[v]:
        if u not in visited:
            dfs(u)

dfs(0)
print("kolejność w głąb:", visited)

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Informatyka - liceum klasa 3, zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.