グラフ内に2つのノード間のルートがあるかどうかをテストします。

Question

私はすでに同様の質問があることを知っていますが、私は自分の検索方法を評価したいと思います。私はDFSアルゴリズムを使用して、2つのノード間にルートがあるかどうかを調べました。ここに私のコードがありますが、私のコードが結果で失敗するテストケースがあるかどうかを知りたいと思います。

public boolean routeExists(Node start, Node end) { 
    Set<Node> visited = new HashSet<>(); 
    Stack<Node> stack = new Stack<>(); 

    visited.add(start); 
    stack.push(start); 

    while(!stack.isEmpty()) { 
     Node current = stack.pop(); 

     if(current.getValue() == end.getValue()) { 
      return true; 
     } 

     for(Node adj : current.getAdjacent()) { 
      // keep track of visited nodes 
      if(!visited.contains(adj)) { 
       stack.push(adj); 
       visited.add(adj); 
      } 
     } 
    } 

    return false; 
} 

私は今、コードが訪れたノードを追跡し、彼らは過去に訪問してきた場合は、それらを展開しません、EDITを行いました。今はこれがうまくいくと思います。

Answer 1

このコードは、多くの入力グラフに対して無限ループに入ります。

A->B 
A->C 
C->A 

あなたのコードでは、まず、次にCを訪問し、リストの上にプッシュし、その後、Cを押して、リストの上にBを押して、します：

はエッジがあるとき、AからBへのルートを見つけることを検討しますスタックのオーバーフローが発生するまで繰り返します。

あなたはwikipedia

1 procedure DFS(G,v): 
2  label v as discovered 
3  for all edges from v to w in G.adjacentEdges(v) do 
4   if vertex w is not labeled as discovered then 
5    recursively call DFS(G,w) 

と比較した場合、あなたは新しい頂点が既に発見されていないことを確認するためのテストが欠落していることがわかります。