0

私はこのプロジェクトに一人で取り組んでおり、別の目でこれを見て、自分が間違っていることを確認することができます。最初のループは無限に実行されます。

public void bfs(String start)
    {   
        //Initial Case
        add_queue.add(start);
        graph.visit(start);

        Iterator<String> neighbors;
        String neighbor;

        while(!add_queue.empty())
        {
            neighbors = graph.neighbors(start);
            neighbor = neighbors.next();
            graph.visit(neighbor);
            add_queue.add(neighbor);
            while(neighbors.hasNext())
            {
                neighbor = neighbors.next();
                if(!graph.isVisited(neighbor))  //If vertex is not visited it is new and is added to the queue
                {
                    add_queue.add(neighbor);
                    graph.visit(neighbor);
                }

            }   
            start = add_queue.remove();
            remove_queue.add(start);    //transfers vertex from add_queue to remove queue so that the order that the vertices were traversed is stored in memory    
        }
    }
4

4 に答える 4

3

すでに訪問されているかどうかを確認せずに、隣人の最初の頂点を追加していると思います..ここ：

neighbor = neighbors.next(); <- you get first
graph.visit(neighbor); <- you visit
add_queue.add(neighbor); <- you add it without any check
while(neighbors.hasNext())
{
  neighbor = neighbors.next();
  if(!graph.isVisited(neighbor)) <- you do check for the others
  {
     add_queue.add(neighbor);
     graph.visit(neighbor);
  }
}

これは、そのキューを空にすることは決してないことを意味します.. サイズが 1 で始まるため、反復ごとに 1 つの要素を削除しますが、少なくとも 1 つの要素を追加します (誰も追加しません)。

于 2010-06-04T18:49:47.553 に答える
0

調査するいくつかの場所：

  1. graph.isVisited()を介してノードにアクセスしたことを実際に認識していることを確認してくださいgraph.visit()。
  2. 本当にgraph.neighbor(start)リターンスタートの隣人ですか？そして、このリストにスタートを含めないのですか？
于 2010-06-04T18:50:20.857 に答える
0

あなたのコードは少し不明瞭です。正確には何がgraph.neighbors返されますか？

一般に、BFSを実行するには、現在のノードの子をキューに追加しますが、隣接ノードは追加しません。すべてがキューに入っているので、これにより、ツリー内の各ノードに正しい順序でアクセスできるようになります。これが一般的なグラフではなくツリーであると仮定すると、これにより、ノードに2回以上アクセスしないようになり、のチェックを削除できるようになりますisVisited。

したがって、次のノードをキューから取り出し、そのすべての子をキューに追加し、ノードにアクセスして、キューが空になるまで繰り返します。

于 2010-06-04T18:54:34.767 に答える
0

のadd_queueの定義はempty()?

ネーミングの問題である可能性がありますが、空であるかどうかをチェックするだけでなく、何かを行うように思えます (これはおそらく と呼ばれempty() ますisEmpty())。

また、外側の各ループ (内側の while の直前) で add_queue に少なくとも 1 つを常に追加しているように見えますが、反復ごとに add_queue から 1 つの項目のみを削除します。

于 2010-06-04T18:49:10.540 に答える