如何在DFS上寫下這篇寫得不好的文章？

正如有人爲母親語言（俄羅斯）我讀這篇文章在維基百科誰沒有英語：http://en.wikibooks.org/wiki/Artificial_Intelligence/Search/Heuristic_search/Depth-first_search 如何在DFS上寫下這篇寫得不好的文章？

，我試圖跟寫在鐵桿英語用更少的資源沒有解釋或評論這個僞代碼示例。

特別是，我不明白他們試圖用這句話說什麼：

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做

我這句話的問題是「相鄰「部分。我的字典說這意味着像「鄰居」。所以我必須遍歷u的超節點的子節點？請注意，u是圖中的一個節點。

還是他們試圖說我必須迭代你的所有子節點？因爲這會造成巨大的差異。

除了那些英語問題，他們忘了，更不用說什麼d和p的意思，這讓我瑞普我的頭髮都出來（是的，即使是那些從我的鬍子）。

這篇文章中的鏈接只是重複這個不太知名的神祕東西。也許有人能夠以一種更具人性化的方式重寫這些內容，並提供更多評論和有意義的變量？我沒有找到任何真正好的解釋，這不僅僅是爲了炫耀作家與DFS相關的主導智慧。

因此，如果有人能以更好的方式在飛行中重新寫下更具學習價值的東西，那麼可以節省我的一天，省去我的鬍子。保存一切。謝謝。

來源

2011-04-26 Proud Member

當語言障礙位於一側時，我會少一點責備。

無論如何，「相鄰」是指直接連接。在該圖中：

A E 
/\/
    B C 
     \ 
     D

A鄰近B和C，B鄰近A，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;}}}

來源

2011-04-26 12:02:30 Svante

太好了。正是我需要的。一個視覺例子！謝謝！ – 2011-04-26 17:11:04

這意味着：「對於所有直接連接到u的節點v」。

http://en.wikipedia.org/wiki/Depth-first_search中的僞碼要簡單得多。希望這個對你更好。

如果我沒有記錯的話，d,p和f來自Cormen關於算法的書。它們分別表示發現節點的時刻，DFS遍歷樹上的上一個節點以及節點完成的時刻。其中一些對於某些應用程序很有用（如拓撲排序，查找組件和DFS周圍的其他算法），但它們對於DFS本身並不重要。

來源

2011-04-26 09:59:43

你確定你並不意味着「所有節點v直接連接U」？ – 2011-04-26 10:00:33

@BugAlert謝謝！ – 2011-04-26 10:05:44

我發現更糟。但是我意識到它並沒有太大的幫助，因爲它們是通過遞歸來實現的。我的DFS已經工作了，但我無法跟蹤深度：http://stackoverflow.com/questions/5788299/how-to-track-the-depth-in-this-object-graph-depth-first-search-算法 – 2011-04-26 10:10:08

從similar question我的代碼也許對你有所幫助：

#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-26 14:42:58 RossFabricant

如何在DFS上寫下這篇寫得不好的文章？

回答

相關問題