DFS & BFS Spanning Trees

Question

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.

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)}

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

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

Answer 1

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.