DSA-VerseLearn by watching code run
DashboardData StructuresAlgorithmsVisualizerCORECoding PlaygroundInterview QuestionsComplexity AnalyzerLearning NotesBookmarksLearning ProgressSettings
Graph Algorithms algorithms

Graph Algorithms

Graph DFS (Depth-First Search)

Goes as deep as possible along each branch before backtracking. This recursive version uses the call stack as its implicit stack.

Worst O(V + E)Space O(V)
Open visualizer

1Detailed explanation

Depth-first search follows one branch as deep as possible before backtracking. The recursive version uses the call stack to remember where to continue.

Each vertex is marked visited on entry so cycles do not cause infinite recursion. When all neighbours of a vertex are handled, the function returns — that is the backtracking step.

DFS is the basis for cycle detection, topological sorting, connected components and many backtracking algorithms.

2Pseudocode

procedure DFS(G, u, visited)
  visited ← visited ∪ {u}
  visit u
  for each neighbor v of u
    if v ∉ visited
      DFS(G, v, visited)

3Interactive visualization

Graph DFS (Depth-First Search)interactive Open full visualizer
ABCDEFG

Call stack (bottom → top)

A

Traversal order

—
Current vertexOn call stackDiscoveredFinishedUnvisited

Goes as deep as possible along each branch before backtracking. This recursive version uses the call stack as its implicit stack.

1 / 67

4Implementations

Equivalent implementations in four languages — the same code the visualizer highlights line by line. Each is a complete program.

function dfs(graph, node, visited, order) {
  visited.add(node);
  order.push(node);
  for (const neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited, order);
    }
  }
}

const edges = [["A", "B"], ["A", "C"], ["B", "D"], ["B", "E"], ["C", "F"], ["E", "F"], ["D", "G"], ["F", "G"]];
const graph = {};
for (const [u, v] of edges) {
  (graph[u] ??= []).push(v);
  (graph[v] ??= []).push(u);
}
const visited = new Set();
const order = [];
dfs(graph, "A", visited, order);
console.log("DFS order:", order.join(" -> "));

5Time and space complexity

Time
Best caseO(V + E)
Average caseO(V + E)
Worst caseO(V + E)
Space
AuxiliaryO(V)
InputO(V + E)
TotalO(V + E)

Time: dfs() is called once per reachable vertex (O(V)) and each call scans that vertex's adjacency list once, so all edge checks together are O(E). Total O(V + E).

Space: The visited set holds up to V vertices and the recursion can go V levels deep on a path-shaped graph → O(V) auxiliary space.

6Common interview variations

  • Iterative DFS with an explicit stack.
  • Count connected components.
  • Detect a cycle in an undirected / directed graph.
  • Topological sort.
  • Find all paths from source to target.

On this page

  1. 01Detailed explanation
  2. 02Pseudocode
  3. 03Interactive visualization
  4. 04Implementations (JS · Python · Java · Go)
  5. 05Time and space complexity
  6. 06Common interview variations