This page describes Breadth-First Search (BFS), which is an algorithm for finding all paths in a graph starting at one particular node. The algorithm described here is from the 6.046 textbook, Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein (new edition: section 22.2, pp. 531--534; old edition: section 23.2, pp. 469--470). There is also a description of BFS in what used to be the 6.034 textbook: Artificial Intelligence, by Patrick Winston (chapter 4, p. 68).

The algorithm as defined here builds a table of the shortest distances from a given node to each other node in the graph (or infinity, if the node is not reachable), and the path taken. The inputs to the algorithm are a graph G, and a start node (or ``vertex''), s. The graph G has a set of vertices, or nodes, V. A node's predecessor is the node that comes before it on a path. A node's color marks its ``visited'' status. A white node is completely unvisited and has yet to be explored. A gray node is currently being explored, and a black node has already been visited, and doesn't need to be visited again.

BFS(G, s)
  for each vertex u in V - { s } do
    u.color = white
    u.dist = infinity  // ``dist'' is distance from s
    u.pred = nil       // ``pred'' is predecessor
  s.color = gray
  s.dist = 0 
  s.pred = nil
  Q = { s }            // ``Q'' is a FIFO queue
  while Q not empty do
    u = Q.head         // get element on top of queue
    for each v in neighbors(u) do  // visit every node u has an edge to
      if v.color == white then
        v.color = gray
        v.dist = u.dist + 1
        v.pred = u
        Q.enqueue(v)   // add v to back of queue
    Q.dequeue          // pop u off top of queue
    u.color = black

• http://www.ics.uci.edu/~eppstein/161/960215.html