Data Structures with Generic Types in C++/

...

/

Graph Traversal

Graph Traversal

Learn about BFS and DFS searching algorithms.

We'll cover the following...

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 neighbors to q, provided that these neighbors 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.

Press + to interact
void bfs(Graph g, int r) {

  boolean[] seen = new boolean[g.nVertices()];

  Queue < Integer > q = new SLList < Integer > ();

  q.add(r);

  seen[r] = true;

  while (!q.isEmpty()) {

    int i = q.remove();

    for (Integer j: g.outEdges(i)) {

      if (!seen[j]) {

        q.add(j);

        seen[j] = true;

      }

    }

  }

}

Visual demonstration of breadth-first search

An example of running bfs(g, 0) on the graph is shown in the illustration below.

An example of bread-first-search starting at node 00. Nodes are labeled with the order in which they are added to q. Edges that result in nodes being added to q are drawn in black, and other edges are drawn in grey.

Press + to interact
Breadth-first search
Breadth-first search

Analyzing the running-time of the bfs(g, i) routine is fairly straightforward. The use of the seen array ensures that no vertex is added to q more than once. Adding (and later removing) each vertex from q takes constant time per vertex for a total of O(n)O(n) time. Since each vertex is processed by the inner loop at most once, each adjacency list is processed at most once, so each edge of GG is processed at most once. This processing, which is done in the inner loop takes constant time per iteration, for a total of O(m)O(m) time. Therefore, the entire algorithm runs in ...