algorithm - 为什么在广度优先搜索中需要访问状态？

Question

我已经实现了广度优先搜索算法(实际上，它是广度优先遍历，因为我没有搜索任何特定节点，只是按照访问的顺序打印出节点值)并且没有使用任何状态跟踪每个节点——即我没有将任何节点标记为已访问。在大多数 BFS 实现中，我看到了将节点标记为已访问的概念，这样您就永远不会访问它两次，但在我的实现中，我看不到任何可能的情况。

有人可以解释为什么访问状态总是有用和/或必要的吗？

这是我的实现:

import java.util.LinkedList;
import java.util.Queue;

public class BFS {

    public static void printTree(Node root) {
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while(queue.isEmpty() == false) {
            Node curr = queue.remove();
            System.out.println(curr.getValue());
            if (curr.getLeft() != null) {
                queue.add(curr.getLeft());
            }
            if (curr.getRight() != null) {
                queue.add(curr.getRight());
            }
        }
    }

    public static void main(String[] args) {
        Node leaf1 = new Node(5);
        Node leaf2 = new Node(6);
        Node leaf3 = new Node(7);
        Node leaf4 = new Node(7);
        Node leaf5 = new Node(11);
        Node rightRightRoot = new Node(12, leaf4, leaf5);
        Node leftRoot = new Node(1, leaf1, leaf2);
        Node rightRoot = new Node(9, leaf3, rightRightRoot);

        Node root = new Node(4, leftRoot, rightRoot);
        printTree(root);
    }

    static class Node {
        private int value;
        private Node left, right;

        public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }

        public Node(int value) {
            this.value = value;
        }

        public int getValue() {
            return value;
        }

        public Node getLeft() {
            return left;
        }

        public Node getRight() {
            return right;
        }
    }
}

Answer 1

您见过的大多数 BFS 实现都会遍历任意图并遍历树。这两种情况的区别在于周期。任意图都可以有它们，并且状态对于不将节点两次放入队列是必要的，但在你的情况下你可能没有它们。