Difference between revisions of "Graph Traversals"
(→Depth First Traversal) |
(→Algorithm) |
||
| Line 21: | Line 21: | ||
*** Add neighbour to queue | *** Add neighbour to queue | ||
*** Set Discovered of neighbour to true | *** 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 | ||
=Breadth First Traversal= | =Breadth First Traversal= | ||
Revision as of 11:48, 15 November 2018
Contents
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
- If Not Discovered
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
