Graph-traversal algorithms Flashcards Preview

Paper 1 - Computer Science > Graph-traversal algorithms > Flashcards

Flashcards in Graph-traversal algorithms Deck (7)
Loading 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)