查找图形中的路径数

Question

我试图得到一个可以计算有向图中路径数的代码，我得到了两个代码。第一个代码使用networkx图形作为参数，另一个代码使用图形的邻接列表，但它们都给了我相同的错误答案，所以我想知道是否有人可以帮助我。提前感谢

def caminos(G, u, v):
  H = G.copy()
  for x in H.node:
    H.node[x]['caminos'] = 0
  H.node[u]['caminos'] = 1
  abiertos = [u]
  while abiertos:
    x = abiertos.pop()
    k = H.node[x]['caminos']
    for y in H.adj[x]:
        H.node[y]['caminos'] += k
       abiertos.append(y)
       return H.node[v]['caminos']

def caminos(LA, u, v):
# LA: adjacency list
# Vertex numbered
# from 0 to len(LA) - 1.
n = len(LA)
caminos = n * [0]
caminos[u] = 1
abiertos = [u]
while abiertos:
    x = abiertos.pop()
    k = caminos[x]
    for y in LA[x]:
        caminos[y] += k
        abiertos.append(y)
return caminos[v]

编辑：我尝试了两种代码，结果显示在图片Picture of results and graph used

Answer 1

您的错误在这一行：caminos[y] += k，请尝试递增1以表示“另一条通向y的路径”

也可以考虑使用不同的变量名。有一个变量caminos和一个函数caminos是有效的，但可能会混淆。例如：

def caminos(LA, u, v):
    # LA: adjacency list
    # Vertex numbered
    # from 0 to len(LA) - 1.
    n = len(LA)
    pathcnt = n * [0]
    pathcnt[u] = 1
    abiertos = [u]
    while abiertos:
        x = abiertos.pop()
        k = pathcnt[x]
        for y in LA[x]:
            pathcnt[y] += 1
            abiertos.append(y)
    return pathcnt[v]