# 6. BFS

### Template

```java
// BFS问题的本质就是让你在一幅「图」中找到从起点 start 到终点 target 的最近距离
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q = new LinkedList<>(); // 核心数据结构
    Set<Node> visited = new HashMap<>(); // 避免走回头路
    
    q.offer(start); // 将起点加入队列
    visited.add(start);

    while (!queue.isEmpty()) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点：这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj()) {
                if (!visited.contains(x) {
                    q.offer(x);
                    visited.add(x);
                }
            }
        }
    }
    // 如果走到这里，说明在图中没有找到目标节点
}

```

### Typical problems

* Binary tree min depth

```java
//Calculate the minimum depth of a tree
int minDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    // root 本身就是一层，depth 初始化为 1
    int depth = 1;
    
    while (!q.isEmpty()) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            TreeNode cur = q.poll();
            /* 判断是否到达终点 */
            if (cur.left == null && cur.right == null) 
                return depth;
            /* 将 cur 的相邻节点加入队列 */
            if (cur.left != null)
                q.offer(cur.left);
            if (cur.right != null) 
                q.offer(cur.right);
        }
        /* 这里增加步数 */
        depth++;
    }
    return depth;
}

```

* Open the lock

```java
public int openLock(String[] deadends, String target) {
    Set<String> dead = new HashSet<>();
    for (String d : deadends) dead.add(d);

    Queue<String> queue = new LinkedList<>();
    Set<String> visited = new HashSet<>();

    int depth = 0;
    String marker = "0000";

    if (dead.contains(marker)) return -1;

    queue.offer(marker);
    visited.add(marker);

    while (!queue.isEmpty()) {
        int size = queue.size();
        while (size > 0) {
            String lockPosition = queue.poll();
            if (lockPosition.equals(target)) {
                return depth;
            }

            for (int i = 0; i < 4; i++) {
                char c = lockPosition.charAt(i);
                String s1 = lockPosition.substring(0, i) + (c == '9' ? 0 : c - '0' + 1) + lockPosition.substring(i + 1);
                String s2 = lockPosition.substring(0, i) + (c == '0' ? 9 : c - '0' - 1) + lockPosition.substring(i + 1);

                if (!visited.contains(s1) && !dead.contains(s1)) {
                    queue.offer(s1);
                    visited.add(s1);
                }
                if (!visited.contains(s2) && !dead.contains(s2)) {
                    queue.offer(s2);
                    visited.add(s2);
                }
            }
            size--;
        }
        depth++;
    }

    return -1;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding.bea.ai/coding-patterns-and-template/6.-bfs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.