Difference between revisions of "Graph Traversals"
(→Algorithm) |
(→Algorithm) |
||
| (4 intermediate revisions by the same user not shown) | |||
| 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= |
| + | 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== | ==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. | ||
| Line 14: | Line 16: | ||
Then while we have an item in the queue: | Then while we have an item in the queue: | ||
| − | * Set the Current Node = | + | * Set the Current Node = Front of Queue |
* Set Explored of Current Node = true | * Set Explored of Current Node = true | ||
* Add Current Node to Visited Nodes | * Add Current Node to Visited Nodes | ||
| Line 21: | Line 23: | ||
*** Add neighbour to queue | *** Add neighbour to queue | ||
*** Set Discovered of neighbour to true | *** Set Discovered of neighbour to true | ||
| + | * Dequeue Current Node | ||
==Applications of Breath First Traversal== | ==Applications of Breath First Traversal== | ||
| Line 27: | Line 30: | ||
*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 | ||
| + | |||
| + | ==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 | ||
Latest revision as of 12:30, 15 November 2018
Contents
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
- If Not Discovered
- 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
- If Not Discovered
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
