Przeszukiwanie wszerz

Przeszukiwanie wszerz (ang. Breadth-first search, w skrócie BFS) – w informatyce algorytm przeszukiwania grafu używany do przechodzenia lub przeszukiwania drzewa lub grafu. Algorytm zaczyna od korzenia i odwiedza wszystkie połączone z nim węzły. Następnie odwiedza węzły połączone z tymi węzłami i tak dalej, aż do odnalezienia celu.

Pseudokod:

bfs (graf G, wierzchołek s)
{
    Q <- NIL

    for każdy wierzchołek v należący do G
    {
        kolor[v] <- BIAŁY
        odległość[v] <- NIL
        poprzednik[v] <- NIL
    }

    kolor[s] <- SZARY
    odległość[s] <- 0
    dodaj s do kolejki Q

    while Q nie jest pusta
    {
        v <- pobierz wierzchołek z kolejki Q

        for każdy wierzchołek u będący sąsiadem v
        {
            if kolor[u] = BIAŁY
            {
                kolor[u] <- SZARY
                odleglość[u] <- odleglosc[v] + 1
                poprzednik[u] <- v
                dodaj u do kolejki Q
            }
        }

        kolor[v] <- CZARNY
    }
}

Realizacja przeszukiwania wszerz w c++
Plik spakowany do formatu zip: bfs