Depth-first search is different from Breadth-first search in the following ways: A depth search traversal technique goes to the deepest level of the tree first and then works up while a breadth-first search looks at all possible paths at the same depth before it goes to a deeper level. When we come to a dead end in a depthfirst search, we back up as little as possible. We try another route from a recent vertex-the route on top of our stack. In a breadth-first search, we want to back up as far as possible to find a route originating from the earliest vertices. So the stack is not an appropriate structure for finding an early route because it keeps track of things in the order opposite of their occurrence-the latest route is on top. To keep track of things in the order in which they happened, we use a FIFO queue. The route at the front of the queue is a route from an earlier vertex; the route at the back of the queue is from a later vertex.
