存在的節點的連接之間的2

我想找如果網絡中的任意兩個節點之間存在連接，我似乎無法理解，我到底做錯了check_connection功能！請幫忙！存在的節點的連接之間的2

b=0 

def make_link(G, node1, node2): 
    if node1 not in G: 
    G[node1] = {} 
    (G[node1])[node2] = 1 
    if node2 not in G: 
    G[node2] = {} 
    (G[node2])[node1] = 1 
    return G

###########爲什麼這個函數迭代到無窮大？

def check_connection(G, v1, v2): 
    # Return True if v1 is connected to v2 in G 
    # or False if otherwise 

    global b 

    for a in G[v1].keys(): 

    if a==v2: 
     return True 

    if b==a: 
     continue 

    else: 
     b=v1 
     check_connection(G,a,v2) 
    return False 

edges = [('a', 'g'), ('a', 'd'), ('g', 'c'), ('g', 'd'), ('b', 'f'), ('f', 'e'), ('e', 'h')] 

G = {} 

for v1, v2 in edges: 
    make_link(G, v1, v2) 

print check_connection(G,edges[0][0],edges[4][1])

來源

2017-04-24 Sarvesh Patil

難道是因爲你有（A，V2）check_connection（G）你的函數中調用的函數？ –

你的圖有一個循環a-> g-> d-> a。你的函數保持字面循環。您應該維護一組所有訪問的節點，而不僅僅是最近的節點，並檢查下一個節點是否已經訪問過。因此，改變b=0到b=set()，b==a到a in b，並b=v1到b.add(v1)。

來源

2017-04-24 05:17:56 DyZ

它仍然對任何搜索操作返回False，因爲for循環結束後，最後遞歸將拋出返回虛假陳述，即使其真實的。即，其在第二個最後遞歸返回true，如果我們A和C之間檢查連接，並在最後遞歸，這實際上將值回哪裏調用該函數返回false。 –

您的遞歸函數不正確。最驚人的錯誤：你從來沒有檢查由嵌套調用的返回值來'你試圖實現check_connection'.The算法稱爲深度優先搜索（DFS）。也許你應該搜索它的僞代碼，並且也存在許多Python實現。 – DyZ

存在的節點的連接之間的2

回答

相關問題