Depth First Search or DFS for a Graph Easy 0 attempts
GeeksforGeeks ↗

Depth First Search or DFS for a Graph

Easy GraphBFSDFS GeeksforGeeks

You're given a graph as an adjacency list adj, where vertices are numbered 0 through V - 1 (with V = adj.length), and adj[i] lists the neighbors reachable directly from vertex i. Starting at vertex 0, perform a depth-first search (DFS) and return the sequence in which vertices are first reached (a preorder-style traversal).

Follow the standard DFS approach: fully explore one neighbor's branch before backtracking to try the next, visiting neighbors in the order they appear in each adjacency list as listed.

Input Format
Implement dfsOfGraph(adj). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
adj = [[1,2],[3],[4],[],[]]
Output
[0,1,3,2,4]

Example 2

Input
adj = [[2,1],[0],[0]]
Output
[0,2,1]
Constraints
  • 1 <= V <= 10^4
  • 0 <= E <= 10^4
  • Neighbors are visited in the listed order; vertices unreachable from 0 are omitted.
Test Cases (2)
Case 1
Args: [[[1,2],[3],[4],[],[]]] Expected: [0,1,3,2,4]
Case 2
Args: [[[2,1],[0],[0]]] Expected: [0,2,1]
Topics
GraphBFSDFS

Iterative DFS

Push neighbors in reverse order so they are visited in the original adjacency-list order. Mark a vertex when it is popped for its first visit; later duplicate stack entries are skipped.

javascript
function dfsOfGraph(adj) {
  const visited=new Set(),stack=[0],result=[];
  while(stack.length){const u=stack.pop();if(visited.has(u))continue;visited.add(u);result.push(u);for(let i=adj[u].length-1;i>=0;i--)if(!visited.has(adj[u][i]))stack.push(adj[u][i]);}
  return result;
}

Time: O(V + E) | Space: O(V + E)

Saved in this browser only. Private to you.

JavaScript