Traversing a graph Vs Traversing a tree

Question

Would a function that traversed a graph work equally well to traverse a tree?

Answer 1

Well a tree is just a special type of graph called a directed acyclical graph, so yes...Breadth First and Depth First traversal both work on a tree.

I could write out a detailed explanation of the differences between breadth and depth first traversals, but I'd probably get it wrong (I'm not a heavy comp-sci guy yet).

Suffice it to say that the only difference between breadth and depth first traversal is the order in which you process the vertices. Breadth first you can think of as adding vertices to a "to-be-processed" queue. Depth first you can think of as adding the vertices to a "to-be-processed" stack. When it comes time to process the vertices (after they've been added to their respective data structures) you dequeue or pop the stack to get the next vertex to process. Clever versions of depth first traversal use recursion to process the vertices instead of adding them to a stack.

I have no idea whether this was helpful or not...

A quick google search (I don't know whether it was breadth or depth first) finds this which seems pretty good at describing the differences between BFS and DFS. I can also recommend Steve Skiena's The Algorithm Design Manual if you want to get a more in depth read.

Answer 2

A function that could traverse a general graph might be overkill for traversing a tree, because in a pure tree you don't have to check for cycles. So it would work, but so would something simpler.