队列和 BFS

BFS是什么

广度优先搜索(BFS),顾名思义,要求的就是广度,也就是就是说,我们有一个节点,这个点又连接了很多子节点,那么只用把它的所有子节点遍历一遍就能实现广度

Current

那么广度遍历顺序就是:A—>BCD—>EFG

BFS与队列结合

不难看出,广度遍历的顺序正好是FIFO,那么我们就可以队列的结构去实现BFS算法

洞悉

  • 与树的层序遍历类似,越是接近根结点的结点将越早地遍历。
  • 如果在第 k 轮中将结点 X 添加到队列中,则根结点与 X 之间的最短路径的长度恰好是 k。也就是说,第一次找到目标结点时,你已经处于最短路径中。

广度优先搜索 - 模板

/**
 * Return the length of the shortest path between root and target node.
 */
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
}

ps:如果需要去重,使用set集合判断

坚持原创技术分享,您的支持将鼓励我继续创作!
  • 本文作者: 带带蓝蜗牛
  • 本文链接: 86.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!