从 BFS 获取 DFS？

Question

是否可以让 DFS 进行 BFS 搜索？如果我只是使用一个堆栈然后将它们弹出，它不会以 DFS 顺序出现吗？

我正在尝试进行 DFS 搜索，但我只有一个带有出边的邻接表，所以我不知道如何获得每个顶点的入度。

0: 2,4 1: none 2: 1,3 3: none 4: none

所以 0 有到 2 和 4 的出边。

我有点迷茫，我想如果我使用堆栈进行 BFS 搜索，我会得到 DFS，然后是拓扑顺序。

Answer 1

迭代完成时，DFS 和 BFS 之间的唯一区别是用于存储将在未来迭代中处理的顶点的数据结构。

使用队列可以获得 BFS，使用堆栈可以获得 DFS。

def bfs(g, start):
   discovered = [False] * (len(g) + 1)
   processed = [False] * (len(g) + 1)
   parents = [-1] * (len(g) + 1)
   discovered[start] = True
   q = deque()   #Different line
   q.append(start)
   while len(q) > 0:
    v = q.popleft() #Different line
    print "Visited:" + str(v)
    # process_ve(v)
    nbors = g[v]
    for n in nbors:
        if not p[n]:
            # process_edge((v,n))
            print ((v, n))
        if not discovered[n]:
            discovered[n] = True
            parents[n] = v
            q.append(n)
    # process_vl(v)
    processed[v] = True
    return parents

和 DFS：

def dfs(g, start):
   discovered = [False] * (len(g) + 1)
   processed = [False] * (len(g) + 1)
   parents = [-1] * (len(g) + 1)
   discovered[start] = True
   q = list()  #Different line
   q.append(start)
   while len(q) > 0:
    v = q.pop()  #Different line
    print "Visited:" + str(v)
    # process_ve(v)
    nbors = g[v]
    for n in nbors:
        if not processed[n]:
            # process_edge((v,n))
            print ((v, n))
        if not discovered[n]:
            d[n] = True
            pts[n] = v
            q.append(n)
    # process_vl(v)
    processed[v] = True
    return parents

上面 Python 中的示例应该清楚地说明了这一点。它们之间的唯一区别是我们在一个中使用 deque（Python 的队列版本），在一个中使用 list（Python 的堆栈版本）另一个。

示例遵循 Steve Skiena 在 The Algorithm Design Manual 中解释的算法。

Answer 2

如果你采用经典的 BFS 算法并将 FIFO 队列替换为 LIFO 堆栈，你确实会得到 DFS 顶点发现顺序 - 所谓的 DFS pre -排序。 IE。您的算法第一次访问图顶点的顺序将与 DFS 中的顺序完全相同。

但是，这不会给您 DFS 内存使用量，也不会给您 post-ordering 顶点 - 经典 DFS 算法的其他极其重要的属性（ Why is depth-first search claimed to be space efficient?)

换句话说，把BFS队列换成栈就可以把BFS变成DFS的说法是完全错误的。这些规范形式的算法具有完全不同的内部结构。通过这样的替换你会得到一个伪DFS算法，会成功模拟DFS预排序，但不会为你提供DFS post-排序。

所以这是一个问题，你想用它做什么。您需要 DFS post-ordering?

而且看起来你确实这样做了。经典的toposort算法具体是基于使用DFS生成的顶点post-ordering。 toposort 顺序是经典 DFS 算法对每个顶点进行 最后一次访问 的顺序。这立即意味着您的伪 DFS 将无法用于该目的。

可能有一些方法可以 "whip it into submission" 并以某种方式通过在这里和那里添加一堆拐杖来使其工作，但这根本不值得。就拿经典的正版DFS来用吧。它将以更简单、优雅和高效的方式完成。

从 BFS 获取 DFS？

Getting a DFS from a BFS?

algorithm

search

graph-algorithm

data-structures