Dydaktyka‎ > ‎Notatki‎ > ‎

BFS - przeglądanie grafu wszerz

opublikowane: 26 lut 2015, 08:32 przez Rafał Nowak   [ zaktualizowane 26 lut 2015, 08:36 ]
Niech dany będzie graf nieskierowany, który ma n wierzchołków i m krawędzi.

Graf będziemy pamiętali w komputerze za pomocą listy sąsiedztwa, tzn. dla każdego wierzchołka u=1,2,...,n będziemy pamiętali listę (właściwie to wektor z biblioteki STL) jego sąsiadów.
W poniższym programie zmienna G jest tablicą wektorów z biblioteki STL. Z góry zakładamy, że graf nie będzie miał więcej niż 106 wierzchołków.

  • Algorytm BFS(a) przegląda graf zaczynając od wierzchołka a.
  • W algorytmie wykorzystuje się kolejkę, do przechowywania wierzchołków, które należy odwiedzić.
  • Każdy wierzchołek, który trafia do kolejki jest oznaczany; w programie nadajemy mu wartość col[u] = true.
  • Algorytm dodatkowo wyznacza tablicę dist[u], która przechowuje informacje o odległościach odwiedzonych wierzchołków od wierzchołka początkowego a.
Kod w języku C++ z wykorzystaniem wektorów (vector) i kolejki (queue) z biblioteki STL.
#include<vector>
#include<queue>
using namespace std;

vector<int> G[1000001];
bool col[1000001];
int dist[1000001];

// Przeglądanie grafu wszerz
// Obliczamy wartości dist[...] oznaczające
// odległości od wierzchołka 'a'
void bfs(int a)
{
  queue<int> Q;
  Q.push(a); col[a] = true; // wstaw wierzchołek 'a' do kolejki
  dist[a] = 0;
  while( !Q.empty() ) // dopóki kolejka nie jest pusta
  {
    int u = Q.front(); Q.pop();
    for (int i=0; i<G[u].size(); i++)
    {
      int v = G[u][i];
      if ( col[v]==false )
      {
	Q.push(v); col[v] = true;
	dist[v] = dist[u]+1;
      }
    }
  }
}
Comments