(Breadth-First Search) Let i and j be two nodes of a directed graph (N , A). (a) Consider the following algorithm, known as breadth-first search, for finding and mark each node n ∈ Tk+1 with the label...

(Breadth-First Search) Let i and j be two nodes of a directed graph (N , A). (a) Consider the following algorithm, known as breadth-first search, for finding

and mark each node n ∈ Tk+1 with the label “(m, n)” or “(n, m),” where m is a node of Tk such that (m, n) or (n, m) is an arc, respectively. The algorithm terminates if either (1) Tk+1 is empty or (2) j ∈ Tk+1. Show that case (1) occurs if and only if there is no path from i to j. If case (2) occurs, how would you use the labels to construct a path from i to j? (b) Show that a path found by breadth-first search has a minimum number of arcs over all paths from i to j. (c) Modify the algorithm of part (a) so that it finds a forward path from i to j.