Difference between revisions of "Graph Traversals"
(→Algorithm) |
(→Depth First Traversal) |
||
Line 4: | Line 4: | ||
https://www.youtube.com/watch?v=GeUlf-m0-Hw&list=PLCiOXwirraUB0HOYmEbmx-7KStKtoXZ6E | https://www.youtube.com/watch?v=GeUlf-m0-Hw&list=PLCiOXwirraUB0HOYmEbmx-7KStKtoXZ6E | ||
− | = | + | =Breath First Traversal= |
==Algorithm== | ==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. | 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. |
Revision as of 11:50, 15 November 2018
Contents
Overview
https://www.youtube.com/watch?v=GeUlf-m0-Hw&list=PLCiOXwirraUB0HOYmEbmx-7KStKtoXZ6E
Breath 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