修改後的深度優先搜索Python

Question

我正在尋找通過圖形來查找以特定方式連接的節點的DFS。

graphed = { 
    1: [25, 30], 2: [11], 3: [13], 4: [17], 5: [17], 
    6: [26], 7: [11, 12], 8: [10, 13], 9: [14, 26], 
    10: [8, 11, 15], 11: [2, 7, 10], 12: [7, 16, 17], 
    13: [3, 8, 14], 14: [9, 13, 20], 15: [10, 19], 
    16: [12, 18], 17: [4, 5, 12], 18: [16, 21, 22], 
    19: [15, 28, 29], 20: [14, 25], 21: [18, 23], 
    22: [18, 24], 23: [21, 27], 24: [22, 27], 25: [1, 20], 
    26: [6, 9], 27: [23, 24], 28: [19], 29: [19], 30: [1] 
} 

letters = { 
    'S': [1], 
    'C': [10, [11], [12], [13], [14], [15], [16], [17], 
       [18], [19], [20], [21], [22], [23], [24], 
       [25], [26], [27], [28], [29], [30] ], 
    'O': [2, [3], [4], [5], [6]], 
    'N': [7, [8], [9]]} 


some_string = 'CO' 

def dfs(graph, start, num, visited = None): 
    # depth first search for connected nodes 
    k = some_string[num] 
    y = some_string[(num+1)] 
    if visited is None: 
     visited = [] 

    if start in visited: 
     return 

    visited.append(start) 
    # if start corresponds to first letter of string, continue 
    if start in letters.get(k): 
     # find all nodes that it is connected too 
     for each in [x for x in graph[start] if x not in visited]: 
      # if any of the connected nodes correspond to 
      # the next letter of string, continue... 
      if [each] in letters.get(y): 
       dfs(graph, each, (num+1), visited) #recursion 

    return visited 

lst1 = [] 
for i in range(1,len(graphed)): 
    lst1.append(dfs(graphed, i, 0)) 
print(lst1) 

目前，DFS函數返回的所有內容都是原始起始值，對於範圍內的i。

[[1], [2], [3], [4], [5], [6], [7], [8], [9], [10], 
[11], [12], [13], [14], [15], [16], [17], [18], [19], [20], 
[21], [22], [23], [24], [25], [26], [27], [28], [29]] 

我想到這一點：

[[1], [2], [3], [4], [5], [6], [7], [8], [9], [10], 
[11, 2], [12], [13,3], [14], [15], [16], [17,4], [17,5], 
[18], [19], [20], [21], [22], [23], [24], [25], [26,6], 
[27], [28], [29]] 

爲了澄清：我希望程序運行DFS功能;如果起始值是'C'中的值，找到所有連接的節點並檢查它們是否在'O'中;如果是的話，與他們一起做dfs;如果沒有，則返回單個值。

希望這很清楚，我無法理解爲什麼它不起作用。任何幫助表示讚賞，謝謝。

Answer 1

這段代碼有幾個問題。我建議你重新開始並使用增量編程：寫幾行代碼，調試它們，直到它們以你想要的方式工作。你沒有得到你的評論似乎假設的一些功能。

1. 我不確定您訪問的節點列表是否按您的要求操作。每次您在主程序中返回到for循環時，都會重置該值。
2. 你的主程序不會碰到最後一個節點，30.
3. 我懷疑你的主要問題是你的節點符號。我不知道你打算如何使用列表，例如[7，[8]，[9]]，其中節點號碼處於不同的嵌套層次上，但您的邏輯似乎假定沒有嵌套。您找不到某些內容，例如，您在列表中搜索元素 [10，[11]，[12]，...] - 這是False。 [11]是後者列表中的一個元素，但不是。

看到這個可愛的debug博客尋求幫助。

我已經做了一些調試，包括將一些變量名改爲更有意義的東西。這是我目前所擁有的嚴格的低科技印刷報表。

graphed = { 
    1: [25, 30], 2: [11], 3: [13], 4: [17], 5: [17], 
    6: [26], 7: [11, 12], 8: [10, 13], 9: [14, 26], 
    10: [8, 11, 15], 11: [2, 7, 10], 12: [7, 16, 17], 
    13: [3, 8, 14], 14: [9, 13, 20], 15: [10, 19], 
    16: [12, 18], 17: [4, 5, 12], 18: [16, 21, 22], 
    19: [15, 28, 29], 20: [14, 25], 21: [18, 23], 
    22: [18, 24], 23: [21, 27], 24: [22, 27], 25: [1, 20], 
    26: [6, 9], 27: [23, 24], 28: [19], 29: [19], 30: [1] 
} 

