Use depth-first search to produce a spanning tree for the given simple graph

2k Views Asked by At

Use depth-first search to produce a spanning tree for the given simple graph. Choose $a$ as the root of this spanning tree.

enter image description here

Here is answer and I am not sure whether is correct or not

enter image description here

Can anyone verify my answer

1

There are 1 best solutions below

0
On

This is a valid spanning tree, but not a DFS tree.

Hint 1:

In a DFS, a vertex is not marked “finished” until all of its neighbours have been examined.

Hint 2:

Every edge of an undirected graph is either a “tree edge” (an edge occurring in the DFS tree) or a “back edge” (an edge going from a vertex in the DFS tree to one if its ancestors).

Hint 3:

Look at the edge between $g$ and $h$, or the edge between $m$ and $i$.