4.3.1.1 Simple graph-traversal algorithms

Question 1

What is traversal?

Answer 1

Traversals are used to visit every edge and vertex systematically. Each vertex is marked using boolean flags when first visited and what hasn’t been completely explored. The data is stored as stack so it knows where to go back to when a node has been completely explored.

Question 2

What is breadth first search algorithms?

Answer 2

Instead of finding another node and exploring that one, the first node has to be fully explored before moving on to the next one. You check the connections to the first node and store them in a queue. Once you have fully explored that node, you check the first item in the queue and explore that node.
Used for shortest path for an unweighted graph
Uses a queue

Question 3

What is depth first search algorithms?

Answer 3

explores one subnode of the root, and keeps going through those subnodes until it needs to go back.
Used for navigating a maze
Uses a stack for navigating, as it needs to go back to the previous node once the last once has been completely explored