DSA for C++ and Dlang Developers- Depth First Search

DFS

Depth first Search or Depth first traversal is a recursive algorithm for searching all the vertices/nodes of a graph or tree data structure.

The algorithm entails conducting exhaustive searches at the root node and examining each branch as far as possible before backtracking(in the case of a graph, you can use any random node as the root node).

When the Depth First Search (DFS) algorithm encounters a dead-end during its traversal, it backtracks through the network using a stack data structure, which helps it keep track of the next vertex to continue the search.

Backtracking is a technique whose goal is to use brute force to find all solutions to a problem

A standard DFS implementation puts each vertex of the graph into one of two categories:

1. Visited
2. Not Visited

The purpose of the algorithm is to mark each vertex as visited while avoiding endless cycles.

Depth-First Search Algorithm

Step 1: Initialize a stack with a capacity equal to the total number of vertices in the graph.

Step 2: Select any vertex/node as the starting point for the traversal. Mark this vertex as visited and push it onto the stack.

Step 3: Push all unvisited adjacent vertices of the vertex currently at the top of the stack onto the stack.

Step 4: Continue repeating Step 3 until there are no more unvisited adjacent vertices for the vertex at the top of the stack.

Step 5: If no new vertices can be visited, backtrack by popping the top vertex off the stack.

Step 6: Repeat Steps 3, 4, and 5 until the stack is completely empty.

Step 7: Once the stack is empty, remove any unused edges from the graph to form the final spanning tree.

// FOR CLEARER UNDERSTANDING DROP A COMMENT BELOW

#include <iostream>
#include <vector>
#include <stack>

class Graph {
public:
    Graph(int vertices);
    void addEdge(int v, int w);
    void DFS(int startVertex);

private:
    int vertices;                  // Number of vertices
    std::vector<std::vector<int>> adjList; // Adjacency list
    void DFSUtil(int v, std::vector<bool> &visited);
};

Graph::Graph(int vertices) {
    this->vertices = vertices;
    adjList.resize(vertices);
}

void Graph::addEdge(int v, int w) {
    adjList[v].push_back(w); // Add w to v's list.
    adjList[w].push_back(v); // Since the graph is undirected, add v to w's list.
}

void Graph::DFSUtil(int v, std::vector<bool> &visited) {
    // Mark the current node as visited and print it
    visited[v] = true;
    std::cout << v << " ";

    // Recur for all the vertices adjacent to this vertex
    for (int i : adjList[v]) {
        if (!visited[i]) {
            DFSUtil(i, visited);
        }
    }
}

void Graph::DFS(int startVertex) {
    // Mark all the vertices as not visited
    std::vector<bool> visited(vertices, false);

    // Call the recursive helper function to print DFS traversal
    DFSUtil(startVertex, visited);
}

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

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 4);
    g.addEdge(3, 5);
    g.addEdge(4, 5);

    std::cout << "Depth First Search (starting from vertex 0): ";
    g.DFS(0);

    return 0;
}

The Graph class represents the graph structure, same for both languages.

• vertices: The number of vertices in the graph.
• adjList: An adjacency list representing edges between vertices.
• addEdge(int v, int w): Adds an edge between vertex v and vertex w.

The Dlang code snippet for DFS algorithm

// FOR CLEARER UNDERSTANDING DROP A COMMENT BELOW
import std.stdio;
import std.array;
import std.range;

// Graph class representing an undirected graph using an adjacency list
class Graph {
    int numVertices;
    int[][] adjList;

    this(int vertices) {
        numVertices = vertices;
        adjList.length = vertices;
    }

    // Add an edge to the graph
    void addEdge(int v, int w) {
        adjList[v] ~= w;
    }

    // Recursive DFS utility function
    void DFSUtil(int v, bool[] visited) {
        // Mark the current node as visited and print it
        visited[v] = true;
        writeln(v);

        // Recur for all the vertices adjacent to this vertex
        foreach (i; adjList[v]) {
            if (!visited[i]) {
                DFSUtil(i, visited);
            }
        }
    }

    // DFS traversal of the vertices reachable from v
    void DFS(int v) {
        // Mark all the vertices as not visited
        bool[] visited = new bool[numVertices];

        // Call the recursive helper function to print DFS traversal
        DFSUtil(v, visited);
    }
}

void main() {
    Graph g = new Graph(6);

    // Add edges to the graph
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 4);
    g.addEdge(3, 5);
    g.addEdge(4, 5);

    writeln("Depth First Search starting from vertex 0:");
    g.DFS(0);
}

Real life Application of DFS Algorithm

1. Network Analysis
2. Web Crawling
3. Solving Word Games etc.