Graph Traversal: Breadth First Search¶

Motivation¶

Google Robot
Lewis Carroll’s Doublets (Knuth does it better then you)
Rubic’s Cube
find diameter (G-d’s Number)
find a shortest path

Definition¶

Given a graph G, and a starting vertex s, a breadth first search, finds all vertices a distance of d from s, prior to moving to a distance of d+1. It finds all children, prior to looking for grandchildren.

Attributes¶

{distance | level}
parent
frontier
{color | is_visited}

Operations¶

traverse(G, s)