Depth First Search (DFS)

DFS is usually implemented via stack or by recursion (via the call stack). Depth-first is naturally associated with stack, going down would be pushing into the stack and backtracking would be popping out from the stack.

Recursive vs iterative visiting order

"These two variations of DFS visit the neighbors of each vertex in the opposite order from each other: the first neighbor of v visited by the recursive variation is the first one in the list of adjacent edges, while in the iterative variation the first visited neighbor is the last one in the list of adjacent edges. The recursive implementation will visit the nodes from the example graph in the following order: A, B, D, F, E, C, G. The non-recursive implementation will visit the nodes as: A, E, F, B, D, C, G."

  • Combinations
    • Order doesn't matter. Same element cannot be used twice
  • Permutations
    • Order does matter. Same element cannot be used twice

References

results matching ""

    No results matching ""