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

基本問題是隻有一條路徑。當您遞歸調用dfs時，它會修改path。呼叫返回時，它不會恢復舊值path。解決方法是將副本的path傳遞給dfs。請注意遞歸調用中的path[:]。

第二個問題是，當你找到一條路徑時，你將它連接到res，而你真的想把它追加到res。

在下面的代碼中，我已經取消了start是否是中的關鍵字。如果不是中的密鑰，它不可能傳遞給函數。

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 2

問題是你的回溯。搜索從A - > B - > D開始，並且在D處達到死角，因爲唯一的繼承者是已經訪問過的B。所以它備份了，但是你沒有從res中刪除D.它只停留在那裏，所以當它繼續E - > F時，結果中仍然有D。

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