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.

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?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top