26.2.3. Graph Traversal

Try these first

1. 1.

   What is the purpose of graph traversal?

   Hint

   Think about why we explore all nodes in a graph.

2. 2.

   Name the two main graph traversal methods.

   Hint

   They're often acronymed. Think about their first letters!

3. 3.

   What does BFS stand for?

   • Breadth-First Search
   • Binary First Search
   • Base First Search

   Hint

   Focus on the first letter of each word.

4. 4.

   True or False: DFS uses a queue to manage the vertices to explore next.

   • True
   • False

   Hint

   Recall how each method handles vertices.

5. 5.

   Design an algorithm to determine if a graph contains a cycle using DFS.

   Hint

   Think about the recursion stack.

6. 6.

   Implement BFS to find the shortest path between two nodes in an unweighted graph. Describe your approach.

   Hint

   Consider how you manage the queue and backtrack the path.