[数据结构与算法]广度优先搜索 - 队列实现模板

通过队列实现广度优先遍历，即层序遍历，找到目标节点，返回目标节点到根节点的最短路径长度

?力扣https://leetcode-cn.com/leetbook/read/queue-stack/kc5ge/

模板代码一

package com.company.myQueue;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;

class Node {
    public int value;
    public List<Node> childrenNode;

    public Node(int value) {
        this.value = value;
        this.childrenNode = new ArrayList<>();
    }
}

public class BFSQueue {

    /**
     * 返回目标节点和根节点之间的长度
     */
    int BFS(Node root, Node target) {
        // store all nodes which are waiting to be processed
        Queue<Node> queue = new ConcurrentLinkedQueue<>();

        // number of steps neeeded from root to current node
        int step = 0;

        // initialize
        queue.offer(root);

        // BFS
        while (!queue.isEmpty()) {
            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 = queue.poll();
                if (cur.value == target.value) {
                    return step;
                }

                //示 cur节点的所有孩子节点放到队列中
                for (Node next : cur.childrenNode) {
                    queue.offer(next);
                }
                queue.poll();
            }
        }

        // there is no path from root to target
        return -1;
    }
}

?模板代码二

• 有时，确保我们永远不会访问一个结点两次很重要。否则，我们可能陷入无限循环。如果是这样，我们可以在上面的代码中添加一个哈希集来解决这个问题

• 有两种情况你不需要使用哈希集

  • 你完全确定没有循环，例如，在树遍历中；

  • 你确实希望多次将结点添加到队列中。

public class BFSQueue2 {

    /**
     * 返回目标节点和根节点之间的长度
     */
    int BFS(Node root, Node target) {
        // store all nodes which are waiting to be processed
        Queue<Node> queue = new ConcurrentLinkedQueue<>();

        // store all the used nodes
        Set<Node> used = new HashSet<>();

        // number of steps neeeded from root to current node
        int step = 0;

        // initialize
        queue.offer(root);
        used.add(root);

        // BFS
        while (!queue.isEmpty()) {
            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 = queue.poll();
                if (cur.value == target.value) {
                    return step;
                }

                for (Node next : cur.childrenNode) {
                    if (!used.contains(next)) {
                        queue.offer(root);
                        used.add(root);
                    }
                }
                queue.poll();
            }
        }
        
        // there is no path from root to target
        return -1;
    }
}

没得会员看看别人的答案

【leetcode】286. 墙与门https://blog.csdn.net/weixin_39722329/article/details/96915866