算法学习之BFS广度优先搜索(java版)

广度优先搜索就如其名字一样，优先横向搜索，通常用于树和图中。

概念

图中给出了一棵二叉树，按照广度优先算法输出的结果是：1, 2, 3, 4, 5, 6

可以将广度优先算法抽象成队列的入队与出队的过程。
设队列为queue，并初始化为空

1. queue=[1]，首个节点入队（表示待搜索节点）
2. queue=[2, 3]，队列内头部节点出队（表示已经搜索了该节点），将该节点的左右子节点入队插入到尾部（表示其子节点待搜索）
3. queue=[3, 4, 5]，队列内头部节点2出队，将节点2的两个子节点入队插入到尾部。
4. queue=[4, 5, 6]，队列内头部节点3出队，将节点3的子节点入队插入到尾部。
5. queue=[5,6]，队列内头部节点4出队，已无子节点。
6. queue=[6]，队列内头部节点5出队，已无子节点。
7. queue=[]，队列内头部节点6出队，已无子节点。
8. 算法结束

注意：数据结构中队列的特性先进先出。

框架

class Node {
    intval;
    Node left;
    Node right;
}

public static int BFS(Node start, Node target) {
    Queue<Node> q = new LinkedList<>(); // 核心数据结构队列

    q.offer(start);
    int step = 1; // 记录步骤

    while (!q.isEmpty()) { // 一层走到下一层
        int sz = q.size();
        // 取当前节点，往下走
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            if (cur.left == null && cur.right == null)
                return step;
            if (cur.left != null)
                q.offer(cur.left);
            if (cur.right != null)
                q.offer(cur.right);
        }
        step++;
    }
    return step;
}

例题

打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字0-9。每个拨轮可以*旋转：例如把’9’变为’0’，‘0’变为’9’。每次旋转都只能旋转一个拨轮的一位数字。
初始的数字为’0000’，一个代表四个拨轮的数字的字符串
列表deadends包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串target代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回-1
输入：deadends = [“0201”,“0101”,“0102”,“1212”,“2002”], target = “0202”
输出：6

思路：
可以将这个问题抽象成一棵树。树的根节点为0000，其结构如下图

每一个节点的下一层有8个节点，分别对应了每位数字的上下旋转两种情况。我们需要避开死亡数字，在最矮的层级中找到目标数字。

public static int openLock(String[] deadends, String target) {
    Set<String> deads = new HashSet<>();
    for (String s : deadends)
        deads.add(s);
    // 记录已经遇到过的密码，防止走回头路，相当于树的剪枝
    Set<String> visited = new HashSet<>();
    Queue<String> q = new LinkedList<>();

    int step = 0;
    q.offer("0000");
    visited.add("0000");

    while (!q.isEmpty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            String cur = q.poll();
            // 判断是否到达终点
            if (deads.contains(cur))
                continue;
            if (cur.equals(target))
                return step;

            for (int j = 0; j < 4; j++) {
                String up = plusOne(cur, j);
                if (!visited.contains(up)) {
                    q.offer(up);
                    visited.add(up);
                }
                String down = minusOne(cur, j);
                if (!visited.contains(down)) {
                    q.offer(down);
                    visited.add(down);
                }
            }
        }
        step++;
    }
    return -1;
}

public static String plusOne(String cur, int pos) {
    char[] ch = cur.toCharArray();
    if (ch[pos] == '9')
        ch[pos] = '0';
    else
        ch[pos] += 1;
    return new String(ch);
}

public static String minusOne(String cur, int pos) {
    char[] ch = cur.toCharArray();
    if (ch[pos] == '0')
        ch[pos] = '9';
    else
        ch[pos] -= 1;
    return new String(ch);
}

总结

在BFS中需要避免重复的访问相同节点，灵活的运用队列这一数据结构。另外还有一种更高效的方法「双向BFS」，在知道目标的前提下，目标与初始点同时移动，如果他们的路径重叠了就说明能够找到目标，否则找不到目标。

申明：本博文是看了labuladong的算法小抄之后个人的理解以及总结。

本文地址：https://blog.csdn.net/yinhou1771/article/details/107369798