正确的DFS遍历

，因为它是图的DFS遍历，我们使用栈，所以我参观了一个，因为它在问题的定则我去了B，因为它是一个有向图，然后到C，因为C没有任何其他方向，所以我不得不回到我的堆栈，即B现在我去了D现在D要么导致C，要么我必须退回到我的堆栈所以我搬到了B（因为我已经访问过C）B再次疲惫，所以我回到了A，现在我的A把我引向F，它是可逆的G，H甚至没有链接，所以它是正确的方式忽视他们或我应该访问他们？什么应该是正确的DFS遍历答案？

来源

2017-07-22 Paul Stoner

@JonChesterfield伙计，我已经学尝试我无法真正理解的答案是否正确，如果错了，做这件事的正确方法是什么？在投票或甚至评论垃圾之前，请阅读问题两次。 –

DFS/BFS背后的概念是，您应该只在遍历不连接的节点时访问连接的节点，这样确实访问的节点是正确的，并且访问的顺序也是正确的，但您应该尝试使堆栈表示有点清晰，因为很难确定如何在映像中跟踪堆栈以适应您的尝试。

来源

2017-07-22 17:24:15

表示DFS遍历的最好方法是构建相应的生成树。

在你的问题图可以用邻接表示的图列出方式：

A: B, C, F 
B: C, D 
C: 
D: A, C 
E: C, G 
F: A, C 
G: E

一个DFS从一开始将只能访问A，B，C，d和F产生以下跨越树：

您可以添加到这个树中的未使用的边缘（那些被忽略，因为它们会导致媒体链接访问顶点），甚至给他们的分类（前部边缘，后边缘和交叉边缘。）但是，跨越TRE电子可能就足够了。

对于更一般的考虑：一个DFS是可以这样描述一个递归程序（可以使用堆栈来模拟）：

DFS(g, cur, mark): 
    mark[cur] = True 
    foreach s in successors of cur in g: 
    if not mark[s]: 
     DFS(g, s, mark)

但是你应该已经知道了......

编辑：这是蟒蛇一个简单的实现产生用于构建图中的点：

https://gist.github.com/slashvar/d4954d04352fc38356f774198e3aa86b

来源

2017-07-22 17:53:04

不会有F？ –

是的，我忘了A的继任者中的F ...我会尝试纠正我的回答 –

我认为它应该是A，B，C，D，F –

正确的DFS遍历

回答

相关问题