Depth First Search

Last updated Nov 8, 2022 Edit Source

Assuming ties are handled in alphabetical order

Expansion Order: A > B > C > E > F > G Final Path: A > B > C > E > F > G

A recursive implementation of DFS:

procedure DFS(G, v) is label v as discovered for all directed edges from v to w that are in G.adjacentEdges(v) do if vertex w is not labeled as discovered then recursively call DFS(G, w)

A non-recursive implementation of DFS with worst-case space complexity O(E)

procedure DFS_iterative(G, v) is let S be a stack S.push(v) while S is not empty do v = S.pop() if v is not labeled as discovered then label v as discovered for all edges from v to w in G.adjacentEdges(v) do S.push(w)