Deep Dive Through A Graph: DFS Traversal

Vaidehi Joshi
Sep 25, 2017 · 17 min read
Depth-first search graph traversal

A primer, before going deep

A helpful first step in knowing how any algorithm works and what it does is by knowing what the algorithm does not do. In other words, when we’re learning something new, it can be useful to compare the new thing that we’re learning to the things that we already know well and feel fairly comfortable with.

Depth-first search: a definition
Comparing DFS to BFS graph traversal

The depth-first algorithm sticks with one path, following that path down a graph structure until it ends. The breadth-first search approach, however, evaluates all the possible paths from a given node equally, checking all potential vertices from one node together, and comparing them simultaneously.

Like architecture and biology, in this case, the old adage rings true: form really does follow function. That is to say, the way that both of these algorithms are designed help give us clues as to what their strengths are! Breadth-first search is crafted to help us determine one (of sometimes many) shortest path between two nodes in the graph. On the other hand, depth-first search is optimized not to tell us if a path is the shortest or not, but rather to tell us if the path even exists!

Depth-first search: solving a maze

Depth-first, in action

Exactly like what we saw in last week’s exploration of BFS, we can start our traversal of a graph with DFS in a similar fashion — wherever we want!

How could we run DFS to explore a directed graph?
DFS, part 1
DFS, part 2
DFS, part 3

We’ve gone as deep as we can down this particular path from the node that we started with, and we’ve hit a dead end; that is to say, we’ve reached a node with no reachable vertices!

Given our conundrum, let’s pause for a moment and take a look at our stack of “visited” nodes, which has the following nodes on it: e, d, c, and a, in that order, from the top of the stack to the bottom. Since there is nowhere to go from node e, we effectively have no other node to visit, which means that we have no other node to add to the top of the stack. At least, given where we currently are, at node e. But, node d, the second element in the stack might have somewhere to go, right?

DFS, part 4
DFS, part 5
  1. We marked it as “visited”.
  2. We checked to see if it had any children — and if it did, we ensured that they had not been visited already, and then visited it. If not, we popped it off the stack.

Real-life recursion and runtime

The recursion of the DFS algorithm stems from the fact that we don’t actually finish checking a “parent” node until we reach a dead end, and inevitably pop off one of the “parent” node’s children from the top of the stack.

Recursion as applied to DFS runtime
We could apply DFS in the same way on an undirected graph
Depth-first search and linear runtime
Implementing DFS using an adjacency list, Part 1
Implementing DFS using an adjacency list, Part 2
Depth-first vs breadth-first: pros and cons

Resources

Depth-first search can be explained and implemented in a few different ways, and trying to understand all of them — at least, when you’re first learning the DFS algorithm — can feel overwhelming. However, once you’re more comfortable and familiar with how it works, it’s helpful to know the different implementations and idiosyncrasies of how DFS works. If you’re looking to gain a deeper understanding of this algorithm, here are some good examples and implementations to help you get started.

  1. Depth-First Search, Department of Computer Science, Harvard
  2. When is it practical to use DFS vs BFS?, StackOverflow
  3. Depth-First Search (DFS), Topological Sort, MIT OpenCourseWare
  4. Graph Traversals — Breadth First and Depth First, CollegeQuery

basecs

Exploring the basics of computer science, every Monday, for a year.

Vaidehi Joshi

Written by

Writing words, writing code. Sometimes doing both at once.

basecs

basecs

Exploring the basics of computer science, every Monday, for a year.