3. BFS - swchen1234/Algorithm GitHub Wiki

理论

• 几乎所有BFS都能用以下模板

from collections import deque
class Solution(object):
    def levelOrder(self, root):
        queue = deque([root])
        output = []
        if not root:
            return output
        visited = [] // maintain visited if the path can go back.
        while len(queue) > 0:
            sz = len(queue)
            temp = []
            for i in xrange(sz):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)                   
                temp.append(node.val)
            output.append(temp)

        return output

1. Tree Traversal

• 二叉树序列化 BFS/DFS 都可以实现
• 详见 Data Struture: Tree

2. Graph Traversal

• Graph BFS 和 Tree BFS的区别在于graph 可能多次访问某个node, 所以要hash visit.
• 详见 Data Struture: Graph

3. Others' Traversal

• 3.1 Color Print Problems

Problems

1. Tree BFS

2. Graph/Matrix BFS

2.1 小岛题

• dfs, bfs 都可以用 1）visited[]/set 记录已访问过的点 2）改变原矩阵已访问过的点的值，但需要最后改回来。

200. Number of IslandsTraverse all nodes, when meet island, add cnt by one and paint all adjacent islands to zero. continue Traverse.\

934. Shortest Bridge先用dfs/bfs找到一个岛，放入s1中（或改变原来的值为2), 再用bfs, 找到连到1的且不再s1中的最短路径。\

130. Surrounded Regions染色题，Set all regions connected to the boarder to some temporary variables（或加入set中）, then mark all remaining 0 to x, then turned the temporary ones back to 0.\

542. 01 Matrix 从每个0开始bfs， O（mn). The issue with bfs from 1 is that the constraints state that the matrix could have up to 10,000 cells. Think about a matrix where the entire matrix is 1 except for one of the corners. We would need to perform O(size) BFS, with each BFS costing up to O(size).
1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix用bit来将grid 放入queue中，bit[i*m+j]=grid[i][j]，这样就化为了一般的bfs题\

547. Number of Provinces类似200.
323. Number of Connected Components in an Undirected Graph类似200.\

1905. Count Sub Islands一定要遍历所有可能值之后再返回True/False\

2.2 病毒蔓延题

994. Rotting Oranges将坏掉的橘子加入q， 每步传染周围的橘子，直至坏橘子数==橘子总数\

2.3 染色题

785. Is Graph Bipartite?用color[]数组记录以访问点的颜色，bfs/dfs均可。注意因为可能存在整个图有几个互补相交的连通图组成，所以需要遍历每个点,若未染色，则bfs/dfs\

3. Others' BFS

279. Perfect Squares以由平方数组成的数作为q的节点，找到所有小于n的平方数，加入q，每次pop出一个，加上每个可能的平方数，直至=n。
1999. Smallest Greater Multiple Made of Two Digitsqueue = [d1, d2], 每次temp = q.popleft()后，若不符合条件， temp*10+d1或d2加入pop中\

721. Accounts Merge已email为status, 建立adjust graph, bfs; union-find时间复杂度一样，但bfs更方便\

950. Reveal Cards In Increasing Order用queue模拟deck 出现的index顺序（e.g. 对于7张牌， Order of indexes revealed: 0, 2, 4, 6, 3, 1, 5), 于是只需将deck排序后，将值依次赋值给revealed order即可
1298. Maximum Candies You Can Get from Boxesjust follow的rule,当没有发现新盒子新钥匙时停止，O（b+k)\