Przeszukiwanie wszerz i odległości

Grafy: przeszukiwanie i najkrótsze drogi - Algorytmy: zakres rozszerzony (Python)

**Przeszukiwanie wszerz** (BFS) odwiedza wierzchołki warstwami: najpierw sąsiadów startu, potem ich sąsiadów i tak dalej. Używa kolejki. Odległość wierzchołka to odległość wierzchołka, z którego go odkryliśmy, plus 1, więc BFS znajduje najmniejszą liczbę krawędzi do każdego wierzchołka.

from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D", "E"],
    "D": ["B", "C", "F"],
    "E": ["C", "F"],
    "F": ["D", "E"],
}
distance = {"A": 0}
queue = deque(["A"])
while queue:
    vertex = queue.popleft()
    for neighbour in graph[vertex]:
        if neighbour not in distance:
            distance[neighbour] = distance[vertex] + 1
            queue.append(neighbour)
            print("odkryty", neighbour, "odległość", distance[neighbour])
print(distance)

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

Wszystkie lekcje kursu Algorytmy: zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.