Graph Traversals

Overview

https://www.youtube.com/watch?v=GeUlf-m0-Hw&list=PLCiOXwirraUB0HOYmEbmx-7KStKtoXZ6E

Breath First Traversal

The purpose of this traversal is to examine the width of the graph as soon as possible, the queue means the oldest discovered edge will be the next node explored. This ensures all of the nodes at a given level are explored before moving to the next level.

Algorithm

For this algorithm we will use a queue to store the nodes we need to visit. We should also maintain a list of the nodes we visit. Every node also has a setting to say if it has been discovered or not, it will also have a setting to say when it has been completely explored. The node will be completely explored when each neighbour has been discovered.

So we:

• Create structure to store Discovered & Completely Explored
• Create structure for Visited Nodes
• Add starting node to the queue

Then while we have an item in the queue:

• Set the Current Node = Front of Queue
• Set Explored of Current Node = true
• Add Current Node to Visited Nodes
• For each neighbour of Current Node
  • If Not Discovered
    • Add neighbour to queue
    • Set Discovered of neighbour to true
• Dequeue Current Node

Applications of Breath First Traversal

• Identifying the shortest path between 2 points (GPS etc)
• Showing relationships between connected nodes (Facebook)
• Web crawlers analyse the sites you can reach by following links on another site

Depth First Traversal

The purpose is to examine the depth of the structure as soon as possible, the stack means it examines the most recently discovered nodes first.

Algorithm

For this algorithm we will use a Stack to store the nodes we need to visit. We should also maintain a list of the nodes we visit. Every node also has a setting to say if it has been discovered or not, it will also have a setting to say when it has been completely explored. The node will be completely explored when each neighbour has been discovered.

So we:

• Create structure to store Discovered & Completely Explored
• Create structure for Visited Nodes
• Add starting node to the Stack

Then while we have an item on the Stack:

• Set the Current Node = Stack.Pop
• Set Explored of Current Node = true
• Add Current Node to Visited Nodes
• For each neighbour of Current Node
  • If Not Discovered
    • Push neighbour to Stack
    • Set Discovered of neighbour to true

Applications of Depth First Traversal

• Solving puzzles with a single solution (eg maze)
• Path finding, the items on the stack when your reach destination should be the path
• Finding cycles in a graph