4

Java で深さ優先検索アルゴリズムを実装しようとしています。このメソッドが無限ループに入る理由は何ですか? ありがとう。

public Node search(Graph graph, String nodeName, int ID) {

    //Get the root node
    Node root = graph.getRoot();

    Stack<Node> stack = new Stack<Node>();
    //Add the root to the stack
    stack.push(root);

    while(!stack.isEmpty()) 
    {
        Node n = stack.pop();
        //Check to see if node n is the requested node
        if(n.getName().equals(nodeName))
        {
            //Found
            return n;
        }else
        {
            //Create an array of the leaf nodes to node n
            Node[] children = n.getNeighbours();
            for(int i =0; i<children.length; i++)
            {
                //Add the leaf nodes to the stack
                stack.push(children[i]);
                System.out.println(stack.peek());
            }
        }
    }
    //Not found so return null
    return null;
}
4

3 に答える 3

5

グラフにサイクルがある場合 (または無向の場合)、ノードにアクセスした後にノードを「マーク」する必要があります。そうしないと、それらに戻ってくることになります。

于 2012-10-25T15:27:50.500 に答える
3

グラフがツリーでない限り、サイクルがあります。ノードはそれ自身の孫になることができます。既にアクセスしたノードが検索ツリーに追加されないようにする必要があります。

これを行う簡単な方法は、別のデータ構造を使用することです。

Set<Node> visitedNodes = new HashSet<Node>();

//...
if ( !visitedNodes.contains(children[i]) ) {
   stack.push(children[i]);
   visitedNodes.add(children[i]);
}
于 2012-10-25T15:27:34.150 に答える
0

グラフにサイクルが含まれている場合、これは予期された動作です。単純な深さ優先検索は、既に訪問した子を訪問し、無限にループします。

これを回避する簡単な方法は、探しているノードであるかどうかを確認した後、すべてのノードを HashSet に追加し、既に検査されている場合はスタックへの追加を拒否することです。

于 2012-10-25T15:32:43.713 に答える