`conncomp`

Connected components of a graph or digraph.

Category: Mathematics > Graph and Network Algorithms

Syntax

bins = conncomp(G)

Labels each node with its component number.

[bins, binsizes] = conncomp(G)

Also returns the number of nodes in each component.

bins = conncomp(G, 'Type', 'strong')

For a digraph, uses strong connectivity instead of weak.

Description

In an undirected graph a component is a maximal set of nodes that can all reach each other. Isolated nodes form components of size one. To find the largest component, take [~, k] = max(binsizes) and select the nodes where bins == k.

In a digraph the weak version asks only whether the underlying undirected graph is connected, while the strong version asks for directed paths in both directions.

Input arguments

G: A graph or digraph.
'Type': 'weak' (default) ignores edge directions; 'strong' requires a directed path both ways.

Output arguments

bins: Row vector with one component label per node.
binsizes: Number of nodes in each component, indexed by label.

Example

Three pieces

G = graph([1 2 4 5 7], [2 3 5 6 8]);
[bins, sizes] = conncomp(G)
[sbins, ssizes] = conncomp(digraph([1 2 3 4], [2 3 1 3]), 'Type', 'strong')

Output

bins = 1×8

     1     1     1     2     2     2     3     3
sizes = 1×3

     3     3     2
sbins = 1×4

     2     2     2     1
ssizes = 1×2

     1     3

conncomp