1

作为一个母语不是英语的人（俄罗斯），我在维基百科上阅读了这篇文章：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;

对于与你相邻的所有节点 v

我对这句话的问题是“相邻”部分。我的字典说这意味着“邻居”。所以我必须遍历你的超级节点的子节点？注意 u 是图中的一个节点。

或者他们是想说我必须遍历你的所有子节点？因为这将产生巨大的影响。

除了那些英语问题，他们忘了提d和p的意思，这让我把我所有的头发都扯掉了（是的，即使是我胡子上的那些）。

文章中的链接只是重复了这个没什么意义的神秘东西。也许有人能够以一种更易于阅读的方式重新编写它，有更多的评论和有意义的变量？我没有找到任何真正好的解释，这不仅仅是为了炫耀与 DFS 相关的作者的主导智慧。

因此，如果有人可以以更好的方式即时重写它，并具有更大的学习价值，这将节省我的一天，节省我的胡子。保存一切。谢谢你。

4

3 回答 3

2

这意味着：“对于所有直接连接到 u 的节点 v”。

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

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

于 2011-04-26T09:59:43.060 回答
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)
于 2011-04-26T14:42:58.257 回答
1

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

无论如何，“相邻”意味着直接连接。在此图中：

    A   E
   / \ /
  B   C
       \
        D

A与 相邻 ,B与相邻,与C,相邻,与相邻,与相邻.BACAEDDCEC

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

{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;}}}
于 2011-04-26T12:02:30.177 回答