1

Javaのツリーに対して次のBFSを作成しました。

public class Node
{
    public int value;
    public ArrayList<Node> myChildren = new ArrayList<Node>();

    public Node(int v)
    {
        value = v;
    }
}

public Node breadthFirstSearch(Node root, int value)
{
    if(root == null) return null;
    Queue<Node> nodesToVisit = new LinkedList<Node>();
    nodesToVisit.add(root);
    while(nodesToVisit.size() > 0)
    {
        Node currentNode = nodesToVisit.remove();
        if(currentNode.value == value) return currentNode;
        nodesToVisit.addAll(currentNode.myChildren);
    }

    return null;
}

私の質問は、ノードを「訪問」するときに（実行時の複雑さやその他の要因の観点から）重要かどうかif(currentNode.value == value)です。ノードをキューから取り出した後、またはキューに入れる前に、ノードにアクセスできます。

4

2 に答える 2

1

いいえ、それは問題ではありません（大いに）。

あなたは基本的にこれらの2行の順序について話している：

if (currentNode.value == value) return currentNode;
nodesToVisit.addAll(currentNode.myChildren);

パフォーマンスとコードを明確にするために、早期に戻ることは常に良いことなので、コードはそのままにしておきます。

これらの行の順序を逆にすると、への呼び出しの追加コストが発生しますが、addAll()無視できます。

于 2012-09-24T19:00:06.343 に答える
1

それは問題ですか？それはあなたが何をしているかによります。

ツリー内に検索基準を満たすノードが複数ある場合、親の前に子ではなく、子の前に親にアクセスすると、検索で返されるノードが変わる可能性があります。それは実際に起こりますか？お申し込み内容により異なります。

ビッグオーの複雑さはどちらの方法でも同じです。ツリーと検索の特性によっては、いずれかの方法でより多くの操作が必要になる場合があります。(たとえば、検索の 50% がルート ノードに格納されている値に対するものである場合、最初に親ノードにアクセスすると、コードの実行が速くなります。)

検索が「失敗」した場合 (値がツリー内のどこにも見つからない場合)、実行される操作の数は、ノードにアクセスする順序に関係なく同じになります。

于 2012-09-24T18:25:44.990 に答える