find_cycle#

find_cycle(G, source=None, orientation=None)[source]#

通过深度优先遍历找到一个环。

环是一个边列表，指示环路路径。有向边的方向由 orientation 控制。

参数：
Ggraph

一个有向/无向图/多重图。

sourcenode, list of nodes

开始遍历的节点。如果为 None，则会任意选择一个源节点并重复，直到遍历图中每个节点的所有边。

orientationNone | ‘original’ | ‘reverse’ | ‘ignore’ (default: None)

对于有向图和有向多重图，边的遍历不必遵循边的原始方向。当设置为 'reverse' 时，每条边都沿反方向遍历。当设置为 'ignore' 时，每条边都被视为无向边。当设置为 'original' 时，每条边都被视为有向边。在这三种情况下，生成的边元组都会添加一个最后一个条目，表示该边遍历的方向。如果 orientation 为 None，生成的边不指示方向。方向被遵循，但不报告。

返回：
edgesdirected edges

一个有向边列表，指示环路路径。如果未找到环，则会引发异常。对于图，边形式为 (u, v)，其中 u 和 v 是由遍历确定的边的起点和终点。对于多重图，边形式为 (u, v, key)，其中 key 是边的键。当图为有向图时，u 和 v 总是按照实际有向边的顺序排列。如果 orientation 不为 None，则边元组将扩展，包括该边上的遍历方向（'forward' 或 'reverse'）。

引发：
NetworkXNoCycle

如果未找到环。

另请参见

simple_cycles

示例

在此示例中，我们构建一个 DAG，并在第一次调用中发现没有有向环，因此引发异常。在第二次调用中，我们忽略边的方向，发现存在无向环。请注意，第二次调用在有效遍历无向图时找到了有向环，因此，我们找到了一个“无向环”。这意味着这个 DAG 结构不形成有向树（也称为多树）。

>>> G = nx.DiGraph([(0, 1), (0, 2), (1, 2)])
>>> nx.find_cycle(G, orientation="original")
Traceback (most recent call last):
    ...
networkx.exception.NetworkXNoCycle: No cycle found.
>>> list(nx.find_cycle(G, orientation="ignore"))
[(0, 1, 'forward'), (1, 2, 'forward'), (0, 2, 'reverse')]
在此页上