python - 在 NetworkX 上使用广度优先搜索来查找前驱只为每个节点返回 1 个前驱

Question

我想使用 NetworkX 的广度优先搜索在图中找到所有节点的所有直接前任。下面是我的代码和图形图像：

import networkx as nx
import matplotlib.pyplot as plt
nodes = ['0','1','2','3','4','5']
G = nx.DiGraph(name='G')
G.add_nodes_from(nodes)
edges = [('0','1'),('2','1'),('5','4'),('1','3'),('3','4')]
G.add_edges_from(edges)

bfs = nx.bfs_predecessors(G, source='0')
bfs = dict(bfs)
nx.draw(G, font_weight='bold', with_labels=True)
plt.show()
plt.savefig('graph.png')
print(bfs)

上面的代码返回{'1': '0', '3': '1', '4': '3'}.
我期待节点“1”的前任是“0”和“2”，对于节点“4”，它们是“5”和“3”。为什么每个节点我只得到 1 个前任？

标签： pythongraphnetworkxbreadth-first-search

Answer 1

因为这是一个有向图，并且 BFS 尊重方向：它只探索输出弧。虽然有向图中有从节点 2 到节点 1 的传入弧，但从节点 0 开始的 BFS 无法计算出这一点，因为它只遵循传出弧，并且弧 1->2 不是从节点 1 传出的。

如果你从节点 2 启动 BFS 你会发现它会报告 2 作为 1 的前驱，但它不会报告 0 作为 1 的前驱。如果你从节点 4 启动 BFS 你会发现它不会报告任何前任。这是因为没有办法从节点 4出去，所以 BFS 会在节点 4 开始和结束。