Breadth-First Search Algorithm in C++ implementation note

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…