创建一个程序，说明最少的联系人数量

Question

给定一个描述社交网络关系的图表，创建一个程序，告诉最小联系人数量才能到达约翰。

输入：

输入的第一行表示图中有多少个n个顶点（2≤n≤100）。接下来n行每行表示一个顶点的信息，格式为：id,A,v1,v2,⋯,vA，其中id为一个标识顶点的整数，A是连接到这个顶点的边的数量，每个vi≠id是一个整数标识相邻的一个顶点id。最后一行有两个 id，由 space 分隔，分别代表你和 John。

退出：

提供联系 John 所需的最少联系人数量，如果可能，请提供消息“Forevis alonis...”，否则。

观察： 每个网络用户都由一个唯一的 id 表示。在第一个示例中，John 已经是您的联系人之一。在第二种情况下，你必须通过用户 2 和 3 才能到达偶像。后一种情况是联系不到你的...

到目前为止，我对这个问题的代码是这样的，因为我无法解决这个问题。代码：

graph = {}
for _ in range(int(input())):
  v, A, *neighbor = map(int,(input().split()))
  graph[v] = neighbor
I, John = map(int, input().split())

def shortest_way(origin, destination, path=[]):
  path.append(origin)
  if origin == destination:
    return path
  shorter = [] 
  for neighbors in graph[origin]:
    if neighbors not in path:
      outro_caminho = shortest_way(neighbors.destination.path[:])

Answer 1

一种可能的解决方案是使用一个list作为当前path，然后一旦到达目的地，将其保存在paths中，这样最后你可以比较所有可能的解决方案和 return 最短的解决方案。

def shortest_way(origin, destination, path, paths):
  if origin == destination:
    path += [destination]
    paths.append(path)
    return paths
  for neighbor in graph[origin]:
    if neighbor not in path:
      shortest_way(neighbor, destination, path+[origin], paths)
  return paths

paths = shortest_way(I, John, [], [])
if not paths:
  print("Forevis alonis...")
print("shortest path =", min([len(i) for i in paths]))

创建一个程序，说明最少的联系人数量

create a program that says the minimum amount of contacts

python

graph

python-3.x