22.1. Applications of BFS and DFS

Try these first

1. 1.

   Define BFS.

   Hint

   Think about how layers are formed.

2. 2.

   What is a connected graph?

   Hint

   Consider paths between every node.

3. 3.

   What does BFS stand for?

   • A. Backward First Search
   • B. Best First Search
   • C. Breadth First Search

   Hint

   Remember how BFS spreads out from the starting vertex.

4. 4.

   True or False: A cycle can exist in an acyclic graph.

   • True
   • False

   Hint

   Think about the definition of acyclic.

5. 5.

   Design a graph where you can illustrate all three types of edges: tree edges, back edges, and forward edges. Illustrate how they indicate cyclical paths.

   Hint

   Think about paths that loop back during DFS.

6. 6.

   Using a graph with at least 4 disconnected components, explain how you would apply BFS to identify each component and the importance of articulation points.

   Hint

   Remember to keep track of visited nodes while marking components.