Bfs

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.

bfs.gif

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);
           }
       }     
     }
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License