如何在间接图中列出从一个节点到另一个节点的所有路径？

Question

我有一个图表，其节点结构如下：

Class Node:
   int source;
   int next;

所以，我有以下节点：[(1,2), (2,3), (3,4), (1,4)]

我想列出从 1 到 3 的所有可能路径，它将列出：[[(1,2),(2,3)],[(1,4),(4,3)].

我正在尝试使用这段代码，但我遗漏了一些东西：

public List<Node> getNodeNeighbors(Node n) {
    List<Node> filteredNodes = new ArrayList<Node>();
    List<Node> allNodes = (List<Node>) nodesRepository.findAll();
    for (Node node: allNodes) {
        if (node.source == n.next) {
            filteredNodes.add(node);
        }
    }
    return filteredNodes;
}

public List<Node> bfs(Node n, String destinationNodeNumber, List<Node> path) {
        visitedX.add(n); //visitedX is a global List to control visited nodes
        path.add(n); //local path to be listed
        List<Node> neighbors = getNodeNeighbors(n); //function to get node neighbors
        if (n.next.equals(destinationNodeNumber)) {
            allPaths.add(paths); //all paths to be listed
            path.remove(n);
        }
        for (Node nNode: neighbors) {
            if(!visitedX.contains(nNode)) {
                bfs(nNode, destinationNodeNumber, path);
            }
        }
        return null;
    }

Answer 1

你的代码有很多缺陷：

您的 class Node 的名称具有误导性：Edge 会是一个更好的名称，
方法getNodeNeighbors只考虑每条边的一个方向
字段 aCompany 和 anotherCompany 是什么？我假设你的意思是 source 和 next?
什么是 class Contract？
destinationNodeNumber是一个String；它应该是 int.
visitedX 设置防止两条路径使用同一条边；您只需要确保边缘不会出现超过一次 在单个路径中 .
你实际上实现了 DFS，而不是 BFS
你总是将相同的 path 添加到 allPaths；你应该复印一份。

这是一个class Edge:

public class Edge {
    final int source;
    final int next;

    Edge(int source, int next) {
        this.source = source;
        this.next = next;
    }

    @Override
    public String toString() {
        return "(" + source + "," + next + ')';
    }
}

然后class Graph包含搜索算法：

public class Graph {
    private final Iterable<Edge> allNodes;

    public Graph(Iterable<Edge> allNodes) {
        this.allNodes = allNodes;
    }

    public List<Edge> edgesFrom(int vertex) {
        List<Edge> filteredNodes = new ArrayList<Edge>();
        for (Edge node : allNodes) {
            if (node.source == vertex || node.next == vertex) {
                filteredNodes.add(node);
            }
        }
        return filteredNodes;
    }

    public List<List<Edge>> allPaths(int source, int dest) {
        List<Edge> path = new ArrayList<>();
        List<List<Edge>> allPaths = new ArrayList<>();
        for (Edge n: edgesFrom(source)) {
            searchPaths(n, source, dest, path, allPaths);
        }            
        return allPaths;
    }

    private void searchPaths(Edge n, int source, int dest, List<Edge> path,
            List<List<Edge>> allPaths) {
        path.add(n); //local path to be listed
        int next = n.source == source ? n.next : n.source;
        List<Edge> neighbors = edgesFrom(next); //function to get node neighbors
        if (next == dest) {
            allPaths.add(new ArrayList<>(path)); //all paths to be listed
        }
        for (Edge nNode : neighbors) {
            if (!path.contains(nNode)) {
                searchPaths(nNode, next, dest, path, allPaths);
            }
        }
        path.remove(n);
    }
}

下面是使用这些 classes 的示例：

Graph graph = new Graph(Arrays.asList(
        new Edge(1,2), new Edge(2,3), new Edge(3,4), new Edge(1,4)));
List<List<Edge>> allPaths = graph.allPaths(1,3);
for (List<Edge> path: allPaths) {
    System.out.println(path);
}

如何在间接图中列出从一个节点到另一个节点的所有路径？

How to list all paths from a node to another in a indirect graph?

java

graph

nodes

breadth-first-search