Difference between revisions of "Graph Traversals"
(→Depth First Traversal) |
(→Breadth First Traversal) |
||
| Line 27: | Line 27: | ||
*Web crawlers analyse the sites you can reach by following links on another site | *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 | ||
Revision as of 11:54, 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
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
- If Not Discovered
