这种深度优先搜索变体是否有特定名称？

Question

我使用下面的算法以特定顺序遍历 (networkx) 图。它类似于经典的深度优先搜索，不同之处在于较深的节点在其父节点之前被检索。出于好奇：是否有任何特定名称来指代此行为？

>>> import networkx

>>> def traverse_graph_dfs_like(graph, source):
...     """Yield nodes from graph beginning with the lowest left"""

...     stack = []
...     stack.append(source)
...     child_generators = {source: graph.neighbors(source)}

...     while stack:
...         try:
...             first_child = next(child_generators[stack[-1]])
...         except StopIteration:
...             yield stack.pop()
...         else:
...             stack.append(first_child)
...             child_generators[first_child] =  graph.neighbors(first_child)

>>> g = networkx.DiGraph({0: [1, 2], 1: [3, 4], 2: [5, 6]})

>>> list(traverse_graph_dfs_like(g, 0))
[3, 4, 1, 5, 6, 2, 0]


>>> list(networkx.algorithms.dfs_tree(g, 0))
[0, 1, 3, 4, 2, 5, 6]

Answer 1

您想以深度优先搜索 post-order 访问节点。在此方法中，您通过递归调用 post-order 函数从左到右遍历子树。一旦你遍历了它们，你就访问了当前节点的数据部分。还有其他遍历树的方法（例如前序、中序、逆序，等等）。有关详细信息，您可以参考 this 维基百科页面。

NetworkX 确实提供了该算法的实现：networkx.algorithms.traversal.depth_first_search.dfs_postorder_nodes。具体来说，它是深度优先搜索预排序中的节点生成器。使用方法如下：

from networkx import DiGraph
from networkx.algorithms.traversal.depth_first_search import dfs_postorder_nodes

g = DiGraph({0: [1, 2], 1: [3, 4], 2: [5, 6]})
print(*dfs_postorder_nodes(g, source=0))

打印输出正是您要查找的内容：3 4 1 5 6 2 0。

这种深度优先搜索变体是否有特定名称？

Is there a specific name for this depth-first-search variant?

python

graph

depth-first-search

networkx

graph-algorithm