I've conducted hundreds of programming interviews for Google, and I'd expect any good candidate to need way less than 45 minutes to code up a graph traversal in arbitrary order, even if I believed that they didn't already know an algorithm for doing so.
