Breadth First Search Input Output Shortest sub-path lemma Updated output Solution, BFS Shortest path lemma Proof of correctness of BFS Solution to a similar problem, DFS Properties of DFS Parenthesis theorem theorem White path theorem theorem