如何理解 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 的意思，这让我把我所有的头发都扯掉了（是的，甚至是我胡子上的头发）。

文章中的链接只是重复了这个没什么可说的神秘内容。也许有人能够以更易于理解的方式实际重写此代码，并添加更多注释和有意义的变量？我没有找到任何真正好的解释，而不仅仅是为了炫耀作者与 DFS 相关的主导智慧。

因此，如果有人能以一种更好的方式即时重写它，并具有更大的学习价值，这将拯救我的日子，拯救我的胡子。保存一切。谢谢。

Answer 1

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

http://en.wikipedia.org/wiki/Depth-first_search 中的伪代码很多更简单。希望这个对你来说效果更好。

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

Answer 2

我来自类似问题的代码可能对您有帮助：

#A tree is a tuple of an int and a tree. 
t = (1, (2,(4, (6), (7, (9)) )), (3, (5, (8)) ))

def dfs(t):
    if type(t) is int:
        print t
        return 
    print t[0]
    dfs(t[1])
    if len(t) > 2: dfs(t[2]) 

dfs(t)

Answer 3

当你遇到语言障碍时，我会少一点责备。
边。

总之，“相邻”就是直接相连的意思。在此图中：

    A   E
   / \ /
  B   C
       \
        D

A 与 B 和 C 相邻，B 与 A 相邻code>、C 相邻
对于 A、E 和 D，D 与 C 相邻，并且E 与C 相邻。

这是相同的代码，但更详细一些：

{with the following global variable:
    time, which is a single integer, and initially 0;}

{and a node being a structure of:
    value;
    adjacent-nodes;
    colour, initially white;
    previous-node;
    discovery-time;
    finishing-time;}

{depth-first-search of node u is:
    visit the value of u;
    increase time by 1;
    set the discovery-time of u to time;
    set the colour of u to grey;

    {for all nodes v in the adjacent-nodes of u:
        {if the colour of v is white then:
            set the previous-node of v to u;
            depth-first-search of v;}}

    increase time by 1;
    set the finishing-time of u to time;
    set the colour of u to black;}

此代码中有几件事纯粹是说明性的
目的。中心主题是这样的：

{with a node being a structure of:
    value;
    adjacent-nodes;
    colour, initially white;}

{depth-first-search of node u is:
    visit the value of u;
    set the colour of u to black;

    {for all nodes v in the adjacent-nodes of u:
        {if the colour of v is white then:
            depth-first-search of v;}}}