BFS (Breadth-First Search) - przeszukiwanie wszerz

BFS (Breadth-First Search) to algorytm przeszukiwania grafów, który przeszukuje graf warstwami, zaczynając od węzła początkowego i eksplorując wszystkie jego sąsiednie węzły przed przejściem do węzłów następnej warstwy. BFS jest szczególnie użyteczny do znajdowania najkrótszej ścieżki w grafach nieskierowanych, gdzie wszystkie krawędzie mają tę samą wagę.

Algorytm BFS

  1. Inicjalizacja:

    • Dodaj węzeł początkowy do kolejki.
    • Oznacz węzeł początkowy jako odwiedzony.

  2. Proces przeszukiwania:

    • Dopóki kolejka nie jest pusta:
      • Usuń węzeł z początku kolejki.
      • Przeszukaj sąsiednie węzły.
      • Dodaj nieodwiedzone sąsiednie węzły do kolejki i oznacz je jako odwiedzone.

Implementacja algorytmu BFS w programie Python

Poniżej znajduje się implementacja BFS dla grafu reprezentowanego jako lista sąsiedztwa.

from collections import deque
def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        vertex = queue.popleft()
        print(vertex, end=" ")
# Można zmienić na inną operację, np. zapisywanie do listy        
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
# Przykładowy graf jako lista sąsiedztwa
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
# Wywołanie BFS
bfs(graph, 'A')

przy czym deque to zoptymalizowana dwukierunkowa kolejka, która pozwala na szybkie dodawanie i usuwanie elementów z obu końców.

Przykład użycia

Graf

A - B - D
|   |
C   E
\ /
F

Wywołanie bfs(graph, 'A') przeszuka graf w następującej kolejności: A B C D E F.

BFS jest powszechnie używany w wielu zastosowaniach, takich jak:

  • znajdowanie najkrótszej ścieżki w grafie nieskierowanym.
  • rozwiązywanie problemów związanych z przeszukiwaniem w szerz, takich jak znajdowanie wszystkich połączeń w sieci.
  • algorytmy sztucznej inteligencji i grafiki komputerowej.

Komentarze