CS-330: Algorithms

Tree Traversals and Spanning Trees

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 tree T starting from the vertex s ("node" = "vertex")

init(S)    // create empty storage S

store(<s,(ss)>, S) // insert s into the storage S, together with loop edge

while not empty(S) do

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

visit(v,(uv)) // this subroutine does all processing needed for the nodes
// it also sets
v.visited <-- true, and marks edge (uv), if needed

for all w : (vw) in E

if not w.visited then store( <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.

Graphs

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.