Breadth First Search

The breadth-first-search(BFS) algorithm starts at a vertex s and visits, first the neighbours of s, then the neighbours of the neighbours of s, then the neighbours of the neighbours of the neighbours of s, and so on.

This algorithm is a generalization of the breadth-first traversal algorithm for binary trees, and is very similar; it uses a queue, q, that initially contains only s. It then repeatedly extracts an element from Q and adds its neighbours to Q, provided that these neighbours have never been in Q before. The only major difference between the breadth-first-search algorithm for graphs and the one for trees is that the algorithm for graphs has to ensure that it does not add the same vertex to Q more than once.

BFS

An example of running BFS(G,s) on a graph is shown in figure. Different executions are possible, depending on the ordering of the adjacency lists.

Algorithm:

BFS(G,s)
    for each vertex u ∈ G.V - {s}
        u.color = WHITE
        u.d = ∞
        u.π = NIL
    s.color = GRAY
    s.d = 0
    s.π = NIL
    Q = ∅
    ENQUEUE(Q,s)
    while Q ≠ ∅
        u = DEQUEUE(Q)
        for each v ∈ G.Adj[u]
            if v.color == WHITE
                v.color = GRAY
                v.d = u.d + 1
                v.π = u
                ENQUEUE(Q,v)
        u.color = BLACK

Implementation:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <limits>
#define MAX 101
using namespace std;

enum colors {BLACK, WHITE, GRAY};
int color[MAX], d[MAX], p[MAX], vertex, edge;
int INF = numeric_limits::max();
int NIL = numeric_limits::min();

void BFS(vector[],int);
void PRINT_PATH(vector[],int,int);

int main()
{
    //freopen("bfs.txt", "r", stdin);
    vector adjList[MAX];
    int u, v;
    cin >> vertex >> edge;

    for(int e=1; e<=edge; e++) {
        cin >> u >> v;
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }

    BFS(adjList, 1);
    PRINT_PATH(adjList, 1, 4);

    return 0;
}

void BFS(vector G[], int s) {
    for(int u=0; u<=vertex; u++) {
        color[u] = WHITE;
        d[u] = INF;
        p[u] = NIL;
    }

    color[s] = GRAY;
    d[s] = 0;
    p[s] = NIL;

    queue Q;
    Q.push(s);

    while( !Q.empty()) {
        int u = Q.front();
        Q.pop();
        for(int i=0; i<G[u].size(); i++) {
            if(color[G[u][i]] == WHITE) {
                color[G[u][i]] = GRAY;
                d[G[u][i]] = d[u] + 1;
                p[G[u][i]] = u;
                Q.push(G[u][i]);
            }
        }
        color[u] = BLACK;
    }
}

void PRINT_PATH(vector G[], int s, int v) {
    if(v == s)
        cout << s;
    else if(p[v] == NIL)
        cout << "no path from " << s << " to " << v << " exists";
    else {
        PRINT_PATH(G, s, p[v]);
        cout << " -> ";
        cout << v;
    }
}

Analyzing the running-time of the BFS(G,i) routine is fairly straightforward. The use of the seen array ensures that no vertex is added to q more than once. Adding (and later removing) each vertex from Q takes constant time per vertex for a total of O(V) time. Since each vertex is processed by the inner loop at most once, each adjacency list is processed at most once, so each edge of G is processed at most once. This processing, which is done in the inner loop takes constant time per iteration, for a total of O(E) time. Therefore, the entire algorithm runs in O(V + E) time.