如何在NetworkX有向图（DiGraph）中查找所有根节点？

Great question! Absolutely, splitting your disconnected directed graph into connected subgraphs (specifically weakly connected components for digraphs) and then finding root nodes per component is the perfect approach here. Let's walk through this with your example.

Step 1: Refine Your Graph Construction #

First, let's adjust your original code to avoid overwriting Python's built-in dict keyword:

import networkx as nx

# Your graph data
graph_data = {1: ['a1', 'a2', 'a3'], 2: ['a4', 'a5', 'a7']}
undirected_graph = nx.from_dict_of_lists(graph_data)
digraph = nx.DiGraph(undirected_graph)

This creates two separate weakly connected components: one with nodes 1, a1, a2, a3 and another with 2, a4, a5, a7.

Step 2: Split into Weakly Connected Components #

For directed graphs, we use weakly connected components (nodes connected when edge directions are ignored) to group disconnected subgraphs. NetworkX has a built-in function to handle this:

# Get all independent weakly connected components
components = nx.weakly_connected_components(digraph)

Step 3: Find Root Nodes per Component #

In your scenario, root nodes are nodes with in-degree 0 (no incoming edges) — these are the starting points of each component. We can loop through each component to filter these nodes:

root_nodes = []
for component in components:
    # Pick nodes in the component that have no incoming edges
    component_roots = [node for node in component if digraph.in_degree(node) == 0]
    root_nodes.extend(component_roots)

print(root_nodes)  # Output: [1, 2]

Alternative: Validate Roots via Reachability #

If you define a root as a node that can reach every other node in its component, we can confirm this using nx.descendants:

for component in nx.weakly_connected_components(digraph):
    for node in component:
        # Check if all other nodes in the component are reachable from this node
        if set(nx.descendants(digraph, node)) == component - {node}:
            print(f"Root for component {component}: {node}")

This will also output 1 and 2, confirming they're valid roots for their respective subgraphs.

Why This Approach Works #

Your graph is disconnected, so each weakly connected component acts as an independent subgraph. By isolating these components first, you avoid mixing nodes from separate groups and can accurately identify roots for each — exactly what you need to get your expected result.

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