connected_components

connected_components(G)

Generate connected components.

The connected components of an undirected graph partition the graph into disjoint sets of nodes. Each of these sets induces a subgraph of graph G that is connected and not part of any larger connected subgraph.

A graph is connected (is_connected()) if, for every pair of distinct nodes, there is a path between them. If there is a pair of nodes for which such path does not exist, the graph is not connected (also referred to as “disconnected”).

A graph consisting of a single node and no edges is connected. Connectivity is undefined for the null graph (graph with no nodes).

Parameters:

GNetworkX graph

An undirected graph

Yields:

compset

A set of nodes in one connected component of the graph.

Raises:

NetworkXNotImplemented

If G is directed.

See also

number_connected_components

is_connected

number_weakly_connected_components

number_strongly_connected_components

Notes

This function is for undirected graphs only. For directed graphs, use strongly_connected_components() or weakly_connected_components().

The algorithm is based on a Breadth-First Search (BFS) traversal and its time complexity is \(O(n + m)\), where \(n\) is the number of nodes and \(m\) the number of edges in the graph.

Examples

Generate a sorted list of connected components, largest first.

>>> G = nx.path_graph(4)
>>> nx.add_path(G, [10, 11, 12])
>>> [len(c) for c in sorted(nx.connected_components(G), key=len, reverse=True)]
[4, 3]

If you only want the largest connected component, it’s more efficient to use max instead of sort.

>>> largest_cc = max(nx.connected_components(G), key=len)

To create the induced subgraph of each component use:

>>> S = [G.subgraph(c).copy() for c in nx.connected_components(G)]
----

Additional backends implement this function

cugraph : GPU-accelerated backend.