1.最常见的BFS算法结构

class Solution:
    def bfs(self, root):
        if not root:
            return  
            
        queue = list()
        queue.append(root)
        # 核心代码开始
        while queue:
            l = len(queue)
            for i in range(l):
                out = queue.pop(0)
                for child in out.children:
                    queue.append(child)

首先要明确，BFS的核心是【滚动组织最新一层的节点】

上面是我们最熟悉的BFS结构，通过维护一个队列，不断弹出结点并把下一层结点加入队列来实现整个BFS，每一层结点的组织方式在这里是【队列】

也许这种结构太习以为常了，于是算法思维就没能再打破一些条条框框，总是想着BFS就是搞个队列然后实现

今天刚好碰到两个BFS的问题，对【结点组织方式】有了一点思考

2.先说思考的结论

BFS中，结点是分层的，对每一层结点我们需要用一种数据结构把它们组织起来，最常见的就是上面的队列了。而队列的本质是什么，线性表。用线性表去组织每一层结点，非常自然。但是，线性表除了队列这样的顺序表，还有链表，链表同样可以拿来组织每层的结点。再进一步想，线性表可以组织每层结点，非线性的数据结构可以吗？当然是可以的，集合、哈希表都可以用来组织每一层的结点

线性结构和非线性结构组织每层结点的区别主要在于，线性结构可以天然保存结点的先后顺序，而当我们并不关心同层结点间的顺序而恰好有一些查找结点的需求，那么集合、哈希表这样的结构就派上用场了

每层结点组织方式：

• 线性
  • 队列、数组
  • 链表
• 非线性
  • set、hashtable

3.实战感受

3.1 链表组织每层结点

117. 填充每个节点的下一个右侧节点指针 II

给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL
初始状态下，所有 next 指针都被设置为 NULL
你只能使用常量级额外空间

分析：
这题用常规的层次遍历很好做，用队列组织每一层结点，然后按顺序调整next指针。但是要求空间复杂度O(1)，这就要想办法改造层次遍历了。根据题目要求，每层结点通过next指针相连形成链表，那我们就可以天然借助链表这个结构去访问和组织每一层的结点。核心就是，队列组织每层结点 -> 链表组织每层结点，但本质也还是一样的

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        cur = root
        while cur: # 从每层头节点cur开始遍历当前层，并链接下一层
            pointer = Node() # 用pointer走一遍来链接下一层
            most_left = pointer
            # 疯狂链接下一层
            while cur:
                if cur.left:
                    pointer.next = cur.left
                    pointer = pointer.next
                if cur.right:
                    pointer.next = cur.right
                    pointer = pointer.next
                cur = cur.next
            
            # cur指向链接好的下一层的最左节点
            cur = most_left.next
        return root

3.2 集合组织每层结点

127. 单词接龙

给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。

说明:
如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出: 5
解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
返回它的长度 5

分析：
每个单词看成一个节点，相差只有一个字母的单词都认为邻接，就抽象成一个无向图结构的问题。问题变成，无向图中寻找到从起点到终点的最短路径距离，后面就是BFS

因此，问题的关键实际上在于建图

• 1.建图。差距只有一个字母的单词之间形成无向边，使用hashtable邻接表把所有差距为1个字母的单词以list形式聚合起来，表示它们之间是邻接关系

如{'*it':['hit'], 'h*t':['hit','hot'], ...}

• 2.注意到起点和终点都给出了，因此可以优化成双向的BFS
• 3.双向BFS的结点组织方式-set。使用双向BFS，往往是图结点的相遇问题。两点各自逐层向外扩张，如同两个石头泛起的涟漪，当涟漪最外层相遇时，就对应最短距离。我们需要记录的是双方的最外层结点，并且判断两者是否存在交集，而层内结点的顺序并不重要。因此，这里使用set来组织每层结点，这样一来，判断A层某个结点是否在B层中，只需要O(1)的时间

class Solution(object):
    ###### 基于集合的双向BFS模式 ######
    def ladderLength(self, beginWord, endWord, wordList):
        if endWord not in wordList:
            return 0

        # 基于wordList建图，使用【同类表】形式。如{'*it':['hit'], 'h*t':['hit','hot'], ...}
        # 建立了图之后就是常规的bfs问题
        size, graph_dic = len(beginWord), defaultdict(list)
        for w in wordList:
            for _ in range(size):
                graph_dic[w[:_]+"*"+w[_+1:]].append(w)
        
        # 两个set的双向BFS
        s, s1 = set(), set()
        s.add(beginWord)
        s1.add(endWord)
        # 标记哪些单词已经访问
        mark_dic = defaultdict(bool)  # bool 的默认值是false，因此所有不在list里的是false
        mark_dic[beginWord] = True
        mark_dic[endWord] = True
        steps = 1
        while s and s1:
            # strick: 总是选择元素少的一方进行bfs扩散
            if len(s) > len(s1):
                s, s1 = s1, s
            
            # 用temp记录本轮s集合的bfs扩散结果
            temp = set()
            l = len(s)
            for _ in range(l):
                cur_word = s.pop() # 随机pop一个
                for i in range(size):               # 找邻居
                    for neighbour in graph_dic[cur_word[:i]+"*"+cur_word[i+1:]]:
                        # 如果从起点、终点扩散的两军前锋相遇，判断元素是否在集合中比判断是否在数组中更快
                        if neighbour in s1: 
                            return steps + 1
                        if not mark_dic[neighbour]:
                            mark_dic[neighbour] = True
                            temp.add(neighbour)  
            steps += 1
            s = s1
            s1 = temp
        return 0