DFS实现O（| E |）时间复杂性解决方案

Question

我正在尝试实现DFS，但是，根据A StackOverFlow link about DFS，DFS只使用堆栈。在

这是我当前的实现：

def DFS_graph_recursive(graph, start, end, stack):
    #Stack to push the node when we are entering the node
    stack.append(start)
    while(end not in stack):
        for i in graph.edges[start]:
            #check if this is inside the stack, to make sure that it doesn't try to go back
            if (i not in stack):
                #Recursive Call
                DFS_graph_recursive(graph, i, end, stack)
        #Pop the stack when we are leaving this node, but need to make sure if end is inside
    if(end not in stack):
        stack.pop()

有几个问题，时间复杂性看起来不像O（| E |）。第一个while循环是O（| E |），但是，我需要检查我的下一个节点是否已经在堆栈中，以避免向后，如果这个堆栈很大，并且我假设i not in stack需要O（n）来计算，使得这个算法在复杂度上看起来像O（| E |^2）。在

if(end not in stack)使得算法在时间复杂度方面更差，因为对于每个边搜索，它都需要检查end是否在堆栈中，这意味着如果找到解决方案，我们不想弹出堆栈。这进一步增加了时间复杂性到O（| E |^2+| E |）。有没有办法只使用一个while循环来完成这个任务？在

在空间复杂性方面，最坏的情况应该是O（| V |）我们有一棵分枝因子为1的长树。在

如果O（| E |）解决方案是一种二叉树类型，有一条指向子节点的路径，我可以很容易地实现它。如果问题a是向前的，那么如果问题a是向前的，那么就让a来检查。。。等等

Answer 1

使用此算法，您实际上会多次访问同一个节点（另一个问题是i not in stack的复杂性）

您应该考虑保留一个visited列表/字典，以跟踪您访问过的节点。如果你已经访问了这个节点，那么你就不会把它推到栈中。代码应该是-

vis = {}
def DFS_graph(graph, start, end, stack):
    #Stack to push the node when we are entering the node
    stack.append(start)
    vis[start] = 1
    while len(stack):
        # got to an element
        found_element = stack[-1]
        if found_element == end:
            # you found the end, so break now
            break
        stack.pop()
        for i in graph.edges[start]:
            #check if this is inside the stack, to make sure that it doesn't try to go back
            if i not in vis:
                #Recursive Call
                stack.push(i)

这里我使用了一个字典，它执行if i not in vis的实际复杂度在最坏情况下应该是O（n），在平均情况下应该是O（1）。 如果将图节点表示为g[0], g[1], g[2] ....，那么可以使用列表将复杂度变成O（1）最坏情况。在