Simple graph-traversal algorithms

Be able to trace breadth-first and depth-first search algorithms and describe typical applications of both.

Bredth-first

Tracing breadth-first

Applications of bredth-first search

Shortest Path and Minimum Spanning Tree for unweighted graph
P2P networks - used to find all neighbour nodes
Social Networking Websites - finding people who are k away from you (friend of a friend etc)

Depth-first

Tracing depth-first

Applications of depth-first search

Solving puzzles with only one solution - e.g. mazes
Detecting cycle in a graph - A graph has cycle if and only if we see a back edge during DFS. So we can run DFS for the graph and check for back edges.

Additional information

Breadth-first: shortest path for an unweighted graph. Depth-first: Navigating a maze.