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.
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; } } } } |