algorithm - 如何理解这篇关于 DFS 的糟糕文章？

Question

作为母语不是英语的人(俄罗斯)，我在维基百科上阅读了这篇文章:http://en.wikibooks.org/wiki/Artificial_Intelligence/Search/Heuristic_search/Depth-first_search

我尝试遵循这个用硬核英语编写的伪代码示例，几乎没有任何解释或评论。

特别是，我不明白他们试图用这句话说什么:

DFS(u):

visit(u);
time = time + 1;
d[u] = time;
color[u] = grey;

for all nodes v adjacent to u do
   if color[v] == white then
      p[v] = u;
       DFS(u);


time = time + 1;
f[u] = time;
color[u] = black;

对与u相邻的所有节点v做

我这句话的问题是“相邻”部分。我的字典说这是“邻居”之类的意思。所以我要遍历u的超节点的子节点？请注意，u 是图中的一个节点。

或者他们是想说我必须遍历 u 的所有子节点？因为这会产生巨大的不同。

除了那些英语问题，他们还忘了提到 d 和 p 是什么意思，这让我把所有的头发都扯掉了(是的，甚至是我 mustache 上的那些)。

文章中的链接只是重复了这些不太清楚的神秘内容。也许有人能够以一种更具人类可读性、更多注释和有意义的变量的方式重写它？我没有找到任何真正好的解释，而不仅仅是为了炫耀与 DFS 相关的作者的主导智慧。

因此，如果有人可以以更好的方式即时重写它并具有更大的学习值(value)，这将节省我的时间，节省我的 mustache 。保存一切。谢谢。

Answer 1

意思是:“对于直接连接到u的所有节点v”。

http://en.wikipedia.org/wiki/Depth-first_search 中的伪代码就简单多了。希望这个更适合您。

如果我没记错的话，d、p 和f 来自 Cormen 的算法书。它们分别表示节点被发现的时刻、DFS 遍历树上的前一个节点和节点完成的时刻。其中一些对某些应用程序很有用(例如拓扑排序、查找组件和其他围绕 DFS 的算法)，但它们对 DFS 本​​身并不重要。