Depth First Search DFS Notes 2025 for Data Structures with Code and PDF

Depth First Search (DFS) is a fundamental algorithm in graph theory and computer science that systematically explores all the vertices and edges of a graph. DFS plays a vital role in solving various computational problems including pathfinding, topological sorting, cycle detection, and component identification. In the context of B.Tech Data Structures Notes 2025, DFS is part of Unit 2 Notes Data Structures and is considered essential Engineering Study Material for examinations and practical understanding.

DFS explores a graph by starting at an arbitrary node and exploring as far as possible along each branch before backtracking. It is typically implemented using recursion or a stack. DFS works on both directed and undirected graphs and is applicable to both connected and disconnected components.

A graph is defined as a collection of vertices (or nodes) and edges. In mathematical terms, a graph G is denoted by G = (V, E), where V is the set of vertices and E is the set of edges. DFS begins at a chosen vertex and marks it as visited. It then moves to an adjacent unvisited vertex, marks it as visited, and continues this process recursively. If all adjacent vertices are visited, the algorithm backtracks to the previous vertex and continues the exploration. This process continues until all vertices reachable from the starting vertex are visited.

Algorithm of DFS (Recursive Approach)

The recursive implementation of DFS uses function calls to emulate the behavior of a stack. The following pseudocode outlines the logic of DFS:

DFS(G, v):
    mark v as visited
    for each vertex u adjacent to v:
        if u is not visited:
            DFS(G, u)

Code Implementation in C++

#include <iostream>
#include <vector>
using namespace std;

void DFS(int vertex, vector<vector<int>> &adj, vector<bool> &visited) {
    visited[vertex] = true;
    cout << vertex << " ";
    for (int i = 0; i < adj[vertex].size(); i++) {
        int next = adj[vertex][i];
        if (!visited[next]) {
            DFS(next, adj, visited);
        }
    }
}

int main() {
    int V = 5;
    vector<vector<int>> adj(V);

    // Example graph
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(4);

    vector<bool> visited(V, false);
    DFS(0, adj, visited);
    return 0;
}

Graph Representations

Graphs can be represented in two major ways: Adjacency Matrix and Adjacency List.

Adjacency Matrix: A 2D array of size V x V where matrix[i][j] = 1 represents an edge between vertex i and j. Adjacency List: An array of lists. Each list represents a vertex and contains all adjacent vertices.

// Sample Adjacency List
adj[0] = [1, 2]
adj[1] = [3]
adj[2] = [4]

📌 Insert Diagram: Adjacency List Representation of a Graph

DFS Using Stack (Iterative Method)

In some programming environments, recursion depth can be a limitation. An iterative DFS using a stack avoids this problem:

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void iterativeDFS(int start, vector<vector<int>> &adj, int V) {
    vector<bool> visited(V, false);
    stack<int> st;
    st.push(start);

    while (!st.empty()) {
        int vertex = st.top();
        st.pop();

        if (!visited[vertex]) {
            cout << vertex << " ";
            visited[vertex] = true;
        }

        for (int i = adj[vertex].size() - 1; i >= 0; --i) {
            int neighbor = adj[vertex][i];
            if (!visited[neighbor]) {
                st.push(neighbor);
            }
        }
    }
}

Applications of DFS

DFS is a versatile algorithm with the following applications:

Cycle Detection in directed and undirected graphs
Topological Sorting in Directed Acyclic Graphs (DAG)
Connected Components Identification
Solving Maze Problems by exploring all paths
Pathfinding Algorithms in AI and game development

Time and Space Complexity

The efficiency of DFS is defined as follows:

Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges
Space Complexity: O(V), for the visited array and recursion stack (or explicit stack)

📌 Insert Diagram: Depth-First Search Tree Traversal

DFS in Disconnected Graphs

When a graph is not connected, a single DFS call from a node may not cover all vertices. To handle this, we perform DFS for all unvisited vertices:

for (int i = 0; i < V; i++) {
    if (!visited[i]) {
        DFS(i, adj, visited);
    }
}

DFS vs BFS: Key Differences

Feature	DFS	BFS
Data Structure Used	Stack / Recursion	Queue
Traversal Strategy	Deep (go deeper first)	Broad (level by level)
Memory Usage	Can be more memory-efficient	May require more memory
Applications	Topological Sort, Cycle Detection	Shortest Path in Unweighted

Handling Cycles in DFS

To detect a cycle, DFS is modified to track the recursion stack:

bool DFS_Cycle(int node, vector<vector<int>> &adj, vector<bool> &visited, vector<bool> &recStack) {
    visited[node] = true;
    recStack[node] = true;

    for (int neighbor : adj[node]) {
        if (!visited[neighbor] && DFS_Cycle(neighbor, adj, visited, recStack))
            return true;
        else if (recStack[neighbor])
            return true;
    }
    recStack[node] = false;
    return false;
}

🔹 Short Answer Questions (2-3 Marks)

Define DFS. DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking.
What is the time complexity of DFS? The time complexity of DFS is O(V + E).
Which data structure is used in iterative DFS? A stack is used for implementing DFS iteratively.
Is DFS applicable to disconnected graphs? Yes, but it must be applied to all unvisited nodes.
Name two applications of DFS. Cycle detection and topological sorting.
What is the primary difference between DFS and BFS? DFS uses stack/recursion while BFS uses a queue.
Can DFS detect cycles? Yes, DFS can be modified to detect cycles.

🔸 Long Answer Questions (5-10 Marks)

Explain the DFS algorithm with an example and its recursive implementation. DFS begins by selecting a starting vertex, marks it visited, and recursively visits adjacent unvisited vertices. Code and explanation as above.
Compare DFS and BFS in detail. DFS explores deeper paths first, uses a stack, and is suitable for problems like topological sorting. BFS uses a queue, explores level by level, and is best for shortest path problems.
Write the iterative version of DFS and explain its working with an example graph. Iterative DFS uses a stack to simulate recursion. It visits the top element, marks it, and pushes unvisited adjacent vertices.
Describe how DFS can be used to detect cycles in a graph. By tracking visited and recursion stack, DFS detects back edges indicating cycles.
Explain DFS traversal in disconnected graphs. Loop through all vertices and apply DFS to unvisited ones to ensure complete traversal.

📝 Chapter Summary DFS is a fundamental graph traversal algorithmDFS uses recursion or a stackDFS explores deep paths before backtrackingIt has time complexity O(V + E) and space complexity O(V)DFS works on both directed and undirected graphsIt is used for cycle detection, topological sorting, pathfinding, and component discoveryDFS can be applied to disconnected graphs by running it on all unvisited nodesDFS differs from BFS in terms of strategy, data structure, and applicationDFS can be implemented both recursively and iteratively

📘 Model Paper / Sample Internal Exam Questions