这是使用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）。