Code Logo

DFS Graph Traversal

Published at25 Jul 2026
Created by
DFS Medium 0 views
Like0

Given an undirected connected graph represented as an adjacency list (1-indexed), return the DFS (Depth-First Search) traversal order starting from node 1. Each node is numbered from 1 to n, and the adjacency list at index i-1 contains the neighbors of node i.

Use a recursive DFS function with a visited set to avoid revisiting nodes. Start DFS from node 1. For each visited node, add it to the result array, then recursively visit all its unvisited neighbors. The recursive approach naturally implements the depth-first exploration pattern.

Since the graph is undirected, the adjacency list contains bidirectional edges. To maintain a deterministic traversal order, visit neighbors in ascending order (sort the neighbor list before recursing). This ensures consistent output across different implementations.

Time complexity is O(V + E) where V is the number of vertices and E is the number of edges, as each node and edge is traversed exactly once. Space complexity is O(V) for the visited array and recursion stack.

Edge cases include an empty graph (return empty array), a single node with no neighbors (return [1]), and a graph with multiple connected components (but the problem guarantees connectivity).

Example Input & Output

Example 1
Input
[[2],[1]]
Output
[1,2]
Explanation

Two connected nodes

Example 2
Input
[[]]
Output
[1]
Explanation

Single node

Example 3
Input
[[2],[3],[1]]
Output
[1,2,3]
Explanation

Triangle: 1->2->3 (3 connects back to 1)

Example 4
Input
[]
Output
[]
Explanation

Empty graph

Example 5
Input
[[2,4],[1,3],[2,4],[1,3]]
Output
[1,2,3,4]
Explanation

Square: 1->2->3->4

Algorithm Flow

Recommendation Algorithm Flow for DFS Graph Traversal
Recommendation Algorithm Flow for DFS Graph Traversal

Solution Approach

Perform a depth-first traversal of a graph starting from a given node. Use an adjacency list representation. Maintain a visited set to avoid revisiting nodes. Use recursion or an explicit stack to visit each node, process it, and explore its neighbors.

function dfsTraversal(graph, start) {
  var visited = {}, result = [];
  function dfs(node) {
    if (visited[node]) return;
    visited[node] = true;
    result.push(node);
    for (var i = 0; i < graph[node].length; i++) {
      dfs(graph[node][i]);
    }
  }
  dfs(start);
  return result;
}

The recursion visits a node, marks it visited, and recursively visits all unvisited neighbors. The visited set prevents infinite loops in cyclic graphs.

Time complexity is O(V + E), space complexity is O(V).

Best Answers

java
import java.util.*;
class Solution {
    public int[] solution(int[][] adjList) {
        if (adjList == null || adjList.length == 0) return new int[]{};
        int n = adjList.length;
        boolean[] visited = new boolean[n + 1];
        List<Integer> result = new ArrayList<>();
        dfs(1, adjList, visited, result);
        int[] res = new int[result.size()];
        for (int i = 0; i < result.size(); i++) res[i] = result.get(i);
        return res;
    }
    void dfs(int u, int[][] adj, boolean[] visited, List<Integer> result) {
        visited[u] = true;
        result.add(u);
        int[] nbs = adj[u - 1];
        Arrays.sort(nbs);
        for (int v : nbs) { if (!visited[v]) dfs(v, adj, visited, result); }
    }
}