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

Strongly Connected Components in Directed Graphs

Learn how connectivity differs in directed graphs and identify maximal strongly connected subgraphs.

Strongly Connected Components in Directed Graphs

You'll learn: How connectivity works differently in directed graphs and how to identify maximal strongly connected subgraphs.

Why Directed Graphs Are Different

In undirected graphs, connectivity is simple: either two vertices are connected or they're not. But in directed graphs, the arrows matter! You might be able to travel from vertex A to vertex B, but not back from B to A.

What Is Strong Connectivity?

A directed graph is strongly connected if every vertex can reach every other vertex following the directed edges. Think of it like a city where you can drive from any location to any other location following one-way streets.

A Strongly Connected Component (SCC) is a maximal subset of vertices where:

  1. Every vertex in the subset can reach every other vertex in that subset
  2. Adding any other vertex would break this property (it's maximal)

An Intuitive Example

Imagine a social network where "following" creates a directed edge. An SCC would be a group of users who all follow each other (mutual connections in all directions). You might have several such tight-knit groups, but they don't all connect to each other in both directions.

Key Properties

  • Every vertex belongs to exactly one SCC (they partition the graph)
  • An SCC with just one vertex means that vertex can't reach others or be reached in a cyclic way
  • If you "collapse" each SCC into a single node, the resulting graph is always acyclic (a DAG)

Key Takeaway: Strongly Connected Components identify maximal subgraphs in directed graphs where every vertex can reach every other vertex, revealing the underlying cyclic structure and interconnected clusters.