Java自定义树实现BFS遍历返回重复节点的解决方法咨询

我正在Java中实现树结构的BFS遍历，项目包含两种实现策略：一种使用Java Collections，另一种使用自定义节点与引用。我的自定义实现进行BFS遍历时有时会返回重复节点，当结构中存在意外的重复引用时，同一节点会多次出现在遍历结果中。以下是我当前的BFS方法：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public List<String> bfs(Node root) {
    Queue<Node> queue = new LinkedList<>();
    List<String> result = new ArrayList<>();

    queue.add(root);

    while (!queue.isEmpty()) {
        Node current = queue.poll();

        result.add(current.getName());

        for (Node child : current.getChildren()) {
            queue.add(child);
        }
    }

    return result;
}

请问避免BFS遍历中重复访问节点的正确方法是什么？即使结构理论上应为树，是否仍需使用Set跟踪已访问节点？

核心方法：用Set跟踪已访问节点 #

当结构中存在意外的重复引用时，你的"树"实际上已经变成了有环图，这时候必须通过记录已访问节点来避免重复遍历和潜在的死循环。

修改后的BFS实现 #

添加一个Set<Node>存储已处理的节点，在将节点加入结果前先检查是否已访问；更高效的方式是在将子节点加入队列前就检查并标记，避免队列中存入重复节点：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.HashSet;
import java.util.Set;

public List<String> bfs(Node root) {
    Queue<Node> queue = new LinkedList<>();
    List<String> result = new ArrayList<>();
    Set<Node> visited = new HashSet<>();

    if (root == null) {
        return result;
    }

    queue.add(root);
    visited.add(root);

    while (!queue.isEmpty()) {
        Node current = queue.poll();
        result.add(current.getName());

        for (Node child : current.getChildren()) {
            if (!visited.contains(child)) {
                visited.add(child);
                queue.add(child);
            }
        }
    }

    return result;
}

关于"理论上是树是否需要Set"的问题 #

如果能100%保证结构是严格的树（无环、每个节点仅有一个父节点、无重复引用），理论上不需要Set。但实际工程中建议始终加上：

• 意外的引用错误（比如代码逻辑失误导致节点被重复添加为子节点）很难完全避免；
• 额外的Set开销对于大多数场景可以忽略，却能大幅提升代码鲁棒性，避免出现难以排查的重复结果或死循环。

内容的提问来源于stack exchange，提问作者DeividGr