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

Question

我正在尝试实现 DFS，但是，根据 A Whosebug link about 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 not in stack 需要O(n) 来计算，使该算法的复杂度看起来像 O(|E|^2)。

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

就space复杂度而言，最坏情况下我们有一个分支因子为1的长树。

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

Answer 1

使用这个算法，你实际上最终会多次到达同一个节点（i not in stack 的复杂性是一个额外的问题）

您应该考虑保留一个 visited list/dictionary，以跟踪您访问过的节点。如果您已经访问过该节点，那么您就不会将其压入堆栈。代码就像 -

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) 最坏情况。

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

DFS - Implementing a O(|E|) timing complexity solution

python

algorithm

graph-algorithm