Understanding connection between minimum spanning tree, shortest path, breadth first and depth first traversal

Question

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.

I have done quick google and found many links, some of which are:1, 2, 3.

My conclusion is:

For unweighted graph,

1. Breadth first search gives both minimum spanning tree and shortest path tree.
2. Depth first search gives only minimum spanning tree but not the shortest path tree.

Now I have further small doubts:

3. 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.

4. 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?

Answer 1

In fact, a MST is a subset of the edges building a tree (thus without cycle) using the minimum edge weights. It has exactly N-1 edges for a N nodes graph.

It may exist several different MST for the same graph. For an unweighted graph, which is in other way a graph with weight 1 on every edges, the total weight of any spanning tree is N-1. Thus any spanning tree is a MST.

When you use BFS or DFS to explore a graph, you build an exploration tree, which is the shortest path tree for BFS. And if the graph is unweighted, you can say this tree is a MST, yes so 1. and 2. are true.

3. is true, MST and SPT are different. Just make BFS and DFS on a 3-clique (3 nodes connected to each other) to have an example.

4. is true but remember that "minimum" adds no information to any spanning tree of an unweighted graph. And also that a N nodes tree has exactly N-1 egdes.

Answer 2

Just putting Vince's answer in more structured manner:

• (Q4) SPT and MST, both being trees, they have same number of edges for unweighted graph, i.e. $n-1$
• (Q1,2) Thus, as long as we have a tree connecting all vertices and thus having n-1 edges, we are ending up with MST, whatever the procedure is followed.
• (Q3) In unweighted graph, SPT will be a MST (as both have same total weight, and total weight is the only constraint put by MST), but reverse is not true (as SPT requires distance from source vertex to every other vertex to be minimum, which is not considered by MST), which can be seen from 3-clique:

• (Q1,2) As can be seen from above, BFS gives SPT which also happen to be MST. But DFS gives MST which may not be a SPT.