all_simple_edge_paths

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

生成图中从源节点到目标节点的所有简单路径的边列表。

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

参数：

GNetworkX 图

source节点

路径的起始节点

target节点

路径的结束节点（单个节点或可迭代的节点集合）

cutoff整数，可选

搜索的深度限制。仅返回长度小于等于 cutoff 的路径。

返回：

path_generator: 生成器

一个生成器，生成简单路径的列表。如果在给定的 cutoff 范围内源节点和目标节点之间没有路径，则生成器不产生输出。对于多重图，边列表的元素形式为 (u,v,k)。其中 k 对应于边的键。

另请参阅

all_shortest_paths, shortest_path, all_simple_paths

说明

此算法使用改进的深度优先搜索来生成路径 [1]。可以在 \(O(V+E)\) 时间内找到一条路径，但图中的简单路径数量可能非常大，例如在 n 阶完全图中可达 \(O(n!)\)。

参考文献

[1]

R. Sedgewick, “Algorithms in C, Part 5: Graph Algorithms”, Addison Wesley Professional, 3rd ed., 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')]

当 source 是目标节点之一时，从 source 开始和结束且不遍历任何边的空路径被视为有效的简单边路径并包含在结果中

>>> G = nx.Graph()
>>> G.add_node(0)
>>> paths = list(nx.all_simple_edge_paths(G, 0, 0))
>>> for path in paths:
...     print(path)
[]
>>> len(paths)
1