Course contentsShow
← Computer Science
Lesson 664 of 2,87216. Graphs: Representation and Basic ConceptsFree lesson

Connected Graphs and Components

Define graph connectivity and identify connected components as maximal subgraphs where all vertices are reachable.

Connected Graphs and Components

What You'll Learn

You'll understand when a graph is "connected" and how to identify separate connected components within larger graphs.


What Does "Connected" Mean?

A graph is connected if you can reach any vertex from any other vertex by following edges. Think of it like islands connected by bridges: if you can walk from any island to any other island using the bridges (possibly going through multiple islands), then the whole system is connected.

In more formal terms: in a connected graph, there exists a path between every pair of vertices.

If a graph is not connected, it splits into separate pieces called connected components. Each component is a maximal connected subgraph—"maximal" meaning you can't add any more vertices to it while keeping it connected.


Identifying Connected Components

Imagine a social network graph where vertices are people and edges are friendships. If there are separate groups of friends with no connections between groups, each isolated group forms its own connected component.

  • Component 1: Alice ↔ Bob ↔ Carol
  • Component 2: Dave ↔ Eve
  • Component 3: Frank (alone, still a component of one vertex)

Each component is its own little connected universe. Within a component, everyone is reachable from everyone else. Between components? No paths exist.


Why Does This Matter?

Connected components help you:

  • Detect isolated clusters in networks
  • Find whether two vertices can communicate
  • Count the number of separate "islands" in a graph

Key Takeaway: A graph is connected if all vertices are mutually reachable; otherwise, it breaks into connected components—maximal subgraphs where internal vertices can all reach each other.