如何在不返回或中斷Python的情況下實現函數

Question

我是在節點a和b之間遍歷的dfs，但是當我在節點b處打開循環時，算法會繼續。這裏是我的代碼：

import networkx as nx 

def Graph(): 
    G=nx.Graph() 

    k = 30 

    G.add_edge(1,2) 
    G.add_edge(2,3) 
    G.add_edge(1,3) 

    for i in range(2,k+1): 
     G.add_edge(2*i-2,2*i) 
     G.add_edge(2*i-1,2*i) 
     G.add_edge(2*i-1,2*i+1) 
     G.add_edge(2*i,2*i+1) 

    G.add_nodes_from(G.nodes(), color='never coloured') 
    G.add_nodes_from(G.nodes(), label = -1) 
    G.add_nodes_from(G.nodes(), visited = 'no') 

    return G 

def dfs(G,a,b,u): 
    global i 
    G.node[u]['visited'] = 'yes' 
    i += 1 
    G.node[u]['label'] = i 
    print(u) 
    print("i", i) 
    for v in G.neighbors(u): 
     if v == b: 
      G.node[v]['visited'] = 'yes' 
      i += 1 
      G.node[v]['label'] = i 
      print("b is ", v) 
      print("distance from a to b is ", G.node[v]['label']) 
      break### the problem area, doesn't break out the function 
     elif v != b: 
      if G.node[v]['visited'] == 'no': 
       dfs(G,a,b,v) 
G=Graph() 
a=1 
b=19 
i = 0 
print('Depth-First-Search visited the following nodes of G in this order:') 
dfs(G,a,b,a) ### count the DFS-path from a to b, starting at a 
print('Depth-First Search found in G7 a path between vertices', a, 'and', b, 'of length:', G7.node[b]['label']) 
print() 

我已經嘗試返回for循環，嘗試使用中斷，也試過try/catch方法。有沒有優雅的方式來打破這個功能，或者我將不得不重寫它，因爲它不通過你的所有鄰居遞解？

Answer 1

這裏的問題不是break或return，但您使用遞歸，並且您不會停止每個遞歸調用中的循環。你需要做的是從你的dfs函數返回一個結果，告訴你是否找到了你的節點，然後如果遞歸調用找到它，則在你的else塊中打破循環。事情是這樣的：

def dfs(G,a,b,u): 
    global i 
    G.node[u]['visited'] = 'yes' 
    i += 1 
    G.node[u]['label'] = i 
    print(u) 
    print("i", i) 
    for v in G.neighbors(u): 
     if v == b: 
      G.node[v]['visited'] = 'yes' 
      i += 1 
      G.node[v]['label'] = i 
      print("b is ", v) 
      print("distance from a to b is ", G.node[v]['label']) 
      return True 
     elif v != b: 
      if G.node[v]['visited'] == 'no': 
       found = dfs(G,a,b,v) 
       if found: 
        return True 
    return False 

注意這是如何傳播的成功結果備份通過您的整個調用堆棧。

Answer 2

在這種情況下，我經常使用全局標誌變量來表示搜索已完成。例如path_found。

Answer 3

如果我明白了，你的問題不是你不能退出該功能。

問題是你沒有從遞歸中突圍。有很多方法可以解決這個問題。

這是很多例子之一。通過返回True並在每次調用中檢查它，您將開始冒泡並在遞歸的每個循環中跳過。您可以將True值理解爲'找到路徑'

def dfs(G,a,b,u): 
    global i 
    G.node[u]['visited'] = 'yes' 
    i += 1 
    G.node[u]['label'] = i 
    print(u) 
    print("i", i) 
    for v in G.neighbors(u): 
     if v == b: 
      G.node[v]['visited'] = 'yes' 
      i += 1 
      G.node[v]['label'] = i 
      print("b is ", v) 
      print("distance from a to b is ", G.node[v]['label']) 
      return True 
     elif v != b: 
      if G.node[v]['visited'] == 'no': 
       if dfs(G,a,b,v): 
        return True