宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

BFS，其英文全称是Breadth First Search。 BFS并不使用经验法则算法。从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实验里，其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中（例如队列或是链表），而被检验过的节点则被放置在被称为 closed 的容器中。（open-closed表）

一、灯泡开关 Ⅱ

672. 灯泡开关 Ⅱ


class Solution {
    Set<Integer> set;
    // 10 1010
    int TURN_EVEN = 0x2a;
    // 01 0101
    int TURN_ODD = 0x15;
    // 00 1001
    int TURN_3K_1 = 0x09;

    public int flipLights(int n, int presses) {
        // 因为二进制操作状态变换了，所以3盏还是6盏其实是一样的
        n = Math.min(n, 6);
        // 最多枚举4^4 = 256，对灯的操作用二进制操作，所以复杂度为O(1)
        // 这里可以改变dfs枚举方式或用二进制迭代枚举，枚举每个操作是否出现，变成2^4 = 16
        int m = Math.min(presses, 4);
        set = new HashSet<>();
        // 比如n=6，state = 11 1111
        int state = (1 << n) - 1;
        dfs(0, state, m, n);
        // print(set, n);
        return set.size();
    }

    void print(Set<Integer> set, int n) {
        for (int s : set) {
            for (int i = 31; i > 31 - n; i--) {
                System.out.print(((1 << i) & s) == 0 ? "0" : "1");
            }
            System.out.println();
        }
        System.out.println();
    }

    private void dfs(int i, int cur, int k, int n) {
        if (i == k) {
            // 去掉不合法的灯状态，保留末尾n栈灯的状态
            set.add(cur << (32 - n));
            return;
        }
        // 反转所有灯
        dfs(i + 1, ~cur, k, n);
        // 反转偶数位的灯, 异或 10 1010
        dfs(i + 1, cur ^ TURN_EVEN, k, n);
        // 反转奇数位的灯, 异或 01 0101
        dfs(i + 1, cur ^ TURN_ODD, k, n);
        // 反转3k+1的灯, 异或  00 1001, 1, 4
        dfs(i + 1, cur ^ TURN_3K_1, k, n);
    }
}

二、员工的重要性

690. 员工的重要性

/*
// Definition for Employee.
class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;
};
*/

class Solution {
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> map = new HashMap<Integer, Employee>();
        for (Employee employee : employees) {
            map.put(employee.id, employee);
        }
        int total = 0;
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(id);
        while (!queue.isEmpty()) {
            int curId = queue.poll();
            Employee employee = map.get(curId);
            total += employee.importance;
            List<Integer> subordinates = employee.subordinates;
            for (int subId : subordinates) {
                queue.offer(subId);
            }
        }
        return total;
    }
}

三、转化数字的最小运算数

2059. 转化数字的最小运算数

class Solution {
    public int minimumOperations(int[] nums, int start, int goal) {
        Deque<Integer> q = new LinkedList<>();
        q.offer(start);
        boolean[] visited = new boolean[1001];
        visited[start] = true;
        int step = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            step++;
            while (size-- > 0){//当前队列元素对应同一个step
                int poll = q.poll();
                for (int n : nums) {
                    for (int x : new int[]{poll - n, poll + n, poll ^ n}) {
                        if (x == goal) {
                            return step;
                        }
                        if (x >= 0 && x <= 1000 && !visited[x]) {
                            q.offer(x);
                            visited[x] = true;
                        }
                    }
                }
            }
        }
        return -1;
    }
}