python - DFS - 实现 O(|E|) 时间复杂度解决方案

Question

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

这是我当前的实现:

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 不在stack 需要 O(n) 来计算，使该算法的复杂度看起来像 O(|E|^2)。

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

就空间复杂度而言，我们有一个分支因子为 1 的长树应该是 O(|V|) 的最坏情况。

如果它是一个二叉树类型，我可以很容易地实现一个 O(|E|) 解决方案，它有一个向下到子节点的定向路径。问题是因为问题是一个无向图，假设有两个顶点，A 和 B。如果 A 连接到 B，那么 B 连接到 A。所以如果我不检查 if (i not in stack) 我会被困在从 A 到 B，B 到 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) 最坏情况。