Graph Traversal: Depth First Search¶

Motivation¶

Knight’s Tour
Maze Generation & Solving
Topological Sort
Detecting a cyclic graph

Definition¶

Given a graph G and starting vertex s, depth first explores all levels of a graph, backtracking to the nearest unvisited neighber when it reaches a visited vertex.

Attributes¶

{is_visited | is_dirty | color}
frontier

Operations¶

traverse(G, s)