dfs 实现图形，python

Question

我试图在 python 中使用 dfs 实现一个图，以找到从 'A' 到 'F' 的所有可能路径。该图是：

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

下面是我的代码：

def dfs_path(graph,start,end):
    res = []
    dfs(graph,start,end,[],res)
    return res
def dfs(graph,start,end,path,res):
    path+=[start]
    if start == end:
        res+=[path]
    elif not graph.has_key(start):
        return
    else:
        for node in graph[start]:
            if node not in path:
                dfs(graph,node,end,path,res)
print dfs_path(graph,'A','F')

通过处理打印，我没有得到我想要的，而是得到 [['A', 'B', 'D', 'E', 'F', 'C']]

谁能告诉我我的代码有什么问题，如果可能的话，我想知道以相同格式编写此代码的正确方法。谢谢

Answer 1

问题出在你的回溯上。搜索从 A -> B -> D 开始，在 D 处进入死胡同，因为唯一的后继者是已经访问过的 B。所以它备份了，但你还没有从 res 中删除 D。它只是停留在那里，所以当它继续 E -> F 时，您的结果中仍然有 D。

Answer 2

基本问题是只有一条路。当您对 dfs 进行递归调用时，它会修改 path。当调用returns时，它不会恢复path的旧值。解决这个问题的方法是将 path 的 copy 传递给 dfs。注意递归调用中的path[:]。

第二个问题是，当您确实找到路径时，您将它与 res 连接起来，而实际上您想要将它附加到 res。

在下面的代码中，我取消了对 start 是否是 graph 中的键的检查。如果它不是 graph.

中的键，则无法将其传递给函数

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

def dfs_path(graph,start,end):
    result = []
    dfs(graph,start,end,[],result)
    return result

def dfs(graph,start,end,path,result):
    path+=[start]
    if start == end:
        result.append(path)
    else:
        for node in graph[start]:
            if node not in path:
                dfs(graph,node,end,path[:],result)
print(dfs_path(graph,'A','F'))

这会打印

[['A', 'B', 'E', 'F'], ['A', 'C', 'F']]

我觉得很合适。

我会说你得到的函数基本上是正确的，但你需要复习 python 列表的技术细节（通常可能还有可变数据结构。）

Answer 3

这是一个带迭代的DFS算法。

def dfs(graph, start):

    vertex=start

    visited, stack = [vertex], [vertex]  #add start index to both visited and stack   

    while stack:    #while stack is not empty
        #for each of the children of current vertex we find the first non visited child and add it to visited as well as stack

        for i,each in enumerate(graph[vertex]):  
            if each not in visited:
                visited.append(each)
                stack+=[each]    #push the element to stack if it is visited
                vertex=each      #change current vertex to last visited vertex
                break            #since the stack keeps track of the order of elements we can jump to children of current vertex.
            else:
                #if the length of children of a vertex is reached and all children are visited then pop the last element from stack
                if i==len(graph[vertex])-1:   
                    vertex=stack.pop() 
                    break
                else:
                    continue    #continue till the end to check if all the children of current vertex are visited
    return visited
graph = {'A': ['B', 'C'],
     'B': ['A', 'D', 'E'],
     'C': ['A', 'F'],
     'D': ['B'],
     'E': ['B', 'F'],
     'F': ['C', 'E']}
dfs(graph,'A')

Answer 4

#Last In First Out
def dfs(G,Source,Goal):
    stack=[]
    stack_visited_result=[]
    stack.append(Source)
    stack_visited_result.append(Source)
    while len(stack)>0:
        print("**********STEP-",len(stack),"**********")
        r=0
        v=stack[-1]
        print("The current stack is ",stack);
        if(len(G.get(v))<=0):
            print("No key value for the top of the stack",x)
            stack.pop()
            v=stack[-1]
            print("After popping stack",stack)
        print ("top of the stack = " , v)
        for x in G[v]:
            if x not in stack_visited_result:
                r=1
                print ("value of x(ADJACENT VERTICES) " , x)
                stack.append(x)
                print("stack ",stack)
                if(stack[-1]==Goal):
                    print("--DESTINATION REACHED----")
                    print("RESULT FOR DFS ",stack_visited_result)   
                    quit()
                stack_visited_result.append(x)
                print("stack-visited ",stack_visited_result)
                break
        if(r is not 1):
                print("already visited so,pop the element")
                stack.pop()             
G={1:[2,3],2:[4,5,6],3:[],4:[],5:[7],6:[],7:[8],8:[]}
dfs(G,1,3)




This code will be used in case of directed graph

dfs 实现图形，python

dfs to implement a graph, python

python

graph

depth-first-search