Algorithms and Data Structures for Programming Contests

Graph Traversal Algorithms (Cont'd)

Regroup (2)

High-level solution?

1. Perform BFS — not DFS — on the implicit graph defined by knight moves.

What's an "implicit graph"?

• A graph whose edges are not stored explicitly, but rather computed from other information.

Why BFS and not DFS?

• Both are guaranteed to find all reachable nodes, but BFS guarantees to do this using the smallest possible number of edges — as required.

To learn more...

• Wikipedia entry on Depth-first search.
• Wikipedia entry on Breadth-first search.

Back to Algorithms

© Copyright 2012–2015 François Pitt <francois.pitt@utoronto.ca>
last updated at 08:25 (EST) on Thu 5 Mar 2015
Algorithms and Data Structures by François Pitt is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.