BFS and DFS

The order you expand neighbour states decides breadth-first vs depth-first search.

BFS: use a queue — finish nearby states before going deeper. Finds a shortest path when every edge has equal cost.
DFS: use a stack — dive deep along one branch first.

BFS expands level by level; DFS dives down one branch (numbers = visit order).

Missionaries and cannibals

State $(m,c,b)$ = missionaries and cannibals on the left bank, and whether the boat is on the left. Goal $(0,0,0)$. Illegal if cannibals outnumber missionaries on either bank.

BFS and DFS both explore the same graph but visit states in different orders — BFS tends to find a shallow solution first.

Key takeaways

BFS = layer by layer; shortest unweighted path.
DFS = deep trails first.
Good state representation is half the work.