1
$\begingroup$

I want to construct a DFS and a BFS spanning trees for the graph below. The root is node a. At each step the next edge to be traversed should be the cheapest one.

enter image description here

DFS:

My understanding that to the construct this DFS where each next is the cheapest one, the resultant spanning tree would be:

{(a,c), (c,h), (h,g), (g,f), (f,b), (b,k), (k, j), (j,i), (i, l), (l,m), (m,e), (e,d)}

enter image description here

BFS:

My understanding that to the construct this BFS where each next is the cheapest one, the resultant spanning tree would be:

Queue: a c d b e f h g k m i j k

enter image description here

Is my understanding of spanning trees correct when the next edge to be traversed should be the cheapest one? Is this a MCST?

$\endgroup$
0
$\begingroup$

You can construct a DFS spanning tree or a BFS spanning tree in many ways. You could require the next edge to be traversed should be the cheapest one available, if that helps in any way or if you just like to do that. As long as you are using DFS or BFS, you will end up with a spanning tree.

However, if you do want to always traverse using next cheapest edge among all possible choices, "Queue: a c d b e f h g k m i j k" for BFS should be "Queue: a c d b e f h g k m i j l", which is I assume a typo.

"Is this a MCST?" No, none of the two is a minimum cost spanning tree, which is more commonly called minimum spanning tree (MST). The DFS spanning tree, {(a,c), (c,h), (h,g), (g,f), (f,b), (b,k), (k, j), (j,i), (i, l), (l,m), (m,e), (e,d)} could have less cost if (g,f) is replaced by (c,f). The BFS spanning tree, {(a,c), (a,d), (a,b), (a,e), (c,f), (c,h), (b,g), (b,k), (e,m), (h,j), (k,l)} could have less cost if (b,g) is replaced by (h,g). As you can see, there is no guarantee that a MST can be obtained if you use a DFS or BFS.

In fact, for this particular graph, no matter how you conduct BFS or DFS, you will not end up with a MST.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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