22.2. Connected Components

Try these first

1. 1.

   What is a connected component in a graph?

   Hint

   Think about the paths between vertices.

2. 2.

   Which algorithm would you use to find connected components?

   Hint

   These are fundamental algorithms for graph traversal.

3. 3.

   What defines a connected component?

   • A single vertex
   • Maximal set of vertices with paths between them
   • Any collection of vertices

   Hint

   Think about the connections in a cluster of vertices.

4. 4.

   True or False: A tree graph is always a connected graph.

   • True
   • False

   Hint

   Recall the definition of a tree.

5. 5.

   Given a graph represented by an adjacency list, determine the connected components and count them.

   Hint

   Keep an array for visited nodes.

6. 6.

   Design a directed graph with vertices and edges that ensure it has at least one strongly connected component but also some non-strongly connected nodes.

   Hint

   Think about how cycles permit bidirectional reach.