Execute a depth-first search traversal of the graph below, starting at F and sto

Question

Execute a depth-first search traversal of the graph below, starting at F and stopping the traversal once E is reached. At a given vertex, when there are multiple edges to the next level, explore edges in alphabetical order of the adjacent vertex. For example, the first edge to explore will be the edge that connects F to C, since C comes before H in the alphabet.

List all of the vertices visited, in order of when they were first visited. If the traversal requires back-tracking, do not include a vertex visited for the second or subsequent time.

Explanation / Answer

Start with F

1. We can see that F can move to either C or H, C is alphabetically smaller than H then move to C
F C
2. We can see that C can move to either H,D or E as D is alphabetically smaller than H, E then move to D
F C D
3. We can see that D can move to B, so move to B
F C D B
2. We BACKTACK to C AND C can move to either H or E . As E is alphabetically smaller than H, move to E and our DFS stop
F C D B E

Because it was said to stop at E

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.