22.6. Applications of BFS and DFS

Try these first

1. 1.

   Define a connected graph.

   Hint

   Think about how vertices are grouped.

2. 2.

   What is a cycle in a graph?

   Hint

   Consider paths that revisit nodes.

3. 3.

   What is the main purpose of BFS?

   • To explore all vertices and edges in a graph
   • To sort the vertices of a graph
   • To find the shortest path between two vertices

   Hint

   Think about its primary function in graph exploration.

4. 4.

   True or False: A cycle can exist if there are no non-tree edges during BFS.

   • True
   • False

   Hint

   Consider the definition of cycles.

5. 5.

   Given a disconnected graph, devise an algorithm using BFS to identify all connected components. How would you ensure each component is labeled correctly?

   Hint

   Consider using an additional array to track the component labels.

6. 6.

   How could you efficiently find articulation points in a graph using DFS? Provide pseudo-code for your approach.

   Hint

   Reflect on how vertices relate to their children in a DFS tree.