dfs_predecessors

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

返回从源节点开始的深度优先搜索中的前驱节点字典。

Parameters:

GNetworkX 图

source节点, 可选

指定深度优先搜索的起始节点。 注意，您将获得包含 source 的连通分量中所有节点的前驱节点。此输入仅指定 DFS 的起始位置。

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

指定最大搜索深度。

sort_neighbors函数 (默认=None)

一个接受节点迭代器的函数，并返回具有自定义顺序的相同节点的可迭代对象。 例如， sorted 将按递增顺序对节点进行排序。

Returns:

pred: dict

一个以节点为键、前驱节点为值的字典。

See also

dfs_preorder_nodes

dfs_postorder_nodes

dfs_labeled_edges

edge_dfs()

bfs_tree()

Notes

如果未指定源节点，则任意选择一个源节点并重复直到搜索完图中的所有连通分量。

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

Examples

>>> G = nx.path_graph(4)
>>> nx.dfs_predecessors(G, source=0)
{1: 0, 2: 1, 3: 2}
>>> nx.dfs_predecessors(G, source=0, depth_limit=2)
{1: 0, 2: 1}