在有向图中找到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类，其中相邻（）返回一个邻接表。程序有时可以工作，但在大多数情况下，即使在2个节点之间存在路由，也会打印错误。

Answer 1

如果存在路线或标记为真，则需要打破循环。

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。

Answer 2

你的行flag = isThereRoute(n, B)将意味着该标志被设置为最后一个检查的节点。这是没有意义的 - 它应该尽快找到一个路径停止：

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