ConnectedComponents

ConnectedComponents[g]

gives the connected components of the graph g.

ConnectedComponents[g,{v1,v2,}]

gives the connected components that include at least one of the vertices v1, v2, .

ConnectedComponents[g,patt]

gives the connected components that include a vertex that matches the pattern patt.

ConnectedComponents[{vw,},]

uses rules vw to specify the graph g.

Details

  • ConnectedComponents returns a list of components {c1,c2,}, where each component ci is given as a list of vertices.
  • For an undirected graph, the vertices u and v are in the same component if there is a path from u to v.
  • For a directed graph, the vertices u and v are in the same component if there is a directed path from u to v and from v to u.
  • For directed graphs, strongly connected components are computed.
  • For undirected graphs, the components are ordered by their length, with the largest component first.
  • For directed graphs, the components {c1,c2,} are given in an order such that there are no edges from ci to ci+1, ci+2, etc.
  • ConnectedComponents works with undirected graphs, directed graphs, multigraphs, and mixed graphs.

Examples

open allclose all

Basic Examples  (1)

Give the connected components of a graph:

In[1]:=
Click for copyable input
In[2]:=
Click for copyable input
Out[2]=

Highlight connected components:

In[3]:=
Click for copyable input
Out[3]=

Scope  (8)

Applications  (4)

Properties & Relations  (4)

See Also

ConnectedGraphQ  ConnectedGraphComponents  WeaklyConnectedComponents  WeaklyConnectedGraphComponents  WeaklyConnectedGraphQ  FindVertexCut  MorphologicalComponents

Introduced in 2010
(8.0)
| Updated in 2015
(10.3)