In CLRS, in the later part of breadth first search topic, for unweighted graphs, it says:
At the beginning of this section, we claimed that breadth-first search finds the distance to each reachable vertex in a graph $G=(V,E)$ from a given source vertex $s \in V$ . Define the shortest-path distance $\delta(s,v)$ from $s$ to $v$ as the minimum number of edges in any path from vertex $s$ to vertex $v$; if there is no path from $s$ to $v$, then $\delta(s,v)=\infty$. We call a path of length $\delta(s,v)$ from $s$ to $v$ a shortest path from $s$ to $v$.
So for many months, I was content with the fact that for unweighted path, BFS gives shortest path. But today I came across problem asking whether breadth first search gives minimum spanning tree for unweighted graph. I was like, BFS gives shortest path not the minimum spanning tree. And to my surprise I was wrong. Somehow, stupidly, I assumed what CLRS stated was the only connection among minimum spanning tree, shortest path, depth first search and breadth first search, because I was subconsciously thinking that its not given in CLRS (in any of four sections), then it should not be the case. I did not give any extra thought for evaluating any possible connection. But now I want to know what all are the connection.
My conclusion is:
For unweighted graph,
- Breadth first search gives both minimum spanning tree and shortest path tree.
- Depth first search gives only minimum spanning tree but not the shortest path tree.
Now I have further small doubts:
I know for weighted graph MST and SPT are not same. But are they same for unweighted graph? Somehow I feel no, as otherwise point 2 will be wrong, and DFS would have given both MST and SPT for unweighted graph. However I am not able to come up with the unweighted graph for which MST and SPT are different.
MSTs given by BFS and DFS on given unweighted graph may be different, its just that the number of edges contained in them will be the same.
Which of above points are correct and which are wrong?