Mastering Algorithms for Problem Solving in C++/

...

/

Introduction to Depth-First Search

Introduction to Depth-First Search

Learn about the history and evolution of depth-first search.

We'll cover the following...

In this lesson, we’ll focus on a particular instantiation of this algorithm called depth-first search, primarily on the behavior of this algorithm in directed graphs. Although depth-first search can be accurately described as “whatever-first search with a stack,” the algorithm is normally implemented recursively rather than using an explicit stack:

Algorithm

DFS(v):‾if v is unmarkedmark vfor each edge v→wDFS(w)\underline{DFS(v):} \\ \hspace{0.4cm} if\space v\space is\space unmarked \\ \hspace{1cm} mark\space v \\ \hspace{1cm} for\space each\space edge\space v\rightarrow w \\ \hspace{1.7cm} DFS(w)

Implementation

C++
#include <iostream>
#include <vector>
using namespace std;
void DFS(int v, bool marked[], vector<int> adj[])
{
    marked[v] = true;
    cout << v << " ";
    for(int i = 0; i < adj[v].size(); i++)
    {
        int w = adj[v][i];
        if(!marked[w])
            DFS(w, marked, adj);
    }
}
int main()
{
    // Define the graph as an adjacency list
    vector<int> adj[6];
    adj[1].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(4);
    adj[3].push_back(4);
    adj[4].push_back(5);
    // Define the marked array
    bool marked[6] = {false};
    // Call DFS starting from vertex 1
    DFS(1, marked, adj);
    return 0;
}

Explanation

  • Line 5: The function DFS takes three arguments: v is the current vertex being visited, marked is an array to keep track of visited vertices, and adj is the adjacency list representation of the graph.

  • Lines 7–14: The above block of code is the recursive part of the DFS algorithm. It first marks the current vertex v as visited by setting marked[v] = true. For each adjacent vertex w, it checks if it has already been visited by checking the corresponding value in the marked array. If it hasn’t been visited yet (!marked[w]), then it calls the DFS function recursively with the adjacent vertex w as the new starting vertex.

Optimization

We can make this algorithm slightly faster (in practice) by checking whether a node is marked before we recursively explore it. This modification ensures that we call DFS(v)DFS(v) only once for each vertex vv. We can further modify the algorithm to compute other useful information about the vertices and edges by introducing two black-box subroutines, PreVisitPreVisit and PostVisitPostVisit, which we leave unspecified for now.

Algorithm

DFS(v):‾mark vPreVisit(v)for each edge vwif w is unma ...