一、BFS三个步骤：

• 1、将初始点（一个或多个）加入队列
• 2、从队列头取出点，判断初始点的周边点，将符合条件的点加入队列尾部
• 3、重复2操作，直至队列为空。while操作，(一般每个点只加入队列一次)

二、BFS的三个小栗子

遍历树，词梯问题（Word Ladder），被包围的岛屿（Surrounded Islands）

2.1、树

对于树，不需要判重，代码简单。

def bfs_tree(node):
    if node is None:
        return None
    else:
        queue = []
        #用list实现队列，左边是尾，右边是头。
        # 用insert方法把后入的元素插入最左边，入队尾部，用pop的方法弹出最右边
        #保证了先进先出的顺序
        queue.insert(0,node)
        #队列不为空，就继续执行循环
        while queue:
            cur = queue.pop()
            print(cur.val)
            #这里我定义的node的next属性，如果没有子节点，那么next就是空列表。
            for next in cur.nexts:
                queue.insert(0,next)

2.2、Word Ladder

对于图，就需要用一个hashSet判重了。这里的hashSet可以是set，也可是dict，但是不能是list！

2.2.1、为什么BFS找到的路线就是最短的----用图说明

对于一个词梯问题，在我们得到词的 集合以后，需要构造一个图。然后对图进行搜索操作。
参考以前写过的文章理解动态规划、BFS和DFS

引入Python的graph类，vertex类。这个类都有其属性。
用两种方法构造词梯的邻接表

• 一种是，对每个单词都和其余的所有单词做一次比较，满足词梯条件的对两个点用addedge方法添加一条边。但是时间复杂度过高。
• 一种， 效率比较高，词桶法。分两步。1、对于新来一个单词，我就先用这个单词的每个缺失一个字母，作为key，然后将满足条件的都添加到该桶中去。2、遍历完单词以后，对同一个桶中的单词进行操作，增加边。
  比如1、在遍历单词时遇到了pope这个单词，我先把ope,p_pe,po_e,pop作为4个key，然后把满足条件的都装到桶里去。再次遇到单词rope时，因为已经有_ope这个key了，就把rope放到桶中，不需要和别的每个单词再次进行比较了。2、接下来，对每个桶中的单词添加边，就会得到图了。

若是把上面的 图画出来，就是这样的：

用BFS进行搜索操作时，从fool到sage。首先，BFS会搜索与fool邻接的点[foul,foil,cool,pool]，在第二步，从foul搜索到foil时，发现foil已经存在于visited集合中了，说明有更短的路线可以从fool到foil（只要1步）。
这就说明，BFS找到的路线，一定是最短的。

2.2.2、LeetCode中的127，词梯问题

因为LeetCode中没有graph与vertex类，所以构造不了图。那怎样体现词与词之间的连词呢？比如上图中怎么去搜索fool相邻的四个词呢？

这里用三步去搜索：
1、对于fool的每个字母，
2、都用26个英文字母去替换，
3、再判断替换一个字母以后的单词，是不是存在于总的单词集合中。

比如对于fool，先对第一个字母 f 进行替换，从a到z，aool不存在于总单词集合中，cool，pool存在于总单词集合中，若是这个单词也不存在于visited中，那么就是有效的。

代码实现：

class Solution:
    def ladderLength(self, beginWord, endWord, wordList):

        if len(wordList) == 0:
            return 0
        if endWord not in wordList:
            return 0
        wordSet = set(wordList)
        word_len = len(beginWord)
        len_dict = {}
        len_dict[beginWord] = 1
        queue = []
        queue.insert(0,beginWord)

        while queue:
            cur_word = queue.pop()
            for i in range(word_len):
                for j in range(26):
                    alp = chr(j + ord('a'))
                    new_word = cur_word[0:i] +alp + cur_word[i+1:]
                    #若是等于目标单词，那就返回当前点的深度加1
                    if new_word == endWord:
                        return len_dict[cur_word] + 1
                    if new_word in wordSet and new_word not in len_dict:
                        queue.insert(0,new_word)
                        len_dict[new_word] = len_dict[cur_word] + 1
        #循环结束，仍是没有返回值，说明没有到达目标单词的路径，于是返回0
        return 0

注意这里用的是wordSet是一个集合，如果把visited的单词放到一个列表list中，因为Python中list的in方法时间复杂度很高，就会超时。

2.3、二维数组问题——LeetCode、200.Surrounded Islands

在上一篇文章中也讲过，对于数组问题，因为能够确定图的形状， 所以不一定非要用一个Set来保存已经搜索过的点。可以用一些小技巧，来更快速的实现。

比如这一题，先搜索数组的四条边界，可以把已经搜索过，下次遇到不会再进行搜索的“O”，替换成别的字母“+”，这样下次就不会再进行搜索了。

利用BFS把四条边的“O”都变成“+”以后，再把数组里面的被X包围的O都替换成X，再把“+”换回“O”，就能解决问题了。

需要注意，在Python中，set类型中，是不允许添加进list类型的元素的。
比如，set.add([i,j])就会出错，而set.add((i,j))就是正确的。在添加坐标时，需要注意这一点。

代码实现：

def solve(board):
    """
    :type board: List[List[str]]
    :rtype: void Do not return anything, modify board in-place instead.
    """

    ####
    #这里需要注意的是，因为采用的方式，是如果遇到O，就替换成+，
    # 因此不会存在再次遇到相同的O被访问的情况，因此不用添加visited了。
    #根那个词梯问题类似，不需要额外的visited，重要的不是这个集合，而是判断是否重复的步骤
    ####

    if len(board) == 0:
        return

    m = len(board)
    n = len(board[0])

    #定义一个bfs函数，传入点的索引i，j，
    #1、把满足条件的是’O‘的点都变成’+‘/2、并且将location添加进queue中
    #locat 是一个（i，j）元组，用以放入visited中的，因为list不能放入set中，元组能。
    def bfs(i,j):
        queue = []
        #如果locat的点是O,就变成+，并将locat添加进queue中

        if board[i][j] == 'O':
            board[i][j] = '+'
            queue.insert(0,(i,j))
        #若是该点不是’O，那这个函数就结束了。
        while queue:
            new_locat = queue.pop()
            i = new_locat[0]
            j = new_locat[1]
            #并对该点周围四个location判断是否有效且是‘O’，如果是，就变为‘+’，并且添加到queue中
            for i_new,j_new in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
                if i_new >= 0 and i_new <= m-1 and j_new >= 0 and j_new <= n-1 and \
                        board[i_new][j_new] == 'O':
                    board[i_new][j_new] = '+'
                    queue.insert(0,(i_new,j_new))

    #对四条边界的每个点，进行上述的bfs操作
    for i in range(m):
        #第一列
        bfs(i,0)
        print(board)
        #最后一列
        bfs(i,n-1)

    for i in range(n):
        #第一行
        bfs(0,i)
        #最后一行
        bfs(m-1,i)

    #四条边为O的都已经替换为+了，只需要把里面的被X包围的O替换成X，
    #把外面的没被包围的+还原为O，即可满足题意了
    for i in range(m):
        for j in range(n):
            if board[i][j] == 'O':
                board[i][j] = 'X'
            if board[i][j] == '+':
                board[i][j] = 'O'

print(solve([["O","O"],["O","O"]]))