Contents of the page


By the end of this lesson, you will be able to describe and compare the two main graph traversal approaches: Depth-First Search (DFS) and Breadth-First Search (BFS).


Finding the exit of a maze requires us to traverse part of the maze. Graph traversal is the domain of graph theory that describes how to explore a graph, one vertex at a time, starting from an initial vertex. In many cases, we’re interested in accessibility. Accessibility is finding how to reach a target vertex from an initial vertex, following a path in the graph. To obtain paths from the initial vertex to all the accessible ones, we are going to build a tree, obtained from the initial graph, that will convey just enough information to guide us to any accessible vertex from the initial one.

Neighbors and spanning trees

Recall that a graph is a couple G composed of a set of vertices V and a set of edges E. Now we need to define a few more things.

We define the neighbors of u in G as the set of vertices v such that {u,v} is in E.

As we’ve seen in the previous lesson, a tree is a connected graph with no cycles. For example, on the left is a drawing of a tree. However, the graph on the right is not a tree, because it includes a cycle.

tree-or-not-tree

Now, a spanning tree of a graph G is a tree obtained from G by removing some edges.

To illustrate, consider the following graph:

tree-or-not-tree
tree-or-not-tree
tree-or-not-tree



We can obtain a spanning tree by keeping only the following edges: 

Note that for a given graph, other spanning trees can be defined, such as this one: 

Finding spanning trees can have many applications. In particular, finding a spanning tree is very useful when you want to avoid loops, such as in routing algorithms in networking. Another example of its usefulness is when assessing if a graph is connected. Imagine that you want to isolate a portion of a highway for maintenance. First, you need to make sure that the graph of streets remain connected during the constructions work.

In this lesson, we’re going to see how to find a path between two vertices of a connected graph, so that we’re able to navigate between any two points. By definition, a spanning tree will include exactly one path between those two points. 

We will compare two approaches – the Depth-first search and the Breadth-first search.

Depth-first search

The main idea of a depth-first search is to keep exploring the graph, jumping from a given vertex to one of its unexplored neighbors. Sometimes, all neighbors of the vertex we’re in have already been explored, in which case we turn back, following the trail in the opposite direction until we find an unexplored vertex to jump to.

tree-or-not-tree
tree-or-not-tree
tree-or-not-tree
tree-or-not-tree
tree-or-not-tree
tree-or-not-tree
tree-or-not-tree
tree-or-not-tree
tree-or-not-tree

Take the following example. A depth-first search, or DFS, can be performed in the following way, starting from v_1.

First we go up. Note that we could have chosen to go right.

We continue exploring the graph, we go up again.

Next, we have only one unexplored neighbor, which is on the right. So we go right.

Now we go down. Alternatively, we could have continued right.

From here, there are three neighbors, two of which are unexplored. We choose to go right. 

Next, we go up. 

At this point, we can’t go further, because all the current neighbors have already been explored. We go back to the last vertex for which there was an unexplored neighbor, which is the previous one, and we go down.

From this vertex, there’s only one remaining, unexplored neighbor, which is the one on the left. This is the last unexplored vertex in the graph.

The graph in red is a spanning tree obtained from the graph using a DFS.

DFS is a simple yet efficient strategy to ensure that all accessible vertices are explored. It’s an easy way to find the exit of a maze, or to make sure streets remain connected during construction work. However, it doesn’t necessarily yield shortest paths between pairs of vertices in the graph. In this example, it takes 7 hops to travel from \(v_1\) to \(v_2\), despite the fact that these could be linked with just 1 hop.

Breadth-first search

The other approach described here is the Breadth-first search. When using a Breadth-first search, or BFS, we explore the graph by gradually increasing the number of hops from the initial vertex.

tree-or-not-tree

Let’s consider the same example, where we start in v_1:

We start by exploring all vertices one hop away from v_1: we thus connect both v_2 and v_4 to v_1.

Then we explore all vertices two hops away from v_1. A vertex two hops away from v_1 is one hop away from a vertex that’s one hop away from v_1. So we look at the neighbors of v_2 and v_4 and connect them to v_2 or v_4. We obtain v_3, v_5 and v_7.

Then we explore the vertices three hops away from vertex v_1. So, we look at vertices two hops away, which are v_3, v_5 and v_7, and at  their unexplored neighbors. We obtain v_8 and v_6.

Finally, the orange vertex is one hop away from v_8, which is three hops away from vertex v_1. We connect them.

The resulting graph in red is a spanning tree obtained from the BFS, which is made exclusively of shortest paths from vertex v_1 to the other vertices of the graph.

