Graph-traversal algorithms Flashcards
What are the two types of way to traverse a graph so that every node is visited?
- Depth first
- Breadth first
What does a depth-first traversal use?
It uses a stack with a recursive or non recursive routine
What does a breadth-first traversal use?
It uses a queue with an iterative routine
How does a depth-first traversal work?
We go as far down one route as we can before backtracking and taking the next route
How does a breadth-first traversal work?
From the current node, visit all the nodes adjacent to it before moving to the next item in the queue and repeating the process for each node at this ‘level’ before moving to the next level..
What are some applications of depth-first traversals?
- Used in solving problems such as mazes which can be represented as graphs
What are some applications of breadth-first traversals?
- Used to find the shortest path between two points (used in GPS navigation)
- Webcrawler (they analyse all the sites you can reach by following links randomly on a particular website)