algorithm - 在有向图中找到 2 个节点之间的路径？

Question

我正在努力处理以下代码，因为我尝试编写一个函数来查找两个节点之间是否存在路由:

我可以使用 isThereRoute 函数的主要位置。

ArrayList<Node> visited = new ArrayList();
visted.add(start_node);
System.out.println(isThereRoute(start_node, end_node, visited));

下面是函数

bool isThereRoute(Node A, Node B, ArrayList<Node> visited){
    flag = false;
    if(A == B) return true;
    for(Node n : A.adjacent()){
        if (!visited.contains(n)) {
            visited.add(n);
            flag = isThereRoute(n, B, visited);
        }
    }
    return flag;
}

所有节点都在 Graph 类中，其中 Adjacent() 返回邻接列表。该程序有时可以运行，但在大多数情况下，即使在 2 个节点之间存在路由，也会打印 false。

Answer 1

如果有路由，或者当 flag 为真时，你需要打破循环。

bool isThereRoute(Node A, Node B, ArrayList<Node> visited){
    flag = false;
    if(A == B) return true;
    for(Node n : A.adjacent()){
        if (!visited.contains(n)) {
            visited.add(n);
            flag = isThereRoute(n, B, visited);
        }
        if (flag == true) break;  //<====insert here
    }
    return flag;
}

如果您不打破循环，标志可能会在任何后续迭代中更改为 false。