Finding goal through BFS and DFS

Question

I have this undirected, unweighted graph:

I need to find the search paths from node S to node O using depth-first search (DFS) and breadth-first search (BFS). Ties should be broken alphabetically.

I understand that with DFS it goes from P to Q, from Q to R, from R to W, and then from W I am not sure: Does it go to Z or to V?

Also how will this work with BFS?

Answer 1

from W I am not sure: Does it go to Z or to V?

Since neither Z nor V was visited yet, it's a tie, and your DFS will choose V, as it comes first in the alphabet.

The traversal order for DFS will be:

S P Q R W V U X Y Z O

Special about this graph is that a DFS traversal will visit all nodes without backtracking. At every stage, there is still a neighboring node that was not visited yet... up until the target node O is encountered.

The traversal order for BFS will visit nodes in the order of their distance to S, and when that distance is equal, in alphabetical order. Visually this means that nodes on the same diagonal (in / direction) will be visited after eachother, in alphabetical order:

S P Q U R V X W Y Z O