Consider the following procedure below to traverse a tree (i.e. visit each node - in case of the tree, also traversing each edge on the way).

Let
**T**=(**V**,**E**), where **V** is the set of nodes, and **E**=**VxV**
is the set of edges.

We will use a "storage" data structure **S**. The specifics of
it will be described later (and will play crucial part in the specific properties
of the traversal), but it is a generic storage - it has methods to **store**
an element (add it to the storage), **extract**
an element (remove some element - chosen by the storage), as well as check whether
the storage is **empty**.
As any data structure, it has the **init**
method to create a new storage, initially empty.

Explore (T, s)

// explores treeTstarting from the vertexs("node" = "vertex")init(S)

// create empty storage Sstore(<s,(ss)>, S)

// insert s into the storage S, together with loop edge

whilenot empty(S)do<v,(uv)> <-- extract(S)

// extract from S a node+edge and visit the nodevisit(v,(uv))

// this subroutine does all processing needed for the nodesv.visited <-- true

// it also sets, and marks edge (uv), if needed

for allw:(vw) in E

ifnot w.visitedthenstore( <w,(vw)>, S )

How is the above related to the travesal schemes you already know?

It is really both! It all depends on how storage works:

**DFS**: storage S is a **stack**, store=push;
extract=pop.

**BFS**: storage S is a **queue**, store=enqueue;
extract=dequeue.

What do you need to change in the above to explore graphs (instead of trees)? - Nothing!

The same algorithm using stack will expore a graph in DFS order and will generate
a DFS tree if you use **stack**, and if you use **queue** it will generate
a BFS tree.

Just for fun: what would happen if you use other storage strucutres? Like **priority
queue**? The answer depends on what we will use as the key when storing pair
<w, (vw)>: if we use the weight of edge (vw)
as the key then the marked edges form a Minimum Weight Spanning Tree. We can
even use mergable priority queues (leftist heaps with lazy deletion, using disjoint
sets) to explore the graph from multiple starting points "in parallel".

If we are careful and clever, we can use the shortest distance from s to w, when storing <w,(vw)>, going via node v. In that case, what we will get is the shortest path (from s) tree.