number_connected_components

number_connected_components(G)

Returns the number of 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.

Returns:

ninteger

Number of connected components

Raises:

NetworkXNotImplemented

If G is directed.

See also

connected_components

is_connected

number_weakly_connected_components

number_strongly_connected_components

Notes

This function is for undirected graphs only. For directed graphs, use number_strongly_connected_components() or number_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

>>> G = nx.Graph([(0, 1), (1, 2), (5, 6), (3, 4)])
>>> nx.number_connected_components(G)
3
----

Additional backends implement this function

cugraph : GPU-accelerated backend.

parallelA networkx backend that uses joblib to run graph algorithms in parallel. Find the nx-parallel’s configuration guide here

The parallel computation is implemented by dividing the list of connected components into chunks and then finding the length of each chunk in parallel and then adding all the lengths at the end.

Additional parameters:

get_chunksstr, function (default = “chunks”)

A function that takes in a list of connected components as input and returns an iterable component_chunks. The default chunking is done by slicing the list of connected components into n_jobs number of chunks.

[Source]