Question: You are a Cretan (not cretin) princess who has decided to help Theseus defeat the Minotaur and escape from the labryinth. You've already equipped him with a phaser gun (set to stun - I only write G-rated problems) and a GPS system so that he can identify when he's at different intersections in the labyrinth. Theseus isn't too clever, though, so you also need to tell him how to efficiently visit every intersection and passage in the labryinth so he can find the Minotaur. What algorithm do you suggest? If each passage is a meter long, how far will Theseus have to walk? Your answer should be in terms of n, the number of intersections, and m, the number of passages; do not use big-O notation for your bound. Note that Theseus will have to travel down every passage at least once to be sure he has visited all passages.
Answer: Theseus can use depth-first search. When he gets to a node he's already visited, he'll immediately return. When he gets to a node that he has not yet visited, he'll first travel down the first untraveled passage and recurse on the node he gets to. Once he has completed with that, he will travel down the second untraveled passage. Then the third passage, and so on until he has tried all passages and can return from the recursion.
Depth-first search will visit every node and it will never use an edge twice. So Theseus will walk at most 2m meters.