在有向圖中找到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;