這是使用Python實現的DFS搜索我從網上採取

Question

graph={ 
     'A':set(['B','C']), 
     'B':set(['A','D','E']), 
     'C':set(['A','F']), 
     'D':set(['B']), 
     'E':set(['B','F']), 
     'F':set(['C','E'])} 

def dfs(graph, start): 
     visited, stack = set(), [start] 

     while stack: 
      vertex = stack.pop() 
      if vertex not in visited: 
         visited.add(vertex) 
         stack.extend(graph[vertex] - visited) 

    return visited 

dfs(graph, 'A') 

任何人都可以解釋爲什麼我們使用這些

1. visited,stack = set(), [start]
2. graph[vertex] - visited
3. stack.extend(graph[vertex] - visited)

Answer 1

的你問的第一行是初始化visited和stack變量。你可以把它寫在兩行，如果你想：

visited = set() 
stack = [] 

我喜歡在不同的行會好一點初始化的東西，但它主要是風格問題。我知道很多其他Python程序員喜歡將它們的初始化結合起來，可能是因爲它允許他們使用較少的行（如果您的功能增長的時間比一次在一個屏幕上看到的要長），那麼這些行就會變得特別有價值。兩個版本都正常工作。你問的第二件事是減法表達式set。在這種情況下，它將從graph[vertex]減去visited，這是一個set，其中包含vertex的鄰居。差異化操作查找graph[vertex]中不在visited中的所有值，並返回包含它們的set。

你問的第三件事是撥打list.extend。這將set減法中的每個值附加到stack（這是一個列表）。您可以編寫一個循環，並重復呼叫append而不是呼叫extend，但在這種情況下確實沒有理由這樣做。 set s是可迭代的，但值得注意的是，它們以任意順序產生它們的項目，所以當它們在列表中時，不能提前確定項目將以何種順序結束。幸運的是，這個算法的順序並不重要。

還值得注意的是，該功能仍然可以在沒有設置減法的情況下工作。這隻會有點低效，因爲更多的值將被添加到stack，只有稍後彈出堆棧時纔會跳過（因爲它們已經是visited）。