all_simple_edge_paths

all_simple_edge_paths(G, source, target, cutoff=None)

为从源到目标的所有简单路径生成边列表。

简单路径是没有重复节点的路径。

参数

G网络X图表

source结点

路径的起始节点

target节点

结束路径的单个节点或可迭代节点

cutoff整数，可选

深度以停止搜索。仅返回长度<=截止的路径。

返回

路径生成器：生成器

生成简单路径列表的生成器。如果在给定的截止范围内源和目标之间没有路径，则生成器不会生成任何输出。对于多重图，边列表具有以下形式的元素 (u,v,k) 。哪里 k 对应于边关键点。

参见

all_shortest_paths, shortest_path, all_simple_paths

笔记

该算法使用改进的深度优先搜索来生成路径 [1]. 只有一条路径可以在 \(O(V+E)\) 但图中简单路径的数量可能非常大，例如 \(O(n!)\) 在完整的有序图中 \(n\) 。

工具书类

1

R.Sedgewick，“C中的算法，第5部分：图形算法”，Addison-Wesley Professional，第3版，2001年。

实例

打印图形的简单路径边：

>>> g = nx.Graph([(1, 2), (2, 4), (1, 3), (3, 4)])
>>> for path in sorted(nx.all_simple_edge_paths(g, 1, 4)):
...     print(path)
[(1, 2), (2, 4)]
[(1, 3), (3, 4)]

打印多重图的简单路径边。返回的边与它们的关联键一起出现：

>>> mg = nx.MultiGraph()
>>> mg.add_edge(1, 2, key="k0")
'k0'
>>> mg.add_edge(1, 2, key="k1")
'k1'
>>> mg.add_edge(2, 3, key="k0")
'k0'
>>> for path in sorted(nx.all_simple_edge_paths(mg, 1, 3)):
...     print(path)
[(1, 2, 'k0'), (2, 3, 'k0')]
[(1, 2, 'k1'), (2, 3, 'k0')]