java - 使用给定的数据结构查找从节点 A 到节点 B 的路径

Question

我遇到了一个棘手的问题，因为我无法以递归的方式思考找到解决方案。

这是我的数据结构：-

public class Airport {
    String name;
    Set<Neighbour> neighbours;
    ...
}

public class Neighbour {
    Airport airport;
    double costToReach;
    ...
}

我正在尝试从一个Airport到另一个获取可用路径（列表列表） Airport。

List<List<Airport>> getPaths(Airport source, Airport destination) {
    // Logic goes here
}

预期的输入样本：-

Source airport - Mumbai
Destination airport - Delhi

预期输出样本：-

Mumbai -> Pune -> Delhi
Mumbai -> Ahmedabad -> Noida -> Delhi

任何帮助将非常感激。谢谢！

标签： javaalgorithmsearchtree

Answer 1

您可以做的是创建一个方法，该方法采用起点、目标点和一组已访问的机场。在此方法中，您可以：

• 如果起点是终点，则返回路径。
• 遍历起点的所有邻居减去所有已访问的机场，并使用邻居作为起点并使用已访问机场的集合加上当前起点进行递归调用（确保克隆此集合，或使用堆栈并在递归调用后恢复其状态）。

如果这样做，您可以有效地尝试从给定起点到给定目标点的每条路径，而无需两次访问同一个机场。我将把这个递归方法的返回值作为练习留给你（返回值必须用于获取找到的成功路径）。