Depth-First Traversal

This idea of exploring a neighbor’s entire subgraph before moving on to the next neighbor is known as Depth First Traversal.

What we just did in DepthFirstPaths is called “DFS Preorder.”

  • DFS Preorder: Action is before DFS calls to neighbors.
    • Our action was setting edgeTo.
    • Example: edgeTo[1] was set before
    • DFS calls to neighbors 2 and 4.
  • One valid DFS preorder for this Graph: 012543678
    • Equivalent to the order of dfs calls.

Could also do actions in DFS Postorder.

  • DFS Postorder: Action is after DFS calls to neighbors.
  • Example: dfs(s):
    • mark(s)
    • For each unmarked neighbor n of s, dfs(n)
    • print(s)
  • Results for dfs(0) would be: 347685210
  • Equivalent to the order of dfs returns.

So too are there many Graph traversals, given some source:

  • DFS Preorder: 012543678 (dfs calls).
  • DFS Postorder: 347685210 (dfs returns).