java - 在进行广度优先搜索时，访问节点的时间重要吗？

Question

已关闭。这个问题是 off-topic 。目前不接受答案。

---

想要改进这个问题吗？ Update the question所以它是on-topic用于堆栈溢出。

已关闭10 年前。

Improve this question

我用 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) 时(就运行时复杂性或其他一些因素而言)是否重要？ 。我可以在将节点从队列中弹出之后或将其放入队列之前访问该节点。

Answer 1

不，这并不重要。

您基本上是在讨论这两行的顺序:

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

为了性能和代码清晰度，尽早返回总是一件好事，所以我会保留您的代码原样。

如果颠倒这些行的顺序，则会产生调用 addAll() 的额外成本，但可以忽略不计。