java - 如何获取项目之间的所有路径

Question

我必须计算列表中两个项目之间的所有可能路径。每个项目都有两个字段:它的名称和它的邻居的名称。

我必须生成一个包含所有项目的列表，这些项目允许我在两个特定项目之间建立路径。

假设我有 Item(A, B) 和 Item(A, C)，并且有人要求我提供从 B 到 C 的解决方案。我必须返回这两个 Item，因为我可以使用它们从 B 到达 C :B->A->C。

请注意，我对到达目的地所需的元素没有限制。

我尝试了多种解决方案，但没有一个成功。我知道我必须使用某种递归函数，但我不知道如何使用。

这是我的 Item 类:

public class Item {
    private String name;
    private String neighbor;

    public Item(String name, String neighbor){

        this.name = name;
        this.neighbor = neighbor;
    }

    //getters and setters
}

由于我必须获取两个特定项目之间的所有可能路径，因此我必须返回列表的列表:

List<List<Item>> solution;

我的解决方法

我最终将我的项目转换为图表，一旦构建完成，我就使用深度优先横向 (DFT) 来查找源和目的地之间的所有可能路径。

我设置了将每个项目的名称与图形表示相关的键值对，并从图形中获取指示图形中路径的整数列表(例如 1-2-3-5)。从该列表中，我找到我的项目，并返回具有我已经解释过的格式的列表列表。

专门为有类似问题的人发帖!

Answer 1

根据我的评论尝试这样的事情:

you could iterate over each node and perform a depth-first search on each node to see if you can reach the desired node

您标记访问过的节点既可以避免循环(如果它们在您的用例中可能存在)，也可以跟踪路径。

List<Item> depthFirstSearch(Item startItem, Item desiredItem, List<Item> visitedNodes) {
    if (startItem.equals(desiredItem)) {
        return visitedNodes;
    }

     // Exit if we reach a cycle or no more neighbors to follow
    if (visitedNodes.contains(startItem) || startItem.getNeighbor() == null) {
        return null;
    }

    visitedNodes.add(startItem); 

     // Recurse; continue search from neighbor
    return depthFirstSearch(startItem.getNeighbor(), desiredItem, visitedNodes);
}

并像这样使用它(您需要根据您的代码进行调整):

List<Item> items;
List<List<Item>> result = new List<List<Item>>();

for (Item item : items) {   
    List<Item> pathToDesired = depthFirstSearch(item, desiredItem, new LinkedList<Item>());

    if (pathToDesired != null) {
        results.add(pathToDesired);
    }
}

结果将包含所需项目的所有路径。