这里需要我们完成最短路径这个函数,是要找出从 source 到 target 建立起关系的最短路径
这里是通过出演同一部电影来建立联系
首先,可以调用 utils 里写好的 queuefronti,这里之所以选择 queue,是因为要找最短,所以我们选择 BFS,广度优先
然后,不同于课上的 maze 迷宫问题,我们不用新定义一个 class
这里先是添加初始节点,然后定义 explored,用于标记检测过的 node
然后定义返回条件,判断是否是 target,使用课上的方法回溯,并将 path 翻转(注意 path 中元素的格式)
然后添加遍历的逻辑,借助 neighbors 函数,获取同一电影的其他人,查找是否检测过,如果没有,那就添加到frontier 之中
这里的 frontier 是需要下一步遍历的节点,explored 是遍历过的节点