dfs_labeled_edges#

dfs_labeled_edges(G, source=None, depth_limit=None, *, sort_neighbors=None)[source]#

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

Parameters:

GNetworkX 图
source节点, 可选: 指定深度优先搜索的起始节点，并返回从源可达的组件中的边。
depth_limit整数, 可选 (默认=len(G)): 指定最大搜索深度。
sort_neighbors函数 (默认=None): 一个接受节点迭代器的函数，并返回具有自定义顺序的相同节点的可迭代对象。例如， sorted 将按递增顺序对节点进行排序。

Returns:

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’。

See also

dfs_edges
dfs_preorder_nodes
dfs_postorder_nodes

Notes

如果没有指定源节点，则任意选择一个源节点并重复直到图中所有组件都被搜索。

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

Examples

标签揭示了深度优先搜索算法的完整过程，比例如 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')]