Graph Traversal

In this lesson we present two algorithms for exploring a graph, starting at one of its vertices, i, and finding all vertices that are reachable from i. Both of these algorithms are best suited to graphs represented using an adjacency list representation. Therefore, when analyzing these algorithms we will assume that the underlying representation is an AdjacencyLists.

Breadth-first-search

The breadth-first-search algorithm starts at a vertex i and visits, first the neighbors of i, then the neighbors of the neighbors of i, then the neighbors of the neighbors of the neighbors of i, and so on. This algorithm is a generalization of the breadth-first traversal algorithm for binary trees, and is very similar; it uses a queue, q, that initially contains only i. It then repeatedly extracts an element from q and adds its neighbours to q, provided that these neighbours have never been in q before. The only major difference between the breadth-first-search algorithm for graphs and the one for trees is that the algorithm for graphs has to ensure that it does not add the same vertex to q more than once. It does this by using an auxiliary boolean array, seen, that tracks which vertices have already been discovered.