[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

Breadth-first search visits every reachable node in a graph in order of increasing distance from the starting node. It can be thought of as a ShortestPath algorithm for the special case where all edges have length 1.

Typical code for breadth-first-search:

BFS(G, s):
  Q = an empty queue
  mark[] = array of booleans, one per vertex, initially false
  mark[s] = true
  push(s, Q)
  while Q is not empty:
    u = pop(Q)
    for each successor v of u:
      if mark[v] = false:
        push(v, Q)

If the queue is replaced by a stack, the algorithm becomes DepthFirstSearch. For a combined implementation of both breadth-first and depth-first search in C, see C/Graphs.

For distributed algorithms, see DistributedBreadthFirstSearch.

CategoryAlgorithmNotes CategoryProgrammingNotes

2014-06-17 11:57