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

Question

我正在实现深度优先搜索算法。有两个要求：我必须使用堆栈（无递归），它还应该返回发现时间和完成时间。下面是我使用递归实现的代码：

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])，其中第一个数组表示发现时间，第二个数组表示完成时间（按索引）

基于这个想法，我使用堆栈实现了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()

• 在处理其子节点之前，您正在将节点的所有子节点推送到堆栈。这意味着实际上深度优先遍历将从最后一个访问到第一个，而递归实现则从第一个访问到最后一个

测井结束时间

现在进入你问题的核心。如果要注册访问的完成时间，需要在堆栈上留下节点的跟踪，并且只有在处理完节点的所有子节点后才将其从堆栈中删除；不早

实现这一点的一种方法是存储在堆栈上，该堆栈是节点访问的最后一个邻居。因此，您将存储（节点、邻居）元组。如果尚未从该节点访问下一个节点，则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])