Graphs

The most common topics in graphs are Breadth First Traversal, and Depth First Traversal.

Think of graphs as trees with cycles. Thus, unlike a tree traversal, you need to make sure you are not moving around in cycles. Other differences are that most graph based questions often involve structures with more than two child nodes per node, and disconnected structures.

Breadth First

  • Usually implemented using a queue
  • In practice, may take more memory than DFS.
  • The go-to algorithm for questions involving shortest distances (or nodes less than 2 hops away etc).

Depth First

  • Usually implemented using recursion
  • In practice, takes less memory than BFS
  • The go-to algorithm for questions involving paths

Basic questions

Find if there is a path between two given nodes in a graph.

Advanced questions

A Knight is at location (0,0) on a 8 X8 chessboard. Find the minimum number of steps needed to reach square (0,3).

A Knight is at location (0,0) on a chessboard. Enumerate its path (points in needs to visit in order) to (3, 3), if such a path exists.
Example: The path to (4,2) is (0,0), (2,1), (4,2).

Your are given a set of processes and a dependency graph. (Each process has a depends on node which points to another process in the set, if the former depends on the latter).

Optional reading