Back

Table of contents

Next

Breadth first search

   Given a graph G = (V, E) and a distinguished source vertex s, breadth first search systematically explores the edges of G to "discover" every vertex that is reachable from s.
Breadth-first search is so named because it expands the frontier between discovered and undiscovered vertices uniformly across the breadth of the frontier.
    To keep track of progress, breadth-first search colors each vertex white gray or black. All vertices start out white anbd may later become gray and then black. A vertex is discovered the first time it is encountered during the search, at which time it becomes non-white. Gray and black vertices, therefore have been discovered, but breadth-first search distinguishes between them to ensuree that the search proceeds in a breadth-first manner.
    Breadth-first search constructs a breadth-first tree, initially containing only it's root, which is the source vertex s. Whenever a white vertex v is discovered in the course of scanning the adjacency list of an already discovered vertex u, the vertex v and the edge (u,v) are added to the tree. We say that u is the predecessor or parenbt of v in the breadth-first tree.
    The Breadth-first search procedure BFS below assumes that the input graph G= (V,E) is represented using adjacency list. The color of each vertex u belonging to V is stored in the variable color[u], and the predecessor of u is stored in the variable parent[u]. If u has no predecessor, then parent[u]= NIL. The distance from the source s to the vertex u computed by the algorithm is stored in d[u].
 

BFS(G, s)

   1   for each vertex u belonging to V[G] - {s}
   2           do color[u] <- WHITE
   3                  d[u] <- inf
   4                 parent[u] <- NIL
   5   color[s] <- GRAY
   6   d[s] <-  0
   7   parent[s] <- NIL
   8   Q <- {s}
   9   while Q != empty
 10          do u <- head[Q]
 11                for each v belonging to Adj[u]
 12                       do if color[v] = WHITE
 13                                 then color[v] <- GRAY
 14                                         d[v] <- d[u] + 1