这是BFS的算法模板。在此,我们有一个while循环,用于检查队列是否为空。我的问题是为什么我们需要内部for循环,一直循环到队列大小。而当队列以FIFO方式处理元素时。
int BFS(Node root, Node target) {
Queue<Node> queue; // store all nodes which are waiting to be processed
int step = 0; // number of steps neeeded from root to current node
// initialize
add root to queue;
// BFS
while (queue is not empty) {
step = step + 1;
// iterate the nodes which are already in the queue
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node cur = the first node in queue;
return step if cur is target;
for (Node next : the neighbors of cur) {
add next to queue;
}
remove the first node from queue;
}
}
return -1; // there is no path from root to target
}
因为否则step
将不正确。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句