这段时间一直没有写刷题总结，因为发现BFS来处理问题会有些吃力。

从基础讲起，BFS（breath first search）宽度优先搜索。就是一层层的去遍历。

BFS的几个主要应用的地方：

1. 树的按层次遍历。

2. 图的按层次遍历。、

3. 数组按层次遍历。

对于这三个不同的应用，大概说一下解题的框架（大概思路）

1. 对于要按照层次遍历的问题，这个比较简单一些。

        a. 树中上一层节点和下一层节点之间是有向的，比如父亲节点会指向孩子节点。

        b. 因为有向，不会出现无向图那种指了一圈又指向自己的情况.

其大概的框架如下：

i. 初始化queue(按照层次遍历肯定得用queue)，比如把root push到queue里去初始化queue。

ii. 记录当前层元素个数，依次出队列。并同时把出队列元素的左右孩子进队列。

iii. 一层层的去遍历子孙，知道队列为空。

对于树中按照层次遍历的问题，解法框架固定。不必费脑子。

2. 对于图的按层次遍历

这些问题有些复杂，特别是无向图。要提前处理下数据。

1. 要提取出成每个元素的neighbors数据，然后才能一层层的遍历neighbor。

2. 要初始化queue，就得找到要初始化queue的数据。也就是最先要访问的数据，比如选课的题目中最先修的课程。

3. 用BFS 一层层的遍历neighbor，并且检查下之前是否已经访问过。无向图因为没有方向，A是B的邻居，同时B也是A的邻居。如果不去查重，会导致死循环的。

比如选课这道题目。有些课程必须先修完才能修后面的课。

像算法导论修完才能修高级算法或者高级数据库。

207. Course Schedule

框架如下：

1. 创建每个课程的后续课程

2. 创建每个课程的入度（前序课程）。

3. 初始化queue的元素为入度为0的课程（最先修的课程）

4. BFS 一层层的访问下个学期准备修的课程,。队列中一层访问完代表这个学期的课程修完了，把把前序课程指向的所有后续课程的入度减去1，代表下学期的课程中该前序课程已经修完了。

5。当该课程的入度为0，代表已经修完所有的前序课程。就能把该课程入队列，代表这学期开始修完这门课程了。

三，对坐标系/数组的层次遍历。

这样的题目也和图的遍历相似，举个例子， 比如2101. Detonate the Maximum Bombs

题目是某个炸弹如果爆炸，在爆炸范围内的所有雷都会爆炸。 那么就找出来一次性可以最多爆炸多少地雷。

步骤如下：

1. 找出每个地雷在爆炸范围内的其他地雷，也就是其后续地雷。

2. 现在就得考虑该把哪些地雷放到queue里，先引爆。

      因为不知道哪个地雷先引爆会点爆更多的地雷，所以只能一个个的尝试。

      不过也不能傻傻的每个都试一遍，当点了一个雷，在引爆范围内依次被爆的雷也被移除要尝试的雷的数组。这样要尝试的地雷数目就少了很多。

但是这道题目用BFS来做也有不好的一点，那就是查重。

unorder_set 或者unorder_map 不支持pair作为key。比如坐标点或者数组的位置都是x，y两个数据。

这一对数据用pair 封装好以后， 没法把pair最为key去申请hash。

这些问题最好用DP来做，这样就能把坐标位置记录下来。

代码如下

class Solution {
public:
    unordered_map<int, vector<int>> buildGraph(vector<vector<int>>& bombs)
    {
        unordered_map<int, vector<int>> graph;
        
        for(int i=0;i<bombs.size();i++){
            long ix= bombs[i][0];
            long iy= bombs[i][1];
            long ir= bombs[i][2];
            
            for(int j=0;j<bombs.size();j++){
                if(j == i)
                    continue;
                
                long jx= bombs[j][0];
                long jy= bombs[j][1];
                
                if( (jx-ix)*(jx-ix) + (jy-iy)*(jy-iy) <= ir*ir )
                    graph[i].push_back(j);
            }
        }
        
        return graph;
    }
    
    int detonateBombs(int start, unordered_map<int, vector<int>> neighbors)
    {
        int ret=1;
        queue<int> myqueue;
        unordered_set<int> bombed;
        
        bombed.insert(start);
        myqueue.push(start);
        
        while(!myqueue.empty()){
            int size = myqueue.size();
            
            for(int i=0;i<size;i++){
                int cur = myqueue.front();
                myqueue.pop();
                
                for(auto neighbor: neighbors[cur]){
                    if(bombed.find(neighbor) != bombed.end())
                        continue;
                    else {
                        myqueue.push(neighbor);
                        bombed.insert(neighbor);
                        ret++;
                    }
                }
            }
        }
        return ret;
    }
    
    int maximumDetonation(vector<vector<int>>& bombs) {
        // build a graph which bombs in the range of bombs A.
        // BFS each bombs to get all the other bombs.
        // go through all bombs as start bombs.
        
        unordered_map<int, vector<int>> graph = buildGraph(bombs);
        int maxBombs=0;
        int tmp=0;
        
        for(int start =0;start<bombs.size();start++) {
            tmp = detonateBombs(start, graph);
            if(tmp > maxBombs)
                maxBombs = tmp;
        }
        
        return maxBombs;
    }
};