如何在递归中确定最后一个堆栈space

Question

我正在通过递归实现众所周知的深度优先搜索。我想知道是否有办法知道最后一个堆栈中的代码 space。我需要的原因是我不想在输出末尾放置 -> 字符。如果可能的话，在最后一步 '\n'。

def DFS(self, vertex=None, visited=None):
    if vertex is None:
        vertex = self.root
    if visited is None:
        visited = []
        print(f"{vertex} -> ", end='')

    visited.append(vertex)
    for neighbor in self.getNeighbors(vertex):
        if neighbor not in visited:
            visited.append(neighbor)
            print(f"{neighbor} -> ", end='')
            self.DFS(neighbor, visited)

例如，它产生 1 -> 2 -> 4 -> 5 ->

有没有办法在同一个方法中做？此外，我可以编写一个辅助函数来删除最后一个 -> 字符。

@编辑：我根据@Carcigenicate 的评论所做的如下

return visited # last line in DFS method
-- in main --
dfs = graph.DFS()
path = " -> ".join(str(vertex) for vertex in dfs)
print(path)

Answer 1

与其尝试对最后一个顶点进行特殊处理，不如对第一个顶点进行特殊处理。也就是说，不要试图弄清楚什么时候不附加“->”，只是不要对第一个顶点这样做：

def DFS(self, vertex=None, visited=None):
    if vertex is None:
        vertex = self.root
    else:
        # Not the first vertex, so need to add the separator.
        print(f" ->", end='')

    if visited is None:
        visited = []

    print(f"{vertex}", end='')

    visited.append(vertex)
    for neighbor in self.getNeighbors(vertex):
        if neighbor not in visited:
            # no need to append here, because it will be done in the recursive call.
            # and the vertex will be printed in the recursive call, too.
            # visited.append(neighbor)
            # print(f"{neighbor} -> ", end='')
            self.DFS(neighbor, visited)

这假定您的初始呼叫将始终是 DFS(root, None, visited)。我认为这是一个合理的假设。

转念一想，也许使用 visited 参数作为条件更好：

    if vertex is None:
        vertex = self.root

    if visited is None:
        visited = []
    else:
        # Not the first vertex, so need to add the separator.
        print(f" ->", end='')

    print(f"{vertex}", end='')

重点是第一项比最后一项更容易特殊化。

如何在递归中确定最后一个堆栈space

How to determine last stack space in recursion

python

algorithm

recursion

graph

graph-traversal