by Jasleen Chhabra | Updated on 24 August 2024

Introduction

Depth-First Search (DFS) is a fundamental algorithm used for traversing or searching through graph structures and tree structures. Unlike Breadth-First Search (BFS), which explores neighbors before going deeper, DFS explores as far as possible along each branch before backtracking. This makes DFS particularly useful for scenarios where you want to explore all possible paths in a graph.

How DFS Works

DFS can be implemented using either a recursive approach or an iterative approach using a stack. The algorithm starts from a specified source vertex and explores as deeply as possible along each branch before backtracking. It marks each vertex as visited to prevent revisiting.

Algorithm Steps

1. Initialization:
   • Create a stack (for the iterative approach) or use the call stack (for the recursive approach).
   • Mark the starting vertex as visited.
2. Exploration:
   • While there are unvisited vertices:
     • If using a stack, push the current vertex onto the stack. If using recursion, call the DFS function for the current vertex.
     • For each unvisited neighbor of the current vertex:
       • Mark the neighbor as visited.
       • Repeat the exploration for the neighbor.
3. Backtracking:
   • If no unvisited neighbors are left, backtrack to the previous vertex (this happens automatically with recursion).

---

DFS Algorithm in Pseudocode

DFS(Graph, vertex):

    mark vertex as visited

    process(vertex)  // e.g., print the vertex

 

    for each neighbor of vertex:

        if neighbor is not visited:

            DFS(Graph, neighbor)

---

DFS Example

Consider the same simple undirected graph used in the BFS example:

       A

      / \

     B   C

    / \   \

   D   E   F

• Starting from vertex A, the DFS traversal might visit the vertices in the following order: A, B, D, E, C, F. The exact order can vary based on how neighbors are stored.

---

C++ Implementation

Here’s a sample implementation of the DFS algorithm in C++ using an adjacency list representation for the graph:

#include <iostream>

#include <vector>

#include <unordered_set>

 

using namespace std;

 

class Graph {

    int V; // Number of vertices

    vector<vector<int>> adj; // Adjacency list

 

public:

    Graph(int V) {

        this->V = V;

        adj.resize(V);

    }

 

    void addEdge(int u, int v) {

        adj[u].push_back(v);

        adj[v].push_back(u); // For undirected graph

    }

 

    void DFS(int vertex, unordered_set<int>& visited) {

        visited.insert(vertex); // Mark the vertex as visited

        cout << vertex << " "; // Process the vertex

 

        // Explore all adjacent vertices

        for (int neighbor : adj[vertex]) {

            if (visited.find(neighbor) == visited.end()) { // If not visited

                DFS(neighbor, visited); // Recursively call DFS

            }

        }

    }

 

    void startDFS(int start) {

        unordered_set<int> visited; // Set to track visited vertices

        DFS(start, visited); // Start DFS from the given vertex

    }

};

 

int main() {

    Graph g(6); // Create a graph with 6 vertices

    g.addEdge(0, 1); // A - B

    g.addEdge(0, 2); // A - C

    g.addEdge(1, 3); // B - D

    g.addEdge(1, 4); // B - E

    g.addEdge(2, 5); // C - F

 

    cout << "DFS traversal starting from vertex A (0): ";

    g.startDFS(0); // Start DFS from vertex A (0)

 

    return 0;

}

---

Explanation of the C++ Code

1. Graph Class: Represents the graph using an adjacency list, including methods for adding edges and performing DFS.
2. addEdge Method: Adds an undirected edge between vertices u and v.
3. DFS Method: Implements the recursive DFS algorithm:
   • It marks the current vertex as visited and processes it (prints its value).
   • It recursively explores each unvisited neighbor.
4. startDFS Method: Initializes the visited set and starts the DFS process from the specified starting vertex.
5. Main Function: Creates a graph, adds edges, and calls the startDFS method starting from vertex A (0).

---

Conclusion

Depth-First Search is a versatile and powerful algorithm for exploring graphs and trees. Its recursive nature makes it suitable for various applications, including topological sorting, finding connected components, and solving puzzles like mazes. In subsequent articles, we will explore more advanced graph algorithms and their practical applications. 

---