A BFS is a cautious strategy in which we try to keep the distance to the initial vertex as small as possible during exploration. This is especially useful when the initial vertex contains specific resources that we might need at any moment. However, it does require more organization than its simpler DFS counterpart.

Comparison between BFS and DFS

tree-or-not-tree
tree-or-not-tree
tree-or-not-tree

In this example, the spanning trees obtained by a BFS and a DFS are very different.

Here’s another example using the graph we considered earlier in this lesson.

This is a spanning tree obtained from a DFS starting from v_1:
While this is a spanning tree obtained from a BFS starting from v_1:

Because a BFS is performed by gradually increasing the hops from v_1, a spanning tree obtained from a BFS will always provide the shortest path from v_1 to any other vertex in the graph, provided that the graph is unweighted. This can be seen clearly in this example.

In the next article, we will see how the difference between a BFS and a DFS directly relates to the type of memory structure that can be used to implement these two algorithms.


Properties of the BFS

In order to understand this section properly, you should first study the proposed implementation of the BFS here.

When writing an algorithm, it is important to answer three questions:

  • Will it terminate?
  • Is it correct?
  • How complex is it?

Termination

The algorithm only visits once each vertex that can be attained. Since the number of vertices is finite, the algorithm will eventually terminate.

Correctness

We want to show that the BFS algorithm returns a shortest path from a vertex u to all other vertices that can be attained from u through graph edges.

We are going to show that:

  1. All vertices are visited in increasing distance to u.
  2. Obtained paths are of minimum length.
  3. All attainable vertices are visited.

All vertices are visited in increasing distance to u

Let’s assume by the absurdity the first moment when a vertex v is added to the FIFO, and there already exists a vertex w inside it such that d(u, v) < d(u, w).

Let’s note p the vertex, neighbor of v, that adds v to the FIFO. There can be two cases:

  • Either w is closer to u than p and we reach a contradiction. Indeed, when w was added, there was a vertex in the FIFO that was already farther. Therefore, this is not the first moment when this situation happens.
  • Or the distance from u to p is the same as the one from u to w. We therefore conclude that v is closer from u than p. Let k be a predecessor of v on a shortest path from u to v. k has not been visited, otherwise v would have added it to the FIFO. By recurrence, we see that a direct neighbor of u hasn’t been added to the FIFO, thus p = u. v cannot thus be closer from u than p.

Obtained paths are of minimum length

The proof is performed by induction. We will show that, at any moment, all paths in the FIFO are of minimal length.

This is trivially true for starting vertex u, as it is at distance 0 from itself.

As shown previously, all vertices are visited in increasing distance to u. This ensures that adding a vertex to the FIFO is always performed by a neighbor that is a predecessor along a shortest path initiated from u.

All attainable vertices are visited

By the absurdity, let v be an attainable vertex, but not yet visited, at minimal distance from u. Let us consider a shortest path from u to v. Let k be the predecessor of v along that path.

Thus, k has not been visited, otherwise it would have been added to the FIFO. Therefore, k is attainable and not yet visited, and is closer from u than v. We reach a contradiction.

Complexity

The algorithm only visits once each vertex, and checks the list of neighbors each time. Therefore, its complexity is O(m), where m is the number of edges in the graph.

Properties of the DFS

Termination

The algorithm only visits once each vertex that can be attained. Since the number of vertices is finite, the algorithm will eventually terminate.

Correctness

We want to show that the algorithm is such that it will visit all the vertices attainable from u.

To verify this property, we first remark that all the visited vertices during a DFS are indeed attainable. This can easily be shown by induction (u is trivially attainable from itself, then neighboring vertices are also attainable).

Then, we have to verify that all attainable vertices are visited by the DFS. Let’s proceed by the absurdity. A vertex v which is attainable is, by definition, such that there exists a path from u to v in the graph. On such a path, we consider the vertex just before v. This vertex cannot be visited, otherwise v would have been visited. By induction, we conclude that u has not been visited, and reach a contradiction.

Complexity

The DFS search only checks twice each edge of the graph, with a number of elemental operations which is proportional to that quantity. Therefore, complexity is O(m), where m is the number of edges in the graph.


To go further

  • Beam search: a variation of the BFS to accelerate it while sacrificing the guarantee it will find the shortest path.
  • IDDFS: a mixed approach between DFS and BFS that takes the best of both worlds.

Quiz

A graph traversal is a way to...
Let's say we use a DFS from vertex v1 on an unweighted graph. Which of the following propositions are true?
Let's say we use a BFS from vertex v1 on an unweighted graph. Which of the following propositions are true?