查找图形中的路径数

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]

编辑：我尝试了两个代码，结果在图片中 使用的结果和图表图片

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]