| title | date | lastmod |
|---|---|---|
Depth First Search |
2022-11-08 |
2022-11-21 |
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)