python之如何使用 DFS 了解节点执行(调用前、调用中、调用后)

假设我实现了一个像这样的迭代 DFS 的简单版本:

import sys 
import traceback 
 
 
def dfs(graph, start): 
    visited, stack = [], [start] 
    while stack: 
        node = stack.pop() 
 
        if node not in visited: 
            visited.append(node) 
            childs = reversed(graph.get(node, list())) 
            stack.extend([item for item in childs if item not in visited]) 
 
    return visited 
 
if __name__ == "__main__": 
    graphs = [ 
        { 
            'A': ['B', 'C'], 
            'B': ['D'] 
        } 
    ] 
 
    for i, g in enumerate(graphs): 
        try: 
            print "{0}Graph {1}{2}".format('-' * 40, i, '-' * 33) 
 
            for f in [dfs]: 
                print f.__name__, '-->', f(g, 'A') 
                print '-' * 80 
        except Exception as e: 
            print "Exception in user code: {0}".format(e) 
            print '-' * 60 
            traceback.print_exc(file=sys.stdout) 
            print '-' * 60 

上面代码片段的输出是这样的:

----------------------------------------Graph 0--------------------------------- 
dfs --> ['A', 'B', 'D', 'C'] 
-------------------------------------------------------------------------------- 

现在，我想弄清楚如何获得以下输出(而不是运行节点的方法，只打印就可以了):

A_start, B_start, D_start, D_end, B_end, A_middle, C_start, C_end, A_end 

*_middle 只会在子节点执行之间执行。例如，如果一个节点没有任何子节点，或者只有一个子节点，它永远不会被执行。这就是为什么在上面的示例中我想要的输出只有 A_middle(没有 B_middle、C_middle、D_middle)。

我该怎么做？

编辑:

试图找到我的问题的递归解决方案:

def dfs(graph, node): 
    if node not in graph: 
        return 
 
    print '{0}_start'.format(node) 
 
    for i, node in enumerate(graph[node]): 
        if i > 0: 
            print '{0}_middle'.format(node) 
 
        dfs(graph, node) 
 
    print '{0}_end'.format(node) 
 
if __name__ == "__main__": 
    graphs = [ 
        { 
            'A': ['B', 'C'], 
            'B': ['D'] 
        } 
    ] 
 
    for i, g in enumerate(graphs): 
        try: 
            print "{0}Graph {1}{2}".format('-' * 40, i, '-' * 33) 
 
            for f in [dfs]: 
                print f.__name__, '-->' 
                f(g, 'A') 
                print '-' * 80 
        except Exception as e: 
            print "Exception in user code: {0}".format(e) 
            print '-' * 60 
            traceback.print_exc(file=sys.stdout) 
            print '-' * 60 

会给我错误的输出:

----------------------------------------Graph 0--------------------------------- 
dfs --> 
A_start 
B_start 
D_end 
C_middle 
C_end 
-------------------------------------------------------------------------------- 

请您参考如下方法:

如其他答案所示，您当前递归代码的主要问题是基本情况:

if node not in graph: 
    return 

当节点没有子节点时，这会错误地跳过输出。去掉这些行，只需使用 enumerate(graph.get(start, [])) 而不是 中的 enumerate(graph[start]) for 循环，它应该按预期工作。

让您的迭代代码正常工作要复杂得多。尝试它的一种方法是将 2 元组压入堆栈。和以前一样，第一个值是一个节点，但第二个值要么是节点的前导(因此我们可以为父节点打印 middle 消息)，要么是 None表示我们需要打印节点的 end 标记。

但是，跟踪哪些节点已被访问变得有点复杂。我没有使用单个节点列表，而是使用从节点到整数的字典映射。一个不存在的值意味着该节点还没有被访问过。一个意味着该节点已被访问并且它的 start 消息已被打印。 2 表示至少访问了一个节点的子节点，每个子节点都应该代表父节点打印一条 middle 消息。 3 表示 end 消息已打印。

def dfs(graph, start): 
    visited = {} 
    stack = [(start, "XXX_THIS_NODE_DOES_NOT_EXIST_XXX")] 
    while stack: 
        node, parent = stack.pop() 
        if parent is None: 
            if visited[node] < 3: 
                print "{}_end".format(node) 
            visited[node] = 3 
 
        elif node not in visited: 
            if visited.get(parent) == 2: 
                print "{}_middle".format(parent) 
            elif visited.get(parent) == 1: 
                visited[parent] = 2 
 
            print "{}_start".format(node) 
            visited[node] = 1 
            stack.append((node, None)) 
            for child in reversed(graph.get(node, [])): 
                if child not in visited: 
                    stack.append((child, node)) 

因为我正在为 visited 使用字典，所以在最后返回它可能是不合适的，所以我删除了 return 语句。我认为如果你真的想恢复它，可以使用 collections.OrderedDict 而不是普通的 dict，并返回它的 keys() .