我已经实现了广度优先搜索算法(实际上,它是广度优先遍历,因为我没有搜索任何特定节点,只是按照访问的顺序打印出节点值)并且没有使用任何状态跟踪每个节点——即我没有将任何节点标记为已访问。在大多数 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;
}
}
}
最佳答案
您见过的大多数 BFS 实现都会遍历任意图并遍历树。这两种情况的区别在于周期。任意图都可以有它们,并且状态对于不将节点两次放入队列是必要的,但在你的情况下你可能没有它们。
关于algorithm - 为什么在广度优先搜索中需要访问状态?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26451034/