Skip to main content
 首页 » 编程设计

python之找到连接到 n 的所有节点

2024年10月24日20zdz8207

我需要找到有向图中每对节点之间的所有最短路径。我正在做的是:

for i in A.nodes() 
    for y in A.nodes() 
        paths = nx.all_shortest_paths(G,i,y) 

但我猜这很慢,因为在图中有很多节点无论如何都与 i 没有连接。 有没有办法优化这个过程?我已经在注意不可能连接到其他节点的节点不会在 A 中结束。

请您参考如下方法:

内置命令: single_source_shortest_path_length(G, source) 为您提供源和每个可达节点之间的最短路径。

import networkx as nx 
G=nx.DiGraph() 
G.add_edges_from([(1,2), (2,3), (3,4), (1,5), (2,5), (6,7)]) #6,7 not reachable from 1 
nx.single_source_shortest_path(G,1) 
>{1: [1], 2: [1, 2], 3: [1, 2, 3], 4: [1, 2, 3, 4], 5: [1, 5]} 

问题标题表明您只想知道可达节点而不是路径。在这种情况下,请使用深度优先或广度优先搜索。文档是 here .例如:dfs_postorder_nodes(G, source=None) 为可从源到达的节点提供迭代器。它们出现的特定顺序是深度优先搜索后序。

for reachable_node in nx.dfs_postorder_nodes(G,source=1): 
   print reachable_node 
>4 
>3 
>5 
>2 
>1