letters = { 
    'S': [1], 
    'C': [10, [11], [12], [13], [14], [15], [16], [17], 
       [18], [19], [20], [21], [22], [23], [24], 
       [25], [26], [27], [28], [29], [30] ], 
    'O': [2, [3], [4], [5], [6]], 
    'N': [7, [8], [9]]} 


node_path = 'CO' 

def dfs(graph, start, num, visited = None): 
    print("ENTER dfs", start, num, visited) 
    # depth first search for connected nodes 
    start_ltr = node_path[num] 
    end_ltr = node_path[(num+1)] 
    if visited is None: 
     visited = [] 

    if start in visited: 
     return 

    visited.append(start) 
    # if start corresponds to first letter of string, continue 
    print(" search for start node", start, "in list", start_ltr, letters.get(start_ltr)) 
    if start in letters.get(start_ltr): 
     # find all nodes that it is connected too 
     for each in [x for x in graph[start] if x not in visited]: 
      print(" found", each, "in", graph[start]) 
      print(" search in list", end_ltr, letters.get(end_ltr)) 
      # if any of the connected nodes correspond to 
      # the next letter of string, continue... 
      if [each] in letters.get(end_ltr): 
       dfs(graph, each, (num+1), visited) #recursion 

    print("LEAVE dfs", visited) 
    return visited 

lst1 = [] 
for i in range(1,15): # I cut back the list for less output. 
    lst1.append(dfs(graphed, i, 0)) 
print(lst1) 

輸出：

$ python3 so.py 
ENTER dfs 1 0 None 
    search for start node 1 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] 
LEAVE dfs [1] 
ENTER dfs 2 0 None 
    search for start node 2 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] 
LEAVE dfs [2] 
ENTER dfs 3 0 None 
    search for start node 3 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] 
LEAVE dfs [3] 
ENTER dfs 4 0 None 
    search for start node 4 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] 
LEAVE dfs [4] 
ENTER dfs 5 0 None 
    search for start node 5 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] 
LEAVE dfs [5] 
ENTER dfs 6 0 None 
    search for start node 6 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] 
LEAVE dfs [6] 
ENTER dfs 7 0 None 
    search for start node 7 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] 
LEAVE dfs [7] 
ENTER dfs 8 0 None 
    search for start node 8 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] 
LEAVE dfs [8] 
ENTER dfs 9 0 None 
    search for start node 9 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] 
LEAVE dfs [9] 
ENTER dfs 10 0 None 
    search for start node 10 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] 
    found 8 in [8, 11, 15] 
    search in list O [2, [3], [4], [5], [6]] 
    found 11 in [8, 11, 15] 
    search in list O [2, [3], [4], [5], [6]] 
    found 15 in [8, 11, 15] 
    search in list O [2, [3], [4], [5], [6]] 
LEAVE dfs [10] 
ENTER dfs 11 0 None 
    search for start node 11 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] 
LEAVE dfs [11] 
ENTER dfs 12 0 None 
    search for start node 12 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] 
LEAVE dfs [12] 
ENTER dfs 13 0 None 
    search for start node 13 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] 
LEAVE dfs [13] 
ENTER dfs 14 0 None 
    search for start node 14 in list C [10, [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30]] 
LEAVE dfs [14] 
[[1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14]] 

這是否讓你感動？

Answer 2

您的letters字典格式錯誤。

'C': [10, [11], [12], [13], [14], [15], [16], [17], 
      [18], [19], [20], [21], [22], [23], [24], 
      [25], [26], [27], [28], [29], [30] ], 
'O': [2, [3], [4], [5], [6]], 
'N': [7, [8], [9]]} 

注意每個字母的第一個數字是如何直接在頂級名單，但其它項是一個子列表本身。因此，對於可能連接到O的每個C節點，if start in letters.get(k)將爲false。

>>> 10 in letters.get("C") 
True 
>>> 11 in letters.get("C") 
False 

所以我改變了字典這樣：

letters = { 
    'S': [1], 
    'C': [10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30], 
    'O': [2, 3, 4, 5, 6], 
    'N': [7, 8, 9]} 

你必須改變這一行相應：

if [each] in letters.get(y): 

要

if each in letters.get(y): 

此外，爲了獲得每個遞歸調用的結果實際上傳遞回來了，我不得不改變這一行：

dfs(graph, each, (num+1), visited) #recursion 

要

return dfs(graph, each, (num+1), visited) #recursion 

最後，在方法的頂部添加一個特殊的情況下，當所有的some_string已經發現：

def dfs(graph, start, num, visited = None): 
    # depth first search for connected nodes 
    if (num+1 == len(some_string)): 
     return visited + [start] 

此時，搜索成功，所以沒有更多的字母可供搜索！