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

有关系吗？这取决于你在做什么。

如果树中有多个节点满足您的搜索条件，则在子节点之前访问父节点，而不是在父节点之前访问子节点，可能会更改搜索返回的节点。这真的会发生吗？这取决于您的应用程序的详细信息。

无论哪种方式，big-O 复杂度都是相同的。根据树和搜索的特性，可能需要以一种或另一种方式进行更多操作。（例如，如果 50% 的搜索是针对存储在根节点中的值，那么通过首先访问父节点，您的代码将运行得更快。）

当搜索“失败”（在树中找不到该值）时，无论您访问节点的顺序如何，执行的操作数都是相同的。

于 2012-09-24T18:25:44.990 回答
1

不，没关系（很多）。

您基本上是在谈论这两行的顺序：

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

为了性能和代码清晰，早点返回总是一件好事，所以我会让你的代码保持原样。

如果您颠倒这些行的顺序，您将产生调用的额外费用，addAll()但是这可以忽略不计。

于 2012-09-24T19:00:06.343 回答