2个节点之间存在连接

Question

我想查找网络中任意两个节点之间是否存在连接，但我似乎无法理解我在 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)。

2个节点之间存在连接

Existence of a connection between 2 nodes

python

connection

graph

nodes