Algorithms - Traversals

Traversals

What is a traversal? It's when you visit every node of a tree or graph using the edges.

Tree traversal

Let's talk about 3 methods of traversing trees (Note: Always start at the root)

• Depth-First-Search: Visit all the descendants of a node before visiting the sibling nodes. You have to visit some nodes more than once in a DFS, this is called backtracking


• Breadth-First-Search: Visit all children of a node before visiting sibling nodes


• Priority Search: Nodes are given priorities, and the children of the node that haven't been visited yet with the highest priority are visited first

So let's try these on a tree. Here's one I made earlier:

• A left-most first DFS would visit the nodes in this order: A, B, D, E, C, F.


• A right-most first DFS goes like this: A, C, F, B, E, D.


• Right-most first BFS: A, C, B, F, E, D.


• Left-most BFS: A, B, C, D, E, F.

First things first: A tree is a type of graph. Think about it...it has nodes and edges and stuff! It's a special type of graph though, because it has a root node, and as you know it's possible to get from the root to any node.

Why is this important? Because now we can use our tree traversals on graphs.

Graph traversal

First we need to change the traversal rules slightly to make them more graph suitable. We can revisit nodes, so this is achieved by marking each node as unvisited, and then changing this to visited when we visit it (obviously). Only continue traversal from unvisited nodes.

Also, unlike with trees, there might be more than one node that can reach all the others, so instead of starting from one node each time, we pick a node, do the traversal, pick an unvisited node and do the traversal again until all the nodes have been visited.

Let's try these out now on a digraph, which is an extension of the tree from earlier:

• DFS: A, B, D, E, C, F, G, H, I, K


• BFS: A, B, C, D, E, F, G, H, I, K

Traversal algorithm

You probably guessed there's an algorithm to do this, and it's recursive. For now we're just talking about the DFS algorithm.

Here's the psuedo code for it: Note: This is the same pseudo code as appeared in the notes (copyright University of Manchester etc). (I didn't see the point in rewriting it as it will be identical code)



Let's briefly talk over the code:

• For every node it assigns it a 'dfs value' of zero


• It makes a variable called i that starts at zero


• When a node is visited, it increments i by one, changes the dfs value to i, and then visits all the adjacent nodes that are unvisited (this is the recursive part)


• Then it calls the visit function to visit all the nodes that are unvisited

That's all for now!