What is Breadth-First Search (BFS) and give example?

Breadth-First Search

•      “Explore” a graph, turning it into a tree

–     One vertex at a time

–     Expand frontier of explored vertices across the breadth of the frontier

•      Builds a tree over the graph

–     Pick a source vertex to be the root

–     Find (“discover”) its children, then their children, etc.

•      Associate vertex “colors” to guide the algorithm

–     White vertices have not been discovered

•      All vertices start out white

–     Grey vertices are discovered but not fully explored

•      They may be adjacent to white vertices

–     Black vertices are discovered and fully explored

•      They are adjacent only to black and gray vertices

•      Explore vertices by scanning adjacency list of grey vertices

Code

BFS(G, s) {

    initialize vertices;

    Q = {s};                             // Q is a queue (duh); initialize to s

    while (Q not empty) {   

                    u = RemoveTop(Q);

                          for each v Î u->adj {

                                              if (v->color == WHITE)

                                               v->color = GREY;

                                               v->d = u->d + 1;

                                              v->p = u;

                                              Enqueue(Q, v);

                                                                  }

                              u->color = BLACK;

                                      }

                         }

                      

 

Breadth-First Search: Properties

•      BFS calculates the shortest-path distance to the source node

–     Shortest-path distance d(s,v) = minimum number of edges from s to v, or ¥ if v not reachable from s

•      BFS builds breadth-first tree, in which paths to root represent shortest paths in G

–     Thus can use BFS to calculate shortest path from one vertex to another in O(V+E) time