Question

If you are doing a depth first traversal of this graph beginning at C and always choose the vertex with the smallest name alphabetically (if there is a choice), can the traversal be made without backtracking? A) no B) yes C) can't determine yes O can't determine no

Answer 1

The given adjacency matrix with weights represent an undirected graph as it is symmetric. Keeping the node C as root, we can design a reader freindly view as the following:

As it has be asked to chose the vertex with smallest alphabetical order, the weights of the edges are disregarded here.

With the graph in hand:

1) We start with C and choose A as next out of { A B E F} beacause it is alphabetically lowest. A is marked as visited.

2) From A onward we choose B out of {B D G} with the same reason as above and mark it as visited.

3) From B onward, we don't have any unvisited neighbour to it and hence, we backtrack to A to choose D from {D G}.

Hence, it is clear that, with the given requirements, we can not perform a depth first traversal in the given graph.

Hope this helps! It it does, please thumbs up!

In case of any clarification, please comment!