DFS, which stands for Depth-First Search, is a graph traversal algorithm used to explore or search through a graph or tree data structure. It starts from a specific node (usually called the "source" or "start" node) and explores as far as possible along each branch before backtracking.

 

What is DFS used for?

DFS is used for plethora of purposes. For example, it is used in-

1. Maze Solving: DFS can be used to solve mazes by exploring possible paths until the exit is found.
2. Topological Sorting: DFS can be used to perform a topological sort on a directed acyclic graph (DAG).
3. Connected Components: DFS can identify connected components in an undirected graph.
4. Cycle Detection: DFS can help in detecting cycles in a graph.
5. Finding Strongly Connected Components: DFS can be used to find strongly connected components in a directed graph.
6. Traversal of Tree Data Structures: DFS can traverse trees in a depth-first manner.

What is the Algorithm for implementing DFS?

1. Begin by selecting a vertex from the graph and place it at the top of a stack.
2. Take the vertex at the top of the stack, mark it as visited.
3. Compile a list of adjacent nodes connected to the current vertex. Add the unvisited neighbors to the top of the stack.
4. Continue steps 2 and 3 until the stack becomes empty, ensuring all vertices have been visited and processed.

How DFS works?

A step by step process of implementation of DFS has been shown below:

1. At first we have an empty VISITED list and an empty STACK.

2. Suppose we start from vertex 2. We put the initial vertex, here 2, in the Visited list and put all its adjacent vertices in the stack.

3. Then we visit the element present at the top of stack, here it is 3 from above picture, and go to its adjacent nodes. The adjacent nodes are 2 and 4 but 2 has already been visited so we visit 4 and put it in the top of the stack. We put 3 in the VISITED list.

4. Vertex 4 has an unvisited adjacent vertex in 6, so we add that to the top of the stack and visit it.

5. 6 has no adjacent nodes, and it has been visited so we put it in the VISITED list.

6. 5 is the last element in the stack and it has no adjacent nodes, and it has been visited so we put it in the VISITED list.

All elements have been thus visited.

C++ implementation of DFS:

#include <bits/stdc++.h>
using namespace std;

class Solution {
    // Recursive function to perform Depth-First Search (DFS)
    void dfs(int node, vector<int> &vis, vector<int> adj[], vector<int> &store) {
        store.push_back(node); // Store the current node in the traversal order
        vis[node] = 1; // Mark the current node as visited
        for (auto it : adj[node]) { // Traverse all adjacent nodes of the current node
            if (!vis[it]) {
                // If an adjacent node is not visited, recursively perform DFS on it
                dfs(it, vis, adj, store); 
            }
        }
    }
public:
    // Function to perform DFS on the entire graph
    vector<int> Graph(int V, int init, vector<int> adj[]) //init refers to initial vertex here 2
    {
        vector<int> store; // Vector to store the nodes visited during DFS traversal
        vector<int> vis(V, 0); // Vector to keep track of visited nodes, initialized to 0 (not visited)

        for (int init = 2; init < V; init++) {
            // Perform DFS on each unvisited node
            if (!vis[init]) {
                dfs(init, vis, adj, store); 
            }
        }

        return store; // Return the DFS traversal order of the graph
    }
};
 
// Function to add a directed edge between two nodes in the adjacency list
void addEdge(vector<int> adj[], int u, int v) {
    adj[u].push_back(v); // Add node v to the adjacency list of node u
}

int main() {
    vector<int> adj[7]; // Create an adjacency list for a graph with 7 nodes (0 to 6)

    // Add directed edges to the graph
    addEdge(adj, 2, 3);
    addEdge(adj, 2, 4);
    addEdge(adj, 2, 5);
    addEdge(adj, 3, 2);
    addEdge(adj, 3, 4);
    addEdge(adj, 4, 2);
    addEdge(adj, 4, 3);
    addEdge(adj, 4, 6);
    addEdge(adj, 6, 4);
    addEdge(adj, 5, 2);

    Solution obj;
    vector<int> df;
    df = obj.Graph(7,2, adj); // Perform DFS on the graph with 4 nodes

    // Print the DFS traversal order of the graph
    for (auto it : df) {
        cout << it << " ";
    }
    
    return 0;
}

Output:

2 3 4 6 5