使用堆栈但不使用递归的发现和完成时间的深度优先搜索

Question

我正在实施深度优先搜索算法。有两个要求：我必须使用 Stack（没有递归），并且它还应该 returns 发现时间和完成时间。这是我实现的使用递归的代码：

def dfs(graph, source):
    """Depth-first search algorithm

    This function computes depth-first search and prints the nodes as it travels

    Arguments:
        graph: List[List[int]], adjacency matrix of the graph
        source: int, the starting point
    Returns:
        None
    """
    visited = [False] * len(graph)
    time_start = [0] * len(graph) # Time when vertex is discovered
    time_finish = [0] * len(graph) # Time when vertex has finished discovering
    time = 0
    dfs_visit(graph, source, visited, time, time_start, time_finish)
    return time_start, time_finish

def dfs_visit(graph, source, visited, time, time_start, time_finish):
    time += 1
    time_start[source] = time
    visited[source] = True
    print(source, end = " ")
    for i, val in enumerate(graph[source]):
        if not visited[i] and val != 0:
            dfs_visit(graph, i, visited, time, time_start, time_finish)
    time += 1
    time_finish[source] = time

示例输入：

graph = [[0, 1, 1, 0], 
         [1, 0, 1, 0], 
         [1, 1, 0, 1], 
         [0, 0, 1, 1]]

预期输出：2 0 1 3 ([2, 3, 1, 2], [3, 4, 2, 3]) 其中第一个数组表示发现时间，第二个数组表示完成时间（按索引）。

基于这个想法，我使用 Stack 实现了 DFS：

def dfs_stack(graph, source):
    """Depth-first search algorithm using stack

    This function computes depth-first search and prints the nodes as it travels

    Arguments:
        graph: List[List[int]], adjacency matrix of the graph
        source: int, the starting point
    Returns:
        None
    """
    visited = [False] * len(graph)
    dfs_visit(graph, source, visited)
    return time_start, time_finish

def dfs_visit(graph, source, visited):
    stack = []
    stack.append(source)

    while (len(stack)):
        s = stack[-1]
        stack.pop()
        if not visited[s]:
            print(s, end = " ")
            visited[s] = True
        for idx, val in enumerate(graph[s]):
            if (not visited[idx]) and val != 0:
                stack.append(idx)

我试着用 time += 1; time_start[s] = ... 来计算这些时间，但它输出了奇怪的结果。我应该把计时器放在哪里？

Answer 1

首先对您的代码做几点说明：

关于递归求解

记录的时间有些混乱，因为您有重复的时间戳（例如 3）。这是因为您对 time 所做的增量不会反馈给调用者，调用者有自己的 time 变量实例。我会让 time 成为一个非局部变量，以便它不断递增。

所以我会把它改成：

def dfs(graph, source):
    def dfs_visit(graph, source, visited, time_start, time_finish):
        nonlocal time
        time += 1
        time_start[source] = time
        visited[source] = True
        print(source, end = " ")
        for i, val in enumerate(graph[source]):
            if not visited[i] and val != 0:
                dfs_visit(graph, i, visited, time_start, time_finish)
        time += 1
        time_finish[source] = time

    visited = [False] * len(graph)
    time_start = [0] * len(graph)
    time_finish = [0] * len(graph)
    time = 0
    dfs_visit(graph, source, visited, time_start, time_finish)
    return time_start, time_finish

现在 print(dfs(graph, 2)) 的输出将是：

2 0 1 3 ([2, 3, 1, 6], [5, 4, 8, 7])

这对我来说更有意义，但也许我误解了你打算用 time 做什么。

关于迭代求解

s = stack[-1]后面跟着stack.pop()其实可以写成s = stack.pop()
您正在将节点的所有 children 推入堆栈 before 处理它们的 children。这意味着实际上 depth-first 遍历将从 last-to-first 访问 children，而您的递归实现从 first-to-last.
访问它们

记录完成时间

现在进入你问题的核心。如果你想记录一次访问的结束时间，你需要在堆栈上留下节点的踪迹，并且只有在它的所有 children 都被处理后才将它从堆栈中删除；不早了。

实现这一点的一种方法是在堆栈中存储从节点访问的最后一个邻居。所以你会存储（节点，邻居）元组。如果尚未从该节点访问下一个节点，则 neighbor 的初始值可能为 -1。

这是如何工作的：

def dfs_stack(graph, source):
    visited = [False] * len(graph)
    time_start = [0] * len(graph)
    time_finish = [0] * len(graph)
    time = 0
    stack = [(source, -1)]
    while stack:
        node, neighbor = stack.pop()
        if neighbor == -1:
            if visited[node]:
                continue
            visited[node] = True
            print(node, end = " ")
            time += 1
            time_start[node] = time
        try:
            neighbor = graph[node].index(1, neighbor + 1)
            stack.append((node, neighbor))
            if not visited[neighbor]:
                stack.append((neighbor, -1))
        except ValueError:  # no more neighbors...
            time += 1
            time_finish[node] = time

如果我们用 print(dfs_stack(graph, 2)) 调用它，我们还会得到：

2 0 1 3 ([2, 3, 1, 6], [5, 4, 8, 7])

使用堆栈但不使用递归的发现和完成时间的深度优先搜索

Depth-first search with discovery and finish time using Stack but without recursion

python

algorithm

depth-first-search

关于递归求解

关于迭代求解

记录完成时间