DFS TRAVERSAL

Practice Link

Given a graph G, Depth First Search traverses all nodes by going ahead to all the levels, when no more nodes are left in current path, it backtracks.

Output: [1,2,5,6,3,4,8,7]

Intiution#

DFS explores a graph by committing fully to one path before backtracking — it recurses as deep as possible along each branch before trying siblings. This mirrors the call stack naturally, making recursion the most straightforward implementation.

• Maintain a visited array to avoid visiting twice.
• Traversal terminates when all nodes are completely explored.
• At each node, recursively visit every unvisited neighbor before returning; this guarantees all reachable nodes are covered exactly once.

Implementation#

void dfs(vector<vector<int>>& adj, vector<int> &ans, int source, vector<bool> &visited)
{
    if(visited[source])
        return;
        
    ans.push_back(source);
    visited[source] = true;
        
    for(auto neighbor: adj[source])
    {
        dfs(adj, ans, neighbor, visited);
    }
}

vector<int> dfsOfGraph(vector<vector<int>>& adj) {
    vector<int> ans;
    vector<bool> visited(adj.size(), 0);
    dfs(adj, ans, 0, visited);
    return ans;
}

Complexities#

Time Complexity: O(V+E),#

We are exploring every vertex V and exploring all its edges.

Space Complexity: O(N)+O(V+E),#

O(N) to keep visited nodes, and O(V+E) to create the adjacency list.