Wszerz, czyli warstwami

Przeszukiwanie grafu wszerz - Informatyka - liceum klasa 3, zakres rozszerzony (Python)

**Przeszukiwanie wszerz** (BFS) zaczyna od wierzchołka startowego, potem odwiedza wszystkich jego sąsiadów, potem sąsiadów sąsiadów i tak dalej, **warstwami**. Wierzchołki czekają w **kolejce**, a zbiór `visited` pilnuje, żeby żaden nie trafił do kolejki dwa razy.

from collections import deque

graph = {0: [1, 2], 1: [0, 3], 2: [0, 3, 4], 3: [1, 2, 5], 4: [2, 5], 5: [3, 4], 6: []}
visited = {0}
queue = deque([0])
order = []
while queue:
    v = queue.popleft()
    order.append(v)
    for u in graph[v]:
        if u not in visited:
            visited.add(u)
            queue.append(u)
    print("odwiedzam", v, "kolejka:", list(queue))
print("kolejność:", order)

Ł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.