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?

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top