Due Tuesday, Dec.12
For an undirected graph G and the
ST(G,s)
algorithm in class, show that G has no path from s
to v in G shorter than the one in T
obtained by using a FIFO
queue. In
other words, show that T is a Shortest Path tree measuring path
length in the number of edges (i.e. each edge has length 1). Yet another way
of stating it is to prove that the (shortest path) distance of v from s
in G is equal to the depth of v in the tree
T (rooted in s).
Show the result of (a) BFS (ST, using queue) and (b) the
result of DFS (ST using stack) on a clique K_{6}
of 6 nodes. And now, (c & d)on a complete bipartite graph K_{4,4}.
(e) How will these results look for a general K_{n}?
We have discussed the ST(G,s) algorithm for undirected graphs
in class. What happens when you run it on a directed graph? Draw all the possible
results (for all orders of selecting edges of a visited node for storage) of
both BFS and DFS for this graph:
Can the the red edges be the tree T output by ST(G,s) if the storage is implemented as (a) stack, (b) queue?
Draw all possible outcomes for (a) and (b).