Graph Traversal
Learn about BFS and DFS searching algorithms.
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.
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 ) 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.
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 ...
Create a free account to access the full course.
By signing up, you agree to Educative's Terms of Service and Privacy Policy