Graph-traversal algorithms

Question 1

What are the two types of way to traverse a graph so that every node is visited?

Answer 1

• Depth first

- Breadth first

Question 2

What does a depth-first traversal use?

Answer 2

It uses a stack with a recursive or non recursive routine

Question 3

What does a breadth-first traversal use?

Answer 3

It uses a queue with an iterative routine

Question 4

How does a depth-first traversal work?

Answer 4

We go as far down one route as we can before backtracking and taking the next route

Question 5

How does a breadth-first traversal work?

Answer 5

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..

Question 6

What are some applications of depth-first traversals?

Answer 6

• Used in solving problems such as mazes which can be represented as graphs

Question 7

What are some applications of breadth-first traversals?

Answer 7

• 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)