When trying to solve a maze puzzle, you might scan a path until it reaches a dead end, then backtracking to the next possible route and exploring that until the exit is found. Using this strategy is not just an intuitive way to solve a maze, but also a popular graph traversal algorithm called Depth-First Search.

Assumptions

  • Knowledge of Big-O notation
  • Familiarity with Graphs and Stacks
  • BFS is a plus!

What is Depth-First Search?

Depth-First Search (DFS) is a search algorithm designed to traverse a tree by exploring one route until it runs out of unvisited nodes to explore, before backtracking to explore another route.

Depth first search on its own yields no useful results from conducting the algorithm, however it is often modified slightly to fit the needs of a problem. For this reason, DFS can be seen as more of a strategy for solving graph problems than a solution on its own.

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/DFS_01.png" alt="Depth-first search header" style="width:500px;max-width:95%;">

</div>

> Similar to BFS, DFS contains the same general structure with the exception of using stacks as opposed to queues.

/* pseudo-code */
// Refresher of what a basic graph might look like.
class Graph {
    // A list of lists for the nodes + edges.
    List[] adj;
    int size;
}

function DFS( Graph G, int startVert ) {
    // (1).
    boolean[] visited = new boolean[ G.size ];
    Stack s = new Stack();

visited[ startVert ] = true;
s.push( startVert );
// (2).
while (not s.isEmpty() ) {
    int vert = s.pop();
    // (3).
    for( int adjV in G.adj[ vert ] ) {
    // (4).
    if ( not visited[ adjV] ) {
        visited[ adjV ] = true;
        s.push( adjV );
    }
    }
}
}

Going over the comments made in the code:

  1. We'll want to keep an array the size of the graph in order to track the nodes that have already been visited. Without this, any graph with a cycle could continue on in an infinite loop. This array accounts for a O(n) memory requirement.
  2. We maintain a Stack in addition to the visited array to keep the node values that we encounter while traversing and still need to explore later. While the stack contains elements, we know that the whole graph has not been traversed.
  3. When we take out the top element from the stack, we'll iterate over all the adjacency's; vertices that this node shares an edge with.
  4. While looking at adjacent vertex of a node, if it hasn't been marked as visited, it will be marked and added to the top of the stack to be traversed during the next iteration.

The recursive version of this algorithm is very useful for utility functions like finding connected components and topological sorting of a graph.

/* pseudo-code */
// Globally held visited array
boolean[] visited;

function DFS ( Graph G, int startVert ) {
    visited = new boolean[ G.size ];
    DFS_aux( G, startVert );
}
// Recursive function that does the actual DFS
function DFS_aux ( Graph G, int vert ) {
    visited [ vert ] = true;
    for( int adjV in G.adj[ vert ] ) {
        if ( not visited[ adjV ] ) {
            // Recursive call to itself.
            DFS_aux( G, adjV );
        }
    }
}

This version is useful as you are now able to easily add functions that can be carried out before and after the recursive call which is not as intuitive of an operation in an iterative approach.

Performance Memory
O(V + E) O(V)

DFS shares the same complexity as BFS, in that it's overall runtime is the sum of the total vertices and edges.

The reason for this is, every node must be explored in a graph to complete the algorithm*, giving a performance of O(V) so far.

> *Assuming the graph is not disconnected.

From there, the adjacent vertices of each node must be looked at in order to find any unexplored vertices. This means for any given node V, it will look at all edges E going away from that node to determine any unexplored nodes. This adds an additional complexity of O(E) to the algorithm.

Putting these two together yields O(V + E). It can be mistaken that the complexity could be V*E, however this is not the case as not all nodes have the same number of adjacency's where the resulting performance would be the product of the two rather than the sum of the edges and vertices.

DFS Example

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/DFS_02.png" alt="DFS graph traversal" style="width:600px;max-width:95%;">

</div>

When to use DFS

Depth-first search is an effective strategy to utilize when trying to find connected components on a graph, as well as sorting a Directional Acyclic Graph (DAG) in a topological order. On top of this, DFS is good at finding out if a maze has a solution, and even can be used to effectively create mazes using a random number generator!

Further Resources