有向グラフ内の2つのノード間のルートを見つけるか？

Question

私は2つのノード間のルートがある場合に発見するための関数を記述しようとすると、コードの一部を次のように苦しんでいます：

主なところ私ができる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; 
} 

で隣接リストを返します。プログラムが動作することはありますが、ほとんどの場合、2つのノード間にルートがあってもfalseが出力されます。

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;