Find a DFS,BFS spanning tree.

Question

Is my answer right?

I think I understood the definition of BFS and DFS spanning tree, but I'm not sure my answer is right.

If it is wrong, please correct it.

Answer 1

At every stage in your algorithm you need to choose which adjacent vertex you move to; I assume you are doing this in alphabetical order, however you should really specify this. You should also specify your starting vertex, which I assume is $a$, but again should be specified.

Your DFS tree for (a) is correct. We add vertices in the order $a,b,c,d,e,f$ before we run out of unvisited neighbours, then backtrack to $c$ where $g$ is the last vertex to be added.

Your BFS tree for (a) does not match what I got. We first exhaust all neighbours of $a$, i.e. adding edges $ab$ then $ag$. Next, we look at $b$, and add $bc$ (but not $bg$, since $g$ is already visited. Then from $c$ we add $cd$ and $cf$(but not $cg$. Finally from $d$ we add $de$, and at this point all vertices have been added to the graph, and we are done.

For part (b) I cannot work out what you have done. For the DFS, if you start from vertex $a$, then we can add vertices in the order $a,b,c,d,f,g,i,h$ before we run out of unvisited neighbours. At this point we need to back track as far as $d$ to find an unvisited neighbour, at which point we add the edge $de$, and now all vertices are included.

Your BFS tree for (b) looks correct, assuming you start at $a$.