THIS IS DOCUMENTATION FOR AN OBSOLETE PRODUCT.
SEE THE DOCUMENTATION CENTER FOR THE LATEST INFORMATION.

DOCUMENTATION CENTER SEARCH

BUILT-IN MATHEMATICA SYMBOL

ConnectedComponents

ConnectedComponents[g]
gives the connected components of the graph g.

gives the connected components that include at least one of the vertices

, ....

ConnectedComponents returns a list of components where each component 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. Weakly connected components can be computed through ConnectedComponents[UndirectedGraph[g]].

Give the connected components for a complete graph:

For a disconnected graph:

Give the connected components for a complete graph:

Out[1]=

Out[2]=

For a disconnected graph:

Out[1]=

Out[2]=

ConnectedComponents works with undirected graphs:

Directed graphs:

The strongly connected components are computed:

Use UndirectedGraph to get the weakly connected components:

Works with large graphs:

An undirected graph which is connected has exactly one connected component:

Every graph with

vertices and

edges has at least

components:

An undirected tree has only one connected component:

A directed tree has as many connected components as it has vertices:

An undirected path has only one connected component: