Track 16 · Lesson 11 of 12

Graphs: routes, networks and hierarchies

Represent connections as adjacency lists, find shortest routes with breadth-first search, and explore networks and org charts with depth-first search.

You will be able to

• Model roads, friendships and reporting lines as graphs stored in a dict of adjacency lists
• Find the shortest route by number of steps with breadth-first search and rebuild the path
• Explore everything reachable with depth-first search, iteratively or recursively
• Count connected components and protect searches against cycles with a visited set