java – 查找人与人之间交易次数最少的算法

可以通过广度优先搜索来发现最短路径.您可以按如下方式实现：

todo = [starting_book]
path = {starting_book: None}
while len(todo) and target_book not in path:
    book = list.pop(0)
    for next_book in neighbors(book):
        if next_book not in path:
            path[next_book] = book
            todo.append(next_book)
if target_book in path:
    solution = [target_book]
    while solution[-1] != starting_book:
        solution.append(path[solution[-1]])
else:
    solution = None

请注意,我在这里提供的解决方案可以实现一系列图书交易,而不是人.将特定图书交易转回到与之交谈的人可以通过搜索s或查找表来完成.

这也不是一个在线解决方案 – 跟踪最短路径,因为在s中添加/删除的东西将是很多工作.