所有代码详见：https://github.com/jingminglake/Leetcode
总体思路
BFS的特点是一层层的访问邻居，这样优点是可以最先找到距离起点最近的(边的权重是1)具有某种特征的目标点。
- 与DFS比较
例如求解无权图的最短距离时候，DFS是每次对一个邻居深入访问，这样在问题路径比较深的时候（也就是树比较高的时候），却存在路径没有解的情况，所以此时DFS求解最短路径慢，使用BFS优于DFS。
而对于走通的路径很多的情况下，也就是说解很多的时候，使用bfs和dfs是等价的，但是对于解少的情况来说，使用bfs更好。这也是为什么图中求最短路径都是使用BFS。
- 解包含多个答案
如果求解的答案不止一个，也就是要看具体层次所有结点的时候，那就需要在编码时候加入分层遍历的结构，也就是多一个for循环，for循环里面装的是若干结点，以无限大的矩阵从中心开始访问为例，一开始是1，第二层是4，第三层是8， 第4层是12。
BFS层次遍历的时候，要防止对之前一层访问过的点继续当作候选者访问。方法是先产生所有可能性，然后去除掉其中已经访问过的和不合法的，将剩余的作为候选者继续访问。 当然，像一些二叉树等的题目，由于点不会往回走，所以不需要考虑重复访问这种问题。
- 考虑遍历的起点对解题有帮助
BFS的题目需要考虑遍历的起点，例如找修建房子的问题，应该从空格和房子少的中的一个出发进行BFS。
- 数据结构使用
使用队列来保证先来先服务，有时候也需要使用优先级队列。有时候使用treeSet来替代优先级队列，时间复杂度是一样的。 如果是分层遍历结构，由于每一层内访问顺序是等价的，所以每层不一定需要用queue来装，可以使用hashSet来装。
- 时空复杂度
BFS的一般时间复杂度是O（V+E），V是结点数量，E是边的数量。因为在访问中，每个节点只会被访问一次，每个节点访问时候会考虑节点的边，由于不走回头路，所以每条边也是访问都是不超过两次的。
在来看边和节点的关系：对于无规律的图形，最坏情况下，每个点和其他点之间都有距离，也就是说从n个里面选两个点的情况数，也就是接近V的平方；对于矩阵，矩阵的顶点数为V，由于每个点与前后左右都有连接，所以我们知道即使每个点独占四个边，那充其量也就是4倍的V，况且每个点都和前后左右在共享边（至少和一个点贡献边），实际上边的数量上限就是2倍的V。
BFS的一般空间复杂度是O（V），需要队列，最坏情况下所有节点入队。
模板总结：bfs有可能出现邻居把自己当邻居又重新加入Queue的情况，在此，推荐所有的bfs使用入队列前先加标记的做法。
先加入队列的副作用是，使用额外数据结构记录每一层的结果的时候，最后一层加入的时候必然出现没有邻居的情况，因此额外数据结构为空，从而不计入总结果的情况。
具体题目
102.Binary Tree Level Order Traversal
题意：分层打印出二叉树。
解：此题使用BFS，要点是：1.使用分层遍历的宽搜，也就是要加一个for循环 2. 循环的size要先计算好 每一层queue构造出下一层的queue，当前queue的所有值一起处理。 时间、空间复杂度都是O（N）,N是二叉树结点数。
107.Binary Tree Level Order Traversal II
题意：此题和102题相同，不过要对102题的答案进行反转，
解：使用102题解法，每层计算完后进行反转操作，每次翻转消耗时间是O（s），s表示一层的数量，并不影响总时间复杂度。
261.Graph Valid Tree
题意：检测图是否为有效的树：（1）n个节点，n－1条边；（2）n的节点之间要连通。
解：遍历图，如果遍历的过程中，下一个将访问的节点如果是已经访问的节点，那么说明存在环，最终看遍历的节点数量，如果等于n，说明都遍历到了，也就是说图是连通的。
方法一：检查树性质。简单宽搜可以用于来检测连通，以及访问的数量，但是要检测环，还是要加入一些特殊的处理，一种方法是一开始检查边的数量，如果一开始不等于n-1，那么直接返回false，这种方法的缺点就是如果边信息可以重复，那么就不可取。
方法二：在建立的图结构中，从一条边经过之后，就立即把返回的边删除掉，这样如果还能遇到之前访问的节点，那只能说明有环；
方法三：本质也是不能回到之前的节点（注意：从0访问到1，然后1到0的时候应该直接过滤掉，而不能作为回到之前节点的情况），方法就是标记每个节点的访问来源，例如处理0的时候，把1放入queue，但是处理1的时候，简单宽搜不知道1是从哪里来的，因此会可能考虑0造成错误。
标记之后，把每个结点的来源直接过滤掉，如果还能走到之前的访问结点，那么就说明有环。
207. Course Schedule
题意：给出课程的先修条件，计算选课顺序。
解：此题是拓扑排序，拓扑排序可以使用BFS模板来解：需要一个vector来计算所有的点的入度，起始的所有点入度为0，然后找到起始点，进行bfs，访问完一个结点后将该点的邻居的入度减1，如果为0，那么加入队列。不用考虑重复，因为点的入度为0只可能发生一次。
拓扑排序是简单的，即使时间复杂度是O（n＋m），但是具体题目中，一定要想办法减少其中的循环次数，也要减少空间复杂度。循环次数的减少要靠精简的中间辅助的数据结构。
例如，此题可以建立邻接表，也就是一张hashmap（结点－>所有邻居的动态数组）。然后，在减少入度的时候，就可以对当前处理结点的所有邻居的入度减1。
总之，拓扑排序实现，主要需要： （1）一个indegree数组；（2）一个hashmap记录结点的所有邻居；
（3）使用queue处理，每次把入度为0的点去除，并计数，如果最后发现计数不等于结点总数，则存在环。如何知道入度为0的点？遍历当前点的所有的边，减小邻居结点的indegree数组，一旦等于0，就加入queue。这种做法是存在漏点的。正确做法是，一开始对所有的顶点，如果indegree等于0，就加入queue。
210. Course ScheduleII
此题和207一样，除了使用vector来保存拓扑排序的结果。
200. Number of Islands
题意：求岛屿数。解法有两个理解关键：
（1）矩阵的本质是图，每个格子是一个结点，每个格子有上下左右四个邻居（所以边长是格子的两倍）。
（2）BFS中由点及面的思想：灌水法，从一个点灌水，那么他连通的点也会有水，一直BFS，直到找到一个面。
解：对矩阵进行遍历，如果是1，那么将其连通的部分全部置为0，岛屿数目+1。
技巧一：使用坐标变换数组，能够优雅的进行for循环一个点的所有邻居。例如邻居是上下左右时候的坐标：vector<pair<int, int> > = {make_pair(1, 0), make_pair(0, 1), make_pair(-1, 0), make_pair(0, -1)};
注意的是全局的小变量，一定要记得及时清空，否则会产生内存错误。
694. Number of Distinct Islands
题意：在200题的基础上，求形状不同的岛屿的个数。
解：将岛屿定义成string型，岛屿存入集合来去重，其余和200题一样。 岛屿定义成每次灌水一个岛时候的路径。
注意：宽搜。为了防止例如（下右 右右和 下 右右右 不同），在每一层访问完后要加一个符号来隔开，这样下右#右右和下#右右就可以看出区别了。
另外的易错点：如果使用visited数组，那么访问的时候，不要忘记原来数组某个位置为1时候才访问。
711. Number of Distinct Islands II
题意：此题和694题不同之处在于岛屿旋转90，180，270，上下左右翻转镜像都是一个岛。
解：694题解法，加上对于岛屿集合的变形，有7种变形。 记录岛屿为坐标序列，首先对岛屿计算其7种变形得到8套坐标序列（例如按照（x，-y）来变换，作图可知，相当于逆时针旋转了90度，注意先不考虑坐标是否落在矩阵的外面），然后分别将8种序列内部分别按照从左到右，从上到下进行内部排序，然后将每一种的变形都减去原始坐标，得出相对位置信息，再将这种相对位置信息进行排序，将这种相对位置信息中最小的一个作为key来进行去重。 理解：8种位置，无论选什么位置作为基点，来计算其他7个位置的相对位置，最终的最小的相对位置一定还是一样的。
127. Word Ladder
题意：每次替换一个字母，一个单词可以进行变形，但是变形单词必须在给出的字典里面，求该单词变成目标单词的路径。
解：宽搜，宽搜中的下一层就是该单词替换一个字母后，在字典中存在的单词组成的集合。需要多维持一个已访问的集合字典，防止产生环(例如hit->hot->hit无限循环)。或者在访问后，从字典集合中去除该单词也可以。每访问一层，结果就多加1。在访问到目标单词时候（先要判断目标单词是在集合里），返回。
一个优化的方法：双向的宽搜，即从开始点和结束点两头开始考虑搜索（注意：并不是同时往里搜，而且此时不应该使用queue了，而是使用hashset），每次搜索时候，从少的一层作为开始（也就是要交换开始层和结束层）。然后只要在结束层的集合中找到目标，就可以返回了。
742. Closest Leaf in a Binary Tree
题意：找到二叉树中距离值为k的结点最近的叶子（二叉树每个结点值都不同，所以结果只有一个），最近是指路径最短。注意的是，路径可以经过父结点。
解：此题难点是考虑经过父结点的情况。解决方法是要将树当作图来看，先使用DFS找到该结点，期间使用hashmap保存走过结点的父节点（从根到该节点的路径），以便向回找。然后使用BFS一层层的找，下一层包括左右孩子、以及父节点，最先找到的叶子就是最短路径的叶子。BFS过程中要使用hashset来保证不会重复访问一个结点。
286. Walls and Gates
题意：给出矩阵图，矩阵中－1表示边界或者障碍，0表示门，INF表示空房间，现在要求所有空房间的最近的门，并将最近的距离作为结果填入房间。
解：此题容易想到bfs层序遍历。但是此题常规bfs遍历会超时。如果要节省时间，那么首先： （1）要从门出发，而不是从房间出发
（2）从多个门同时出发，遇到能走到的房间就立即把当前距离作为房间结果。这是因为不会出现因为下一次的访问而导致房间结果变更小。因为同时出发，而且是每一次走一步，那么每个房间必然会被最近的门走到。这也是从门出发的原因：可以并行的计算，而且从逻辑上减少了访问的次数。
（3）可以进一步优化，因为只需要在元素为INF时候才需要更新，所以不必使用bool数组来记录结点是否被访问。只要知道只要不是INT_MAX，那么不进入队列就行了。
542. 01 Matrix
题意：给出01矩阵，找出距离最近的1：对所有1找距离他最近0，并将距离替代值1，对于0来说，最近的就是自己。
解：此题和wallsAngGates一样，只不过此题使用bfs的时候，要先将全部的1修改为INT_MAX，不然就要使用额外空间了，这是因为bfs的时候，我们不知道什么时候应该更新当前的值。
529. Minesweeper
题意：扫雷游戏，给出当前棋盘状态和要点击的一个格子，返回下一个棋盘状态。
解：BFS。但是此题要考虑的情况比较复杂。 首先，判断点击的格子是不是雷，如果是雷，那么就改为X，然后返回；如果不是雷，是数字或者是一个打开的空格子，那么并不会影响棋盘变化，直接返回。而如果格子是一个未打开的格子E，那么以该格子为起点进行BFS。
对于BFS，首先，计算当前格子8个邻居中有几个雷，如果没有雷，说明本身应该被设置为打开空状态，并将所有未打开的邻居加入队列继续点击。如果有雷，那么将当前格子设置为雷的数量。
注意的是：BFS时候，如果队列弹出的元素后进行判断，那么其中有些坐标状态可能已经发生改变了，因此不能盲目的把他当作E来看了，否则会有大量重复。之所以一个坐标会被加入多次是因为没有使用额外空间标记每一个坐标。 建议采用入队列之前的检查，也就是说，如果不是要对周围进行展开（周围没有雷的情况），那么就根本不会入队。
675. Cut Off Trees for Golf Event
题意：二维矩阵中，0表示不能经过的障碍，1表示草地，比1大的数表示树，树和草地都可以通过(树可以不砍就通过)。现在要求从（0，0）开始，沿着树从低到高去砍树（树的高度是唯一的，不重复），将所有树砍完得出草地所要经历的最少路径。
解：宽度优先搜索，先将树按树高从小到大排序，并记录下对应坐标（例如先建立tuple，然后对tuple中字段排序），然后使用BFS求两两之间的距离（起点是0，0）。
只要其中一条路线找不到路径，那么就返回-1。否则结果就是线段和。
133. Clone Graph
题意：克隆一张图。图的数据结构是邻接表，一开始给出图中一个顶点。
解：由于图的数据结构是邻接表，且一开始只给出一个顶点，所以首先要找出所有的结点，并进行复制。难点在于边的复制。如何保存复制后的点？使用hash表，将旧结点映射到新结点。首先使用广度优先搜索或深度优先搜索，使用hash表保存复制的点，然后在根据邻接表来拷贝边。 先复制点，在复制边，分为三步：第一步：从一个点dfs出发找到所有点；第二步，复制所有点成新节点；第三步，复制所有边。 注意边界条件，看要拷贝的图是否为空。
PS. 使用邻接表时候，从一个点就可以知道整个图，这相当于树的根。
269. Alien Dictionary
题意：给出字典序的字符串单词数组，这些单词是按照新的字母优先级来规定的。现在让我们推测出其中的字母优先级规则，如果发现不合法，那么返回空。单词的长度不一定相等，其中pine的优先级比pineapple要靠前。
解：单词之间是有顺序的，里面蕴含的规律就是，如果相同字母开头的，就看第二个字母，也就是说，从左到右，两个单词第一个相同位置的不同字母就呈现出大小关系，至于后面的字母的优先关系就无法判断了。
我们首先从上往下，每次取相邻两个单词找规律（不考虑非相邻单词是因为信息不会因为没考虑而丢失，相邻单词的优先级信息会根据共同的字母传导到后面），然后根据共同的字母将信息连接起来，也就是形成了有向图，只需要进行拓扑排序，就可以求出整个的排列规则：使用unordered_map<char, set
PS.(1) indegree的计算不能在扫描单词的过程中进行，因为会出现大量重复，正确做法是先建好边集合和邻接表之后，在计算indegree数组。
(2) node结点要考虑所有的字母，只需要返回任意的拓扑序列都可以，哪怕只有一个单词，那么也可以返回这个单词的任意排序。
310. Minimum Height Trees
题意：给出一个树性质的无向图，其中每个结点都可以看作为root，现在求哪个结点作为root的树高最小（不止一个，列出所有作为结果）。
解：暴力求解，bfs适合求出最近距离类问题，以每个结点作为出发点进行bfs，复杂度是O(n^2)。
优化到O(N)解法：使用无向图的拓扑排序。把按层把所有的叶子剥除，剩余的最后一个或者两个结点时，停止剥除，剩余的就是结果。
无向图的拓扑排序：（1）找叶子 。由于无向图每个结点都有入度，所以叶子不是只出度为0的结点，而是入度和出度为1的节点，也就是只有一个邻居节点的节点。
（2） 按层(注意！)删除叶子，按层删除叶子，并不是每次删除完之后暴力循环找邻居只有一个的结点，这样做时间复杂度是O(N^2)的。 而是可以对删除的叶子结点进行保存，因为叶子结点的邻居结点由于失去了叶子这个邻居，它的邻居结点的个数也会发生变化，因此成为了候选者。通过“候选者”的这种思维，就可以把寻找某一个特征的由本来O（N）的时间变成了O（1）时间。
（3）使用队列存入接下来要处理叶子节点，每次删除叶子结点后先在邻接表中进行相应删除（在邻居结点的表里面删除自己），之后在看邻居的剩余的邻居个数，如果只有一个，那么就是下一层叶子结点，加入队列。
PS.bfs时候，如果使用层序方式，那么还可以求出高度，如果不需要求高度，那么可以不用层序方式。
417. Pacific Atlantic Water Flow
题意：给出矩阵，矩阵左上边界记做太平洋，右下边记做大西洋，现在求矩阵中能够流向两边大洋的点，流向规律是从大数字可以到小数字，反之不然。
解：此题如果是从每个点出发bfs看是不是能够到达两边，时间复杂度是O（N^2）。此题应该考虑从边框出发进行bfs才是优秀解题方案，好处是可以使用多个点（半个边框）作为起点，且只需要进行两遍bfs。每次bfs将能到达的点标记为能够到达，那么两边都同时能到达的点就满足了条件。 PS.此题的套路就是起点和终点的互换对解题带来帮助。
317. Shortest Distance from All Buildings
题意：二维矩阵，0表示空地，1表示建筑，2表示障碍物。现在要新建一个建筑，要求距离其他所有建筑距离和最短。求这样建筑的坐标，如果不存在这样的建筑，那么返回-1。
解：此题是使用bfs，而且知道大致思路是两种，一种是从所有空地依次出发，计算到达所有建筑的距离，看其中最小的距离和；另一种是从所有建筑物出发做bfs，看所有空地的距离和可以到达的建筑数，在扫描所有空地看其中最小的作为答案。第一种方式的时间复杂度为m * nlogn，m是空地的数量；第二种由于可以同时对所有建筑开始进行bfs，因此时间复杂度就是相当于一遍bfs，nlogn。 其中暗含的难点在于障碍物会导致有些建筑物之间是不连通的，这种情况下不存在这样的建筑点，是可以直接返回总结果-1的；另外还有一个很难考虑到的点，就是即使所有建筑都是连通的，那也不代表任何空地都和所有建筑连通，解决方法是对每一块土地设置计数器，如果从某个建筑出发可以到达它，那么计数器加1。
505. The Maze II
题意：Maze I只要求计算能否到达目标点，此题要求计算到达目标点最近走法的距离。
解：求最短路径一般都是使用bfs，但是此题不可。此题乍看起来像是无权图，但是实际上是带权值的图（因为球的特殊走法会导致点到点一步路径的距离实际上是大小不确定的距离）。
方法一：暴力解。使用简单的bfs，从起点开始bfs，并将走过的地方路径修改为距离自己最近的距离，如果某个点可以减少距离，那么继续加入队列进行访问，直到所有的点都无法更新为止，最后再看终点是否被更新过了，如果更新了，那么就知道终点是可达的。这种方法下，最坏情况下，每个点都要进入队列，且每个点最坏情况下，将在自己的两个维度上（横或者是竖），走上格子数遍。所以时间复杂度为O（mnmax（m，n））。
方法二：使用基于bfs迪杰斯特拉：使用dist数组，记录起始点到其他坐标的最短距离。然后，对当前点能到达的下一层，全部加入优先级队列，把最近能到的邻居弹出，然后对他进行下一层bfs。bfs过程中，如果当前结点距离起始点的距离小于起始点到父节点距离加本次走的距离的话，就不更新，否则更新。 理解：迪杰斯特拉是一种贪心算法，总思路就是分为两个集合S和U，集合S是已经计算出最短路径距离的点，集合U是尚未计算出最短路径距离的点，每次更新后把集合U里面距离原起点最小的点取出来放入S，因为它是贪心后计算出来的最优值。至于本题的实现，优先级队列弹出来的值其实就是每次贪心出来的最优值，只不过我们每次只是把可能给结果带来变化的点存入队列，因此不会出现重复弹出值的情况。因此最坏情况下，每个结点处理一遍，每次处理时候入出队列一次，时间复杂度是O(mnlog(m*n))。
444. Sequence Reconstruction
题意：给出org序列（一串不重复的数字），再给出seqs序列数组，看org序列是不是能由seqs中的序列唯一的构成。序列是需要考虑顺序的，也就是说，seqs必须覆盖org中所有的点和边。
解：方法一：使用拓扑排序。将seqs构成图，对该图进行拓扑排序，如果是每次走一个元素且顺序与org一致，那么说明是可以唯一构成。
方法二：按照定义来计算，有三个检查点：
（1）org里面所有的值需要在seqs里面存在。 使用hashset保存org节点，然后使用另一个hashset来保存遇到的seqs里面的节点，首先，如果扫描时候遇到非org节点，那么直接返回不能，之后就是在最后检查第二个hashSet的大小是否等于第一个。
（2）判断seqs中串是否顺序和org一致。 只需要把org中值到下标的映射首先计算出来，然后seq看当前关系对应下标是不是违反了下标先后顺序。
（3）判断覆盖原来的所有org的相邻边。 方法就是每当发现一个org相邻边，就把相邻边的第一个节点记录下来。使用hashset，加入检测到的相邻边的起点。这样，如果最后set的size等于n，那么就说明覆盖所有点。 第三点和第一点可以进行融合：发现所有的边，然后检查所有的点都是org里面的节点的时候，就可以了。
PS.要注意边界条件，当没有边关系存在的时候，或者为空的时候或者结点的值越界了，是需要直接返回false的。还有就是org是一个点，seq也都是一个点可能为真的情况。 另外拓扑排序时候，队列每次size只能为1，如果大于1，那么就说明有多条路径，就不行。 还有就是不能使用i到i+1的操作，因为i计算之前都要检测，而i+1在未检测的情况下被执行了。 corner case: (1) [1,2], [[1,2],[1,2]] -> true 解决方法是：将两个结点的多条边当作一条边。先去重。或者是将2当作两个结点，但是indegree中的2入度为2,然后1的邻居也有两个2，第二次访问的时候2的indegree被减为0，只发生一次。 (2) [1], [] -> false
297. Serialize and Deserialize Binary Tree
题意：序列化和反序列化二叉树。
解：序列化的要点： 序列化的信息需要保证是二叉树的一种唯一表达的形式。 需要深刻理解二叉树的唯一形式，也就是二叉树的空节点信息不能忽略，而要看作“#”。
方法一：把二叉树唯一形式根据先序遍历序列化。例如{1,2,3,null,null,4,5}序列化成{1 2 # # 3 4 # # 5 # #}。其中， 对二叉树结点以一个分隔符（空格）进行分割。
序列化：进行递归的前序遍历，遇到空结点，就使用“＃”代替，每个结点之间使用空格“ ”隔开。
反序列化：根据空格分隔来每次读入一个元素。每读一个元素，对后续元素递归处理它的左右孩子，相当于使用栈来处理，可以写成递归。
当作之前元素的左孩子，如果不能作为左孩子（也就是之前元素为空结点的情况），那么作为右孩子，然后继续处理未处理的节点。
方法二（推荐）：把二叉树唯一形式根据层序遍历序列化。{1,2,3,null,null,4,5}序列化成{1 2 3 # # 4 5 # # # #}。
序列化和反序列化都需要使用Queue结构。序列化处理完弹出的节点后，要把子节点(包括空结点)入队列，Queue的初始化就是把root放入；
反序列化的时候先按空格分割获取所有节点，以便一个个的访问提供输入；
然后使用Queue装树节点类型，初始化为第一个val构建的节点，作用是作为构建树的中间数据结构。
