Computing Distance

We begin with the problem we want to solve:

As we have seen, we can solve the above problem using BFS. Here is the algorithm statement:

					\\Input: G=(V,E) and s in V

					Run BFS on G with start vertex s and let T be a BFS tree
					
					for(every t in connected component of s)
					{
						dist[t]= ComputeDist(s, t, T);
					}

					return dist;

				

Note that in the above ComputeDist(s, t, T) computes the distance between s and t in the tree T. This can be easily be done if e.g. the BFS tree T produced by the BFS has all the edges pointing towards the root s. Finally, the correctness of the algorithm above follows from (3.3) on page 80 in the textbook.

Why not DFS?

Given that DFS and BFS were equivalent in exploring the graph (and e.g. computing connected component), it is natural to propose the following "algorithm" to compute distances

                                        \\Input: G=(V,E) and s in V

                                        Run DFS on G with start vertex s and let T be a DFS tree

                                        for(every t in connected component of s)
                                        {
                                                dist[t]= ComputeDist(s, t, T);
                                        }

					return dist;
                                

Not so fast...

It turns out that the "algorithm" above is incorrect. For example consider the following (undirected) graph $G=(\{A,B,C,D\}, \{(A,B), (B,C), (C,D), (D,A)\})$, i.e. this is a cycle with four nodes. Now let $s=A$. In this case the DFS will either go to $D$ first (in which case the algorithm above will output dist[B]=3 instead of the correct answer of $1$) or it will go to $B$ first )in which case the algorithm above will output dist[D]=3 instead of the correct answer of $1$.