dfs_labeled_edges

dfs_labeled_edges(G, source=None, depth_limit=None, *, sort_neighbors=None)

迭代深度优先搜索 (DFS) 中按类型标记的边。

参数:

GNetworkX 图

source节点, 可选

指定深度优先搜索的起始节点，并返回从 source 可达的分量中的边。

depth_limitint, 可选 (默认=len(G))

指定最大搜索深度。

sort_neighbors函数 (默认=None)

一个函数，它接受一个节点迭代器作为输入，并返回一个具有自定义顺序的相同节点的迭代器。例如，sorted 将按升序对节点进行排序。

返回:

edges: 生成器

一个生成器，生成形如 (u, v, d) 的三元组，其中 (u, v) 是在深度优先搜索中正在探索的边，d 是字符串 ‘forward’、‘nontree’、‘reverse’ 或 ‘reverse-depth_limit’ 之一。‘forward’ 边表示 u 已访问但 v 未访问。‘nontree’ 边表示 u 和 v 都已访问但该边不在 DFS 树中。‘reverse’ 边表示 u 和 v 都已访问且该边在 DFS 树中。当通过 ‘forward’ 边达到 depth_limit 时，会立即生成一条 ‘reverse’ 边，而不是探索子树。为了指示这种类型的 ‘reverse’ 边，生成的字符串是 ‘reverse-depth_limit’。

另请参阅

dfs_edges

dfs_preorder_nodes

dfs_postorder_nodes

注意

如果没有指定 source，则会任意选择一个 source 并重复搜索，直到图中的所有连通分量都被搜索。

此函数的实现改编自 David Eppstein 在 PADS 中的深度优先搜索函数，并根据维基百科文章“深度限制搜索”进行了修改，以允许设置深度限制。

示例

与例如 dfs_edges() 相比，这些标签更详细地揭示了深度优先搜索算法的完整过程。

>>> from pprint import pprint
>>>
>>> G = nx.DiGraph([(0, 1), (1, 2), (2, 1)])
>>> pprint(list(nx.dfs_labeled_edges(G, source=0)))
[(0, 0, 'forward'),
 (0, 1, 'forward'),
 (1, 2, 'forward'),
 (2, 1, 'nontree'),
 (1, 2, 'reverse'),
 (0, 1, 'reverse'),
 (0, 0, 'reverse')]