BFS就是廣度優(yōu)先算法，BFS相對(duì)DFS來(lái)說(shuō)不太直觀。BFS中，我們會(huì)搜索r的“孫子節(jié)點(diǎn)”之前先訪問(wèn)結(jié)點(diǎn)r的所有相鄰結(jié)點(diǎn)。一般用隊(duì)列+迭代方案實(shí)現(xiàn)。

為了復(fù)習(xí)下BFS的思想，看下BFS最基本的場(chǎng)景=。=
無(wú)向圖的BFS來(lái)舉栗子??
BFS是“地毯式”層層遞進(jìn)的搜索策略，先查找離起始頂點(diǎn)最近的，依次往外搜索。下圖表示了搜索的過(guò)程，盜一張大佬的圖。

其實(shí)思想不復(fù)雜，實(shí)現(xiàn)起來(lái)還是要琢磨一下的。

前面提到BFS要用隊(duì)列+迭代方案實(shí)現(xiàn)，那么我們需要三個(gè)輔助變量visited，queue，prev

visited：記錄以及訪問(wèn)過(guò)的頂點(diǎn)，避免頂點(diǎn)被重復(fù)訪問(wèn)
queue：關(guān)鍵的是這里，實(shí)現(xiàn)的是記錄功能，因?yàn)槭菍訉舆f進(jìn)，需要暫存訪問(wèn)過(guò)的頂點(diǎn)，方便進(jìn)行下一層搜索
prev:記錄搜索過(guò)的路徑，不過(guò)是反向存儲(chǔ)的，prev[w]存儲(chǔ)的是從哪個(gè)前驅(qū)頂點(diǎn)遍歷過(guò)來(lái)的。關(guān)注下print函數(shù)的實(shí)現(xiàn)。

talk is cheap，show you the code：

public class BFS {
    public int v;//頂點(diǎn)個(gè)數(shù)
    public LinkedList<Integer> adj[];// 鄰接表

    public BFS(int v) {
        this.v = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i) {
            adj[i] = new LinkedList<>();
        }
    }

    // 添加連接關(guān)系
    public void addEdge(int s, int t) {
        adj[s].add(t);
        adj[t].add(s);
    }

    // bfs搜索，s到t的路徑
    public void bfs(int s, int t) {
        // s，t是同一節(jié)點(diǎn)，返回
        if (s == t) {
            return;
        }

        //三大輔助變量---visited
        boolean[] visited = new boolean[v];

        // 三大輔助變量---queue
        Queue<Integer> queue = new LinkedList<>();

        // 加入s
        queue.add(s);

        // 三大輔助變量-- prev
        int[] prev = new int[v];

        // 初始化為-1
        for (int i = 0; i < v; ++i) {
            prev[i] = -1;
        }

        while (queue.size() != 0) {
            // 堆頂出隊(duì)
            int w = queue.poll();

            // 遍歷w的臨接節(jié)點(diǎn)
            for (int i = 0; i < adj[w].size(); ++i) {
                //和w相鄰的一個(gè)節(jié)點(diǎn)
                int q = adj[w].get(i);
                // 如果q沒(méi)有訪問(wèn)過(guò)
                if (!visited[q]) {
                    // 記錄prev，q的上前驅(qū)節(jié)點(diǎn)是w
                    prev[q] = w;
                    // 到終點(diǎn)了打印路徑
                    if (q == t) {
                        print(prev, s, t);
                        return;
                    }
                    // q訪問(wèn)過(guò)了，標(biāo)記
                    visited[q] = true;
                    // 將q加入隊(duì)列
                    queue.add(q);
                }
            }
        }

    }

    // 遞歸打印從終點(diǎn)t到起點(diǎn)的路徑
    private void print(int[] prev, int s, int t) {
        if (prev[t] != -1 && t != s) {
            print(prev, s, prev[t]);
        }
        System.out.print(t + " ");
    }
}

其實(shí)呢，要記住模板~編碼5分鐘，調(diào)試兩小時(shí)，再放一個(gè)方便記憶的模板，也方便手寫(xiě)??

void search(Node root) {
        Queue queue = new Queue();
        root.visited = true;
        visit(root);
        queue.add(root); // 加至隊(duì)列尾部
      
       while(!queue.isEmpty())  {
           Node r = queue.poll(); //從隊(duì)列頭部移除
           foreach(Node n in r.adjacent) {
                if(n.visited == false) {
                    visit(n);
                    n.visited = true;
                    queue.add(n);
                }
          }
      }
}

下面實(shí)操一下，看看LeetCode真題??

最短路徑的題，“地毯式搜索”，廣度優(yōu)先返回的就是最短路線

• visited數(shù)組，記錄訪問(wèn)過(guò)的數(shù)字，是從0到n
• queue 這里存放的挑選后剩余的總和n，以及已選數(shù)字的個(gè)數(shù)
• 滿足條件時(shí)，返回
• 用java寫(xiě)感覺(jué)有點(diǎn)啰嗦，=。=

    public int numSquares(int n) {
        if (n == 0) {
            return 0;
        }

        // 暫存隊(duì)列，每一種元素有剩余總數(shù)和已選元素個(gè)數(shù)組成
        Deque<ArrayList<Integer>> queue = new LinkedList<ArrayList<Integer>>();
        ArrayList list = new ArrayList(2);
        list.add(n);
        list.add(0);
        queue.add(list);

        boolean[] visited = new boolean[n + 1];
        visited[n] = true;

        while (!queue.isEmpty()) {
            ArrayList<Integer> temp = queue.removeFirst();
            int remain = temp.get(0);
            int step = temp.get(1);
            if(remain == 0) {
                return step;
            }
            for (int i = 1; remain - i * i >= 0; i++) {
                int a = remain - i * i;
                if (!visited[a]) {
                    if (a == 0) {
                        return step+1;
                    }
                    ArrayList tempList = new ArrayList(2);
                    tempList.add(a);
                    tempList.add(step + 1);
                    queue.addLast(tempList);
                    visited[a] = true;
                }

            }
        }
        return 0;
    }

再看一題：

根據(jù)題目的意思，就是要廣搜來(lái)遍歷對(duì)應(yīng)id的員工所有impance的值

• 使用了java 8的stream來(lái)篩選出對(duì)應(yīng)id的employee的信息

       public int getImportance(List<Employee> employees, int id) {
        int result = 0;
        Employee rootEmployee = new Employee();
        Queue<Employee> queue = new LinkedList<>();
        rootEmployee = getEmployeeById(employees, id);
        queue.offer(rootEmployee);
        while (!queue.isEmpty()) {
            Employee employee = queue.poll();
            result += employee.importance;
            for (Integer subordinate : employee.subordinates) {
                queue.offer(getEmployeeById(employees, subordinate));
            }
        }
        return result;

    }

    private Employee getEmployeeById(List<Employee> employees, int id) {
        return employees.stream().filter(employee -> employee.id == id).collect(Collectors.toList()).get(0);
    }