Mirosław Mortka
W przypadku przetwarzania grafów jedną z ważniejszych operacji jest systematyczne przechodzenie grafu w taki sposób, aby odwiedzić każdy wierzchołek oraz każdą krawędź jeden raz. Przechodzenie to może się odbywać w określonej kolejności wierzchołków. Dwie podstawowe metody przechodzenia grafów to BFS (ang. breadth first serach – przeszukiwanie wszerz) oraz DFS (ang. depth first serach – przeszukiwanie w głąb).
Algorytmu BFS używamy wszędzie tam, gdzie kolejność odwiedzania wierzchołków nie ma istotnego znaczenia lub chcemy uzyskać najkrótsze ścieżki w grafie nieważonym.
Algorytm przeszukiwania wszerz wymaga pełnego przetworzenia odwiedzanego wierzchołka przed obraniem kolejnego. Nieodwiedzonych dotąd sąsiadów przetwarzanego wierzchołka typujemy jako kolejnych kandydatów do odwiedzenia, umieszczając ich na końcu kolejki wierzchołków do przetworzenia oraz zaznaczając jako odwiedzonych. Po przetworzeniu w ten sposób wierzchołka wybieramy kolejny wierzchołek znajdujący się na początku kolejki. Operację powtarzamy do momentu, kiedy w kolejce nie pozostanie żaden wierzchołek.

Przykładowy kod programu w C++
// deklaracja tablicy złożonej z N_MAX wektorów
// na i-tej pozycji przechowuję w wektorze listę sąsiadów i-tego wierzchołka
vector <int> A[N_MAX]
// liczba wierzchołków n oraz liczba krawędzi k
int n, k;
// deklaracja tablicy złożonej z N_MAX elementów – informacja o przetworzeniu wierzchołka
bool odwiedzony[N_MAX]={0};
// deklaracja kolejki przechowującej kolejnych kandydatów do przetworzenia
queue <int> Q;
void bfs (int v)
{
//zaznacz wierzchołek v jako odwiedzony i dodaj go do kolejki wierzchołków do przetwarzania
odwiedzony [v] = 1;
Q.push(v);
//dopoki kolejka nie jest pusta
while ( !Q.empty() ) {
//pobierz pierwszy element z kolejki
v = Q.front(); Q.pop();
//odwiedź wszystkich nieodwiedzonych sąsiadów badanego wierzchołka
for ( int i=0; i<G[v].size(); i++){
int u = G[v][i];
//nieodwiedzonego sąsiada wstaw do kolejki i oznacz jako odwiedzony
if ( !odwiedzony[u] ) {
odwiedzony[u]=1;
Q.push(u);
}
}
}
}