22.2.1. Identifying Connected Components

Try these first

1. 1.

   What is a connected component?

   Hint

   Think of it as a group in a family tree.

2. 2.

   Name the two algorithms discussed for exploring graphs.

   Hint

   One goes level by level, the other dives deep.

3. 3.

   What is a connected component?

   • A set of isolated vertices
   • A subset of vertices where every vertex is reachable from every other vertex
   • Any connected subgraph

   Hint

   Think about how planets might be grouped based on their orbits.

4. 4.

   True or False: A connected graph has no disconnected components.

   • True
   • False

   Hint

   Consider the definition of connectivity.

5. 5.

   Given a complex undirected graph with isolated vertices and connected components, explain how you would identify and label each component.

   Hint

   Consider sorting your visit order by the vertex number for systematic labeling.

6. 6.

   Write a function to determine if a given undirected graph contains cycles using DFS. What parameters would you pass?

   Hint

   Focus on backtracking and how visited nodes are tracked.