Graph Traversals

What is graph traversing

A way of visiting different nodes on a graph. There are two types, Depth first(using a stack) and breadth first(using a queue)

Depth first Traversal

First, push A onto the stack and mark it as visited. Then Push B onto the stack and mark it as visited (you choose from either B or D).

Next, you push C to the stack and mark it as visited

You then push E to the stack(you can choose E or D).

Because node E has no neighbours, we remove it from the stack and see if node C has any neighbours that haven't already been visited. Node D has not been visited, so it is pushed to the top of the stack.

D has no neighbours, so it popped. C has no unvisited neighbouring nodes, so it is popped, as are B and A. The stack is now empty, and the search is finished.

Breadth first

Firstly, we enqueue()(add) a node onto the queue. We will choose node A.

Next we visit all of its neighbouring nodes and enqueue it onto the queue.

Since there are no more neighbouring nodes, A is dequeued(remove) the top item from the queue. It's now been visited. Remember its first in first out (FIFO) with queues.

Now you enqueue all the connecting nodes of B which is node C.

Since all of it's child nodes have already been visited, we can dequeue node B. D is also dequeued because there are no connecting nodes.

Finally we enqueue all of node C's neighbours. E is enqueued

Since E has no neighbouring nodes, C is dequeued along with E since it too has no neighbours that haven't already been visited.

Summary

Breadth Traversal(Queue) - You only dequeue if have visited and enqueued all of its neighbouring/child nodes.

Depth Traversal(Stack) - You can pop if you have no more visited child/neighbouring nodes.

To learn about graphs click here or to read about different topics, click here