Think of a graph as a map of relationships. A connected component is one self-contained region of that map: every vertex in the region can reach every other by following paths, while no edge connects it to another region. section 13.6
Two clusters in a social graph
Imagine a graph of animal accounts and their follows. One cluster centers on the Tiger and another on the Lion, with no connection between them. Each cluster is a connected component. Adding the Chicken can connect previously separate relationships without necessarily making every vertex mutually reachable in the directed graph. section 13.6
Use these distinctions when reading or designing a graph:
- An undirected graph is connected when every pair of vertices has a path between them; it then has one connected component. section 13.6
- A disconnected graph can be decomposed into multiple connected components. section 13.16
- In directed graphs, distinguish weak connectivity from strong connectivity; strongly connected components require paths in both directions. section 13.6
- In a forest, each connected component is a tree. section 13.7
Inspect the graph figure to compare the separate regions and see why each region forms its own connected component. section 13.6
