**breadth-first search** (BFS): Finds a path between two nodes by taking one step down all paths and then immediately backtracking.

– Often implemented by maintaining a queue of vertices to visit

Well.. CCC 2015 is on Feb. 18 so now it’s probably a good time to review all kind of stuff in C++. BFS is an important algorithm for searching paths, and here is how it works.

Pseudocode (CS106B Stanford Lecture note, distributed under CC 2.5 License):

function bfs(v1, v2): queue := {v1}. mark v 1 as visited. while queue is not empty: dequeue a vertex v from the queue. if v is v2: a path is found! for each unvisited neighbor n of v mark n as visited, and enqueue n in queue //if we get here, no path exists.

An implementation in C++ follows (CCC 2008 Senior Problem No. 3, did it quickly probably poor code style): Continue Reading…