如何高效获取NetworkX有向图的所有直接与间接出后继边？

我希望将以下列表构建为NetworkX有向图：

testlist = [(0, 1), (0, 5), (1, 2), (2, 9), (5, 3),(6, 4), (4, 9)]

并获取所有直接与间接出后继对应的边，预期输出如下：

# all_edges = [(0, 1), (0, 5), 
#              (1, 2), (0, 2),
#              (1, 9), (2, 9),
#              (5, 3), (0, 3), 
#              (6, 4), (4, 9), 
#              (6, 9)]

我查阅了NetworkX教程但未找到对应方法，猜测可借助有向图的successors()方法实现，遂尝试以下代码：

list1 = [sum(nx.dfs_successors(L, i).values(), []) for i in L.nodes()]   

list2 = [i for i in L.nodes()]

再通过笛卡尔积处理：

import itertools
list3 = [j for i in range(len(list1)) for j in itertools.product([list2[i]],list1[i]) ]

最终输出结果为：

[(0, 1),
 (0, 5),
 (0, 2),
 (0, 9),
 (0, 3),
 (1, 2),
 (1, 9),
 (5, 3),
 (2, 9),
 (6, 4),
 (6, 9),
 (4, 9)]

我已实现需求，但想了解是否有更高效、更简洁的实现方式？

方法1：用nx.transitive_closure直接生成传递闭包图 #

NetworkX内置了传递闭包计算工具，nx.transitive_closure能直接生成包含所有直接、间接边的有向图，提取边即可完成需求，代码简洁且效率高：

import networkx as nx

testlist = [(0, 1), (0, 5), (1, 2), (2, 9), (5, 3),(6, 4), (4, 9)]
G = nx.DiGraph(testlist)
# 生成包含所有直接/间接边的闭包图
closure_graph = nx.transitive_closure(G)
# 获取所有边
all_edges = list(closure_graph.edges())

输出结果和你实现的完全一致，内部优化过的算法在节点数量较多时，比手动DFS的效率提升明显。

方法2：用nx.descendants简化遍历逻辑 #

如果不想直接生成闭包图，也可以用nx.descendants直接获取每个节点的所有后继（含直接、间接），再生成对应边，写法更简洁：

import networkx as nx

testlist = [(0, 1), (0, 5), (1, 2), (2, 9), (5, 3),(6, 4), (4, 9)]
G = nx.DiGraph(testlist)

all_edges = []
for node in G.nodes():
    # 获取当前节点的所有后继节点
    descendants = nx.descendants(G, node)
    # 批量添加边
    all_edges.extend((node, desc) for desc in descendants)

也可以用列表推导式压缩成一行：

all_edges = [(node, desc) for node in G.nodes() for desc in nx.descendants(G, node)]

这种写法逻辑清晰，代码量少，nx.descendants的实现也经过优化，比手动处理DFS后继的开销更小。

对比原实现 #

你的方法逻辑可行，但sum(nx.dfs_successors(...).values(), [])会产生额外的列表拼接开销，代码可读性也不如上面两种方法。如果追求简洁性，优先选transitive_closure；如果需要在生成边前做额外处理，nx.descendants更灵活。

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