在python深度优先搜索（DFS）代码

Question

可否请您让我知道在下面DFS代码不正确。它AFAIK给予正确的结果，但我不知道什么时候会失败。

graph1 = {
    'A' : ['B','S'],
    'B' : ['A'],
    'C' : ['D','E','F','S'],
    'D' : ['C'],
    'E' : ['C','H'],
    'F' : ['C','G'],
    'G' : ['F','S'],
    'H' : ['E','G'],
    'S' : ['A','C','G']
}

visited = []

def dfs(graph,node):
    global visited
    if node not in visited:
        visited.append(node)
        for n in graph[node]:
            dfs(graph,n)

    dfs(graph1,'A')
    print(visited)

输出：

['A', 'B', 'S', 'C', 'D', 'E', 'H', 'G', 'F']

Answer 1

我认为你有一个压痕问题存在。假设你的代码如下所示：

graph1 = {
    'A' : ['B','S'],
    'B' : ['A'],
    'C' : ['D','E','F','S'],
    'D' : ['C'],
    'E' : ['C','H'],
    'F' : ['C','G'],
    'G' : ['F','S'],
    'H' : ['E','G'],
    'S' : ['A','C','G']
}

visited = []

def dfs(graph,node):
    global visited
    if node not in visited:
        visited.append(node)
        for n in graph[node]:
            dfs(graph,n)

dfs(graph1,'A')
print(visited)

我会说几件事情：

• 如果你能避免全局
• 对走访了名单相反的，使用一组

更多：

• 这不会对森林工作，但我想你已经知道，
• 如果引用不存在的节点就会失败。

---

更新的代码：

graph1 = {
    'A' : ['B','S'],
    'B' : ['A'],
    'C' : ['D','E','F','S'],
    'D' : ['C'],
    'E' : ['C','H'],
    'F' : ['C','G'],
    'G' : ['F','S'],
    'H' : ['E','G'],
    'S' : ['A','C','G']
}

def dfs(graph, node, visited):
    if node not in visited:
        visited.append(node)
        for n in graph[node]:
            dfs(graph,n, visited)
    return visited

visited = dfs(graph1,'A', [])
print(visited)

Answer 2

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

   def dfs(s,d):
    def dfs_helper(s,d):
        if s == d:
            return True
        if  s in visited :
            return False
        visited.add(s)
        for c in graph[s]:
            dfs_helper(c,d)
        return False
    visited = set()
    return dfs_helper(s,d) 
dfs('A','E') ---- True
dfs('A','M') ---- False

Answer 3

from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def addEdge(self,u,v):
        self.graph[u].append(v)

    def DFS(self,v,vertex):
        visited = [False]*vertex
        print(self. graph)
        # print(len(self.graph),"+++")
        self.DFSUtil(v,visited)

    def DFSUtil(self,v,visited):
        visited[v]=True
        print(v)

        for i in self.graph[v]:
            if visited[i] == False:
                # print(visited)
                self.DFSUtil(i,visited)
g= Graph()

vertex=7

g.addEdge(0,1)
g.addEdge(0,2)
g.addEdge(0,6)
g.addEdge(0,5)
g.addEdge(5,3)
g.addEdge(5,4)
g.addEdge(4,3)
g.addEdge(6,4)

g.DFS(0,vertex) 

这是上面的代码，因为这并不在所有情况下的修改。 我们必须指定向量的数量，然后手动给边缘。

Answer 4

在Python DFS实现

from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def addEdge(self, u, v):
        self.graph[u].append(v)

    def DFSUtil(self, v, visited):
        visited[v]=True
        print(v)

        for i in self.graph[v]:
            if visited[i] == False:
                self.DFSUtil(i, visited)

    def DFS(self):
        V = len(self.graph)

        visited = [False]*(V)

        for i in range(V):
            if visited[i] == False:
                self.DFSUtil(i, visited)

# Driver code
# Create a graph given in the above diagram
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)

print("Following is Depth First Traversal")
g.DFS()

来源:: this

Answer 5

没有递归：

def dfs(graph, node):
    visited = [node]
    stack = [node]
    while stack:
        node = stack[-1]
        if node not in visited:
            visited.extend(node)
        remove_from_stack = True
        for next in graph[node]:
            if next not in visited:
                stack.extend(next)
                remove_from_stack = False
                break
        if remove_from_stack:
            stack.pop()
    return visited