DFS (Graph)

Graphs

avgO(V + E)worstO(V + E)spaceO(V)

Start the depth-first search at A

1 / 38

Code

function dfs(graph: Graph, source: number) {  const order: number[] = [];  const seen = new Set<number>();  visit(source);  return order;  function visit(node: number) {    seen.add(node);    order.push(node);    for (const next of graph.neighbours(node)) {      if (seen.has(next)) continue;      visit(next);    }  }}

procedure DFS(G, source)  order ← []  seen ← ∅  visit(source)  return order  procedure visit(node)    add node to seen    append node to order    for each neighbour next of node, in label order do      if next ∈ seen then skip it      visit(next)    ▷ go deeper before trying the next neighbour    end for  end procedureend procedure

Variables

stack=empty

Counters

visited: 0
edges considered: 0

Nodes8

Source

Edges

How it works

Depth-first search follows one branch as deep as it can before backing up to the most recent node that still has an unexplored neighbour. The recursion's call stack remembers the way back, and the edges that lead to new nodes form a depth-first tree.

Complexity

Best: O(V + E)
Average: O(V + E)
Worst: O(V + E)
Space: O(V)

DFS (Graph)

How it works

Complexity

Search algorithms