Breadth-First Search

From Algorithmist
Jump to: navigation, search
This is a stub or unfinished. Contribute by editing me.

Take a look at the wikipedia: http://en.wikipedia.org/wiki/Breadth_first_search

In a breadth-first search, all children of a node are visited before their (unvisited) children are visited. Given any connected graph (including trees), the search starts at the root node.

  1. Each unvisited node connected to this root node is added to a visitor queue and marked as already visited.
  2. Add the root node to the visited queue. Take the first node from the visitor queue.
  3. Repeat step 1 for the current node.
  4. Stop when the visitor queue is empty.