Graph Traversals

Overview

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

Depth First Traversal

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 = dequeue node
• 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

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