处理广度优先搜索中的重复节点

Question

假设有一个图表。节点的形式为 GraphNode。该图可以有重复的节点。我们必须在图上做一个 BFS。一开始我们不知道整个图，即没有办法索引图的节点。例如，只有根节点作为 BFS 函数的输入。

这是GraphNode的定义，不能修改。

public class GraphNode {
  int val;
  GraphNode left;
  GraphNode right;
  GraphNode(int x) { val = x; }
}

在 BFS 算法中处理访问节点的最佳方式是什么？请记住，该图具有重复节点，即具有相同键的多个节点。而且我们不想删除或忽略重复项。

Answer 1

为什么那些重复键对广度优先遍历很重要？

例如

static void breadthFirstVisit(TreeNode root) {
    Deque<TreeNode> queue = new LinkedList();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println("visiting node with value " + node.val);
        // visit(visitedNode)
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
}

或像这样省略重复项

 static void breadthFirstVisit(TreeNode root) {
    Deque<TreeNode> queue = new LinkedList();
    Set<TreeNode> visited = new HashSet();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println("visiting node with value " + node.val);
        // visit(visitedNode)
        if (node.left != null && !visited.contains(node.left)) {
            queue.add(node.left);
            visited.add(node.left);
        } 
        if (node.right != null && !visited.contains(node.right)) {
            queue.add(node.right);
            visited.add(node.right);
        } 
    }
}