Depth-first Search (DFS)

After settling the basic terminology and learning about graph representations, let’s dive into our first actual graph algorithm. In this section, we’ll look into different ways of traversing graphs.

Unlike totally or partially ordered data structures, such as lists or trees, there is no canonical order in which the nodes of a graph should be explored. However, there are two standard algorithms to traverse graphs that define an order in which the nodes are visited: depth-first search (DFS) and breadth-first search (BFS). Although the algorithms are elementary, they can already be applied to solve a wide variety of graph problems with just basic modifications.

In this lesson, we will start by looking into depth-first search.

Explanation of DFS

Depth-first search is a method to traverse a graph where the deepest not yet explored node is always explored first.

To illustrate the concept let’s consider the following example graph: