Data Structures with Generic Types in Java/

...

/

Graph Traversal

Graph Traversal

Learn about BFS and DFS searching algorithms.

We'll cover the following...

In this section 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 AdjacencyLists.

Breadth-first search

The breadth-first-search algorithm starts at a vertex i and visits, first the neighbours of i, then the neighbours of the neighbours of i, then the neighbours of the neighbours of the neighbours 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.

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 algorithm

An example of running bfs(g, 0) (bread-first-search starting at node 00) on the graph is shown in the illustration below. Nodes are labelled 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 gray.

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) ...