ConnectedComponents

The strongly-connected components of a Graph, respecting edge direction.

✓ checked against that system · ! checked, with disagreements (hover a chip)Wolfram LanguageConnectedComponents!

ConnectedComponents(g)each component's vertices, largest component first.

Typed signatures

Type	Package	Applies
`(value) -> list<list<any>>`	`combinatorics`	always

Domain: Collections

Details

Respects edge direction (kernel-verified): a directed edge only counts toward mutual reachability one way, so Graph({1,2,3}, {1->2, 2->1, 2->3}) gives two components, {1, 2} (a 2-cycle) and {3} (reachable but never reached from), even though the graph is a single WEAKLY connected piece. An undirected edge counts both ways, so a purely undirected graph's components are its ordinary (weakly) connected pieces.
IsConnectedGraph and IsTreeGraph test weak connectivity instead — direction ignored — since a directed tree (edges pointing away from a root) is weakly connected but never strongly connected. The two heads deliberately disagree on a directed graph.
Vertex order WITHIN a component is this implementation's own traversal order, not a claim about matching Wolfram's.

Examples

Basic #

1 and 2 reach each other; 3 is downstream only

\mathrm{ConnectedComponents}(\mathrm{Graph}(\bigl\lbrack1, 2, 3\bigr\rbrack, \bigl\lbrack\mathrm{DirectedEdge}(1, 2), \mathrm{DirectedEdge}(2, 1), \mathrm{DirectedEdge}(2, 3)\bigr\rbrack))

Out

\bigl\lbrack\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack3\bigr\rbrack\bigr\rbrack

Applications #

With $g$ an undefined symbol the components list is empty

\mathrm{Length}(\mathrm{First}(\mathrm{ConnectedComponents}(g)))

Out

0

Count of components minus one is $0$ here

\mathrm{Length}(\mathrm{ConnectedComponents}(g))-1

Out

0

Properties #

A connected graph has exactly one component

\mathrm{Length}(\mathrm{ConnectedComponents}(g))

Out

1

About

Examples	4
Checked against	Wolfram Language 3 agree1 differ
Crosswalk	Wolfram Language