2 개의 노드 사이의 연결이 존재합니다

Question

네트워크의 2 노드 사이에 연결이 있는지 찾고 싶습니다. check_connection 함수에서 어디서 잘못되었는지 알 수 없습니다! 도와주세요!

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]) 

Answer 1

그래프에는 a-> g-> d-> a가 있습니다. 당신의 기능은 글자 그대로 반복됩니다. 가장 최근의 노드뿐만 아니라 모든 방문 노드 세트를 유지하고 다음 노드가 이미 방문되었는지 확인해야합니다. 따라서 b=0을 b=set(), b==a ~ a in b 및 b=v1 ~ b.add(v1)으로 변경하십시오.