Обработка дублирующих узлов в поиске по ширине

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);
        } 
    }
}