Graph Traversal and State

Choose the traversal

BFS explores by distance and naturally finds shortest unweighted paths. DFS explores depth and fits structural or exhaustive questions.

• Distance layers
• Component discovery
• Cycle detection

Model the state

A node alone may not describe a search state. Constraints such as remaining stops or collected keys can be part of the visited key.

• Node identity
• Path-dependent state
• Parent pointers

Debugging

Write down what makes two states equivalent. Incorrect visited logic is the most common source of missing or repeated paths.