请求提供NetworkX库中connected_components(G)函数的Python实现源码

Alright, let's get right to the actual Python source code for NetworkX's connected_components function, taken directly from the library's codebase (based on version 3.1, a widely used stable release):

First, the main connected_components function itself:

def connected_components(G):
    """Generate connected components of an undirected graph.

    Parameters
    ----------
    G : NetworkX Graph
        An undirected graph.

    Returns
    -------
    generator of sets
        A generator of sets of nodes, one for each connected component of G.

    Examples
    --------
    >>> G = nx.path_graph(4)
    >>> list(nx.connected_components(G))
    [{0, 1, 2, 3}]
    >>> G.add_edge(4, 5)
    >>> list(nx.connected_components(G))
    [{0, 1, 2, 3}, {4, 5}]

    Notes
    -----
    For undirected graphs only.
    """
    if G.is_directed():
        raise nx.NetworkXError(
            "connected_components() is not defined for directed graphs.")
    return _connected_components_iter(G)

It relies on an internal helper function _connected_components_iter to handle the iteration over components:

def _connected_components_iter(G):
    seen = set()
    for v in G:
        if v not in seen:
            component = set(_plain_bfs(G, v))
            yield component
            seen.update(component)

And the core traversal logic is handled by the _plain_bfs function, which performs a fast breadth-first search to collect all nodes in a component:

def _plain_bfs(G, source):
    """A fast BFS node generator"""
    seen = set()
    nextlevel = {source}
    while nextlevel:
        thislevel = nextlevel
        nextlevel = set()
        for v in thislevel:
            if v not in seen:
                seen.add(v)
                yield v
                nextlevel.update(G[v])

Quick note: This implementation uses BFS to traverse each connected component, marking nodes as seen to avoid reprocessing. The function explicitly checks if the input graph is directed and throws an error, since connected components are a concept for undirected graphs (for directed graphs, you'd use strongly_connected_components or weakly_connected_components instead).

内容的提问来源于stack exchange，提问作者Zero_Cool