Difference between revisions of "Graph Traversals"
(Created page with "=Overview= <youtube>https://www.youtube.com/watch?v=GeUlf-m0-Hw&list=PLCiOXwirraUB0HOYmEbmx-7KStKtoXZ6E</youtube> https://www.youtube.com/watch?v=GeUlf-m0-Hw&list=PLCiOXwirra...") |
(→Depth First Traversal) |
||
| Line 5: | Line 5: | ||
=Depth First Traversal= | =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 | ||
=Breadth First Traversal= | =Breadth First Traversal= | ||
Revision as of 11:46, 15 November 2018
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
