0
$\begingroup$

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:

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

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

$\endgroup$
  • $\begingroup$ You should never assume that lists of properties are exhaustive. If I tell you that I am a man, you don't assume that I am not anything else. If I tell you Barcelona is a nice city, you don't assume that every other city is not nice. If I tell you that Richard Feyman won the Nobel Prize, you don't assume that nobody else did, or that he won no other prizes. $\endgroup$ – David Richerby Jan 25 at 12:58
  • $\begingroup$ yeah...I know that, but when "CLRS" tells something & does not specify something very related, possibly next nearby concept, and also when for many months (possibly a year) no other text / problem expose me that thing while discussing same topics...I have read other 2-3 reference book. No one touched these facts. not at even under different topics, forget about on same page, as I have asked in this question. $\endgroup$ – anir Jan 25 at 13:11
  • $\begingroup$ [continued from last comment] The passage of time and authority of CLRS made me believe in unsaid facts. I believe this is the case with every life fact. When some big personality says something and no one says anything more on that thing for long duration, it becomes normal belief unless someone exposes the other un discussed side. $\endgroup$ – anir Jan 25 at 13:11
  • $\begingroup$ I'm sorry but you misled yourself. You cannot reasonably expect even an authoritative textbook to list every known fact. You cannot reasonably expect them to repeatedly disclaim that they have not listed every known fact or that the failure to mention something as a fact does not necessarily mean that it is false. $\endgroup$ – David Richerby Jan 25 at 13:23
  • $\begingroup$ Yess I know thats also the fact. Please dont take my comments in wrong way. You have also helped me quite a lot of times in understanding concepts. I feel I had such thoughts because I was pissed with the fact that their is no single resource which will list all such related concepts in neat manner at one place. This becomes quite frustrating when you are expecting them to do that, especially when you are preparing for certain exam. Knowing things slowly over a period of time takes away precious time. I could have cleared certain exam far earlier if at least single such resource existed. $\endgroup$ – anir Jan 26 at 16:10
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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:

enter image description here

  • (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.
$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.