Algorithm Notes: BFS

### 1. 单队列的实现方式：
 
"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
 
class Solution:
    """
    @param root: A Tree
    @return: Level order a list of lists of integer
    """
    def levelOrder(self, root):
        # write your code here
        if not root:
            return []
        # step 1. 把第一层的节点 防盗队列当中
        queue = collections.deque([root])
        res = []
        # step 2. while 队列非空
        while queue:
            level = []
            # step 3 把上一层的节点，拓展出下一层的节
            for _ in range(len(queue)):
                ### pop the first in the queue in current level
                node = queue.popleft()
                ### update this node val in the level list
                level.append(node.val)
                ### find children in left and right, if any append to the tail of teh queue
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                    
            res.append(level)
            
        return res
 

### 双队列的实现方式：
 
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root):
        ### two queue (two lists)
        if not root:
            return []
        ### use list for queue and next_queue
        queue = [root]
        res = []
        while queue:
            ### start a new next_queue
            next_queue = []
            res.append([node.val for node in queue])
            for node in queue:
                if node.left:
                    next_queue.append(node.left)
                if node.right:
                    next_queue.append(node.right)
            ### next_queue is now queue
            queue = next_queue
                    
        return res

### Dummy Node 的实现方式：
 
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root):
        ### DummyNode
        ### use a Dummy Node in the queue to represent the end of the level:
        
        if not root:
            return []
        ### 这里要初始化的时候就带上末尾的dummy node
        queue = collections.deque([root, None])
        res, level = [],[]
        
        ### 使用dummy node只需要pop就好
        while queue:
            node = queue.popleft()
            ### 如果当前node是dummy node，说明这一层已经pop完
            if node is None:
                ### 更新level到res里
                res.append(level)
                ### reset level
                level = []
                ### 如果queue里还有node，说明还有下一层
                if queue:
                    ### 那么需要更新下一层的尾巴，加上dummy node
                    queue.append(None)
                ### 这里需要跳过，因为更新到了下一层了
                continue
            ### 如果当前node不是dummy node
            ### 更新 level
            level.append(node.val)
            ### 把当前node的children加进queue
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        return res

def DirectedGraphNode:
def init(self, label):
self.label = label
self.neighbors = [] # a list of DirectedGraphNode's
...

# 假设nodes为节点标签的列表:
# 使用了Python中的dictionary comprehension语法
adjacency_list = {x:set() for x in nodes}
# 另一种写法
adjacency_list = {}
for x in nodes:
    adjacency_list[x] = set()

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""
 
class Solution:
    def cloneGraph(self, node):
        root = node
        if not node:
            return 
        ### BFS to transverse the graph and get all nodes:
        nodes = self.getNodes(root)
        ### mapping old with new nodes:
        ### mapping key old node, value: new Node
        mapping = {}
        for node in nodes:
            ### at the same time creating, the new node using Node() class, using the old node's val first.
            mapping[node] = Node(node.val)
        
        ### mapping, adding neighbors:
        for node in nodes:
            #get new node from mapped hashmap
            new_node = mapping[node]
            #get neighbor list from old node
            for neighbor in node.neighbors: #neignbor are nodes too, so we can find them from the mapping
                #find this neighbor in the mapped hashmap, where we used the old node key and get new node value. so mapping[old key] = new node
                new_neighbor = mapping[neighbor]
                #add this neighbor to the new_node's atrribute
                new_node.neighbors.append(new_neighbor)
        
        return mapping[root]
        
    def getNodes(self, node):
        queue = collections.deque([node])
        res = set()
        res.add(node)
        while queue:
            head = queue.popleft()
            for neighbor in head.neighbors:
                if neighbor not in res:
                    res.add(neighbor)
                    queue.append(neighbor)
        return res

 
DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
class Solution:
    """
    @param grid: a boolean 2D matrix
    @return: an integer
    """
    def numIslands(self, grid):
        # write your code here
        n = len(grid)
        if n == 0:
            return 0
        m = len(grid[0])
        if m == 0:
            return 0
 
        
        islands = 0
        visited = set()
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1 and (i, j) not in visited:
                    self.bfs(grid, i, j, visited)
                    islands += 1
                    
        return islands     
        
    def bfs(self, grid, x, y, visited):
        queue = collections.deque([(x, y)])
        visited.add((x, y))
        while queue:
            cur_x, cur_y = queue.popleft()
            for dx, dy in DIRECTIONS:
                next_x = cur_x + dx
                next_y = cur_y + dy
                if (next_x, next_y) in visited:
                    continue
                if not self.is_valid(grid, next_x, next_y):
                    continue
                queue.append((next_x, next_y))
                visited.add((next_x, next_y))
                
    
    def is_valid(self, grid, x, y):
        n, m = len(grid), len(grid[0])
        if x < 0 or x >= n or y < 0 or y >= m:
            return False
        return grid[x][y] == 1

"""
Definition for a Directed graph node
class DirectedGraphNode:
    def __init__(self, x):
        self.label = x
        self.neighbors = []
"""
 
 
class Solution:
    """
    @param: graph: A list of Directed graph node
    @return: Any topological order for the given graph.
    """
    def topSort(self, graph):
        # write your code here
        ### 利用hash统计in-degree of nodes
        
        inDegree = {}
        
        for node in graph:
            inDegree[node] = 0
            
        for node in graph:
            for neighbor in node.neighbors:
                inDegree[neighbor] += 1
        # bfs
        order = []
        start_nodes = [n for n in graph if inDegree[n] == 0]
        queue = collections.deque(start_nodes)
        while queue:
            node = queue.popleft()
            order.append(node)
            for neighbor in node.neighbors:
                inDegree[neighbor] -= 1
                if inDegree[neighbor] == 0:
                    queue.append(neighbor)
 
    
        return order
        
        
    def findHead(self, inDegree):
        for node, degree in inDegree.items():
            if degree == 0:
                return node
        return None
        

from heapq import heappush, heappop, heapify
 
class Solution:
    def alienOrder(self, words):
        graph = self.build_graph(words)
        return self.topological_sort(graph)
        
    def build_graph(self, words):
        # key is node, value is neighbors
        graph = {}
 
        # initialize graph
        for word in words:
            for c in word:
                if c not in graph:
                    graph[c] = set() 
 
        # add edges        
        n = len(words)
        for i in range(n - 1):
            for j in range(min(len(words[i]), len(words[i + 1]))):
                if words[i][j] != words[i + 1][j]:
                    if words[i + 1][j] not in graph[words[i][j]]:
                        graph[words[i][j]].add(words[i + 1][j])
                    break
            else:
                if len(words[i]) > len(words[i + 1]):
                    return ""
                
        return graph
 
    def topological_sort(self, graph):
        # before looking into this part of code
        # you should know how to use bfs algorithm to do topological sorting
        # if you don't know, please google it first or join us at 九章算法班.
        
        # initialize indegree 
        indegree = {
            node: 0
            for node in graph
        }
        
        # calculate indegree
        for node in graph:
            for neighbor in graph[node]:
                indegree[neighbor] = indegree[neighbor] + 1
        
        # use heapq instead of regular queue so that we can get the 
        # smallest lexicographical order
        queue = [node for node in graph if indegree[node] == 0]
        heapify(queue)
        
        # regular bfs algorithm to do topological sorting
        topo_order = ""
        while queue:
            node = heappop(queue)
            topo_order += node
            for neighbor in graph[node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    heappush(queue, neighbor)
            
        # if all nodes popped
        if len(topo_order) == len(graph):
            return topo_order
        
        return ""        

### 第一种二分搜索树的BFS：
 
class Solution:
    """
    @param nums: A set of numbers
    @return: A list of lists
    """
    def subsets(self, nums):
        # write your code here
        if not nums:
            return [[]]
        
        queue = [[]]
        index = 0
        while index < len(queue):
            subset = queue[index]
            index += 1
            for num in nums:
                if subset and subset[-1] >= num:
                    continue
                queue.append(subset + [num])
        
        return queue
 
 
### 第二种二分搜索树的BFS：
 
class Solution:
    """
    @param nums: A set of numbers
    @return: A list of lists
    """
    def subsets(self, nums):
        # write your code here
        if not nums:
            return [[]]
        
        queue = [[]]
        for num in sorted(nums):
            for i in range(len(queue)):
                subset = list(queue[i])
                subset.append(num)
                queue.append(subset)
        
        return queue

class Solution:
    """
    @param arr:  an array of non-negative integers
    @return: minimum number of elements
    """
    def minElements(self, arr):
        # write your code here
        n = len(arr)
        totalsum = sum(arr)
        halfsum = int(totalsum / 2)
        
        queue = [[]]
        index = 0
        while index < len(queue):
            subset = queue[index]
            curr_sum = sum(subset)
            index += 1
            ### 只需这里加上判断就好，因为是从小到大，无重复增加子集的长度的方法。
            if curr_sum > halfsum:
                return len(subset)
            for num in arr:
                if subset and subset[-1] >= num:
                    continue
                queue.append(subset + [num])
        return 0
 

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
 
 
class Solution:
    """
    @param root: An object of TreeNode, denote the root of the binary tree.
    This method will be invoked first, you should design your own algorithm 
    to serialize a binary tree which denote by a root node to a string which
    can be easily deserialized by your own "deserialize" method later.
    """
    def serialize(self, root):
        # write your code here
        if root is None:
            return ""
        
        queue = collections.deque([root])
        bfs_order = []
        while queue:
            node = queue.popleft()
            bfs_order.append(str(node.val) if node else "#")
            if node:
                queue.append(node.left)
                queue.append(node.right)
        return ','.join(bfs_order)
        
 
    """
    @param data: A string serialized by your serialize method.
    This method will be invoked second, the argument data is what exactly
    you serialized at method "serialize", that means the data is not given by
    system, it's given by your own serialize method. So the format of data is
    designed by yourself, and deserialize it here as you serialize it in 
    "serialize" method.
    """
    def deserialize(self, data):
        # write your code here
        if not data:
            return None
        
        vals = data.split(',')
        root = TreeNode(int(vals[0]))
        queue = [root]
        isLeftChild = True
        index = 0
        
        for val in vals[1:]:
            if val is not "#":
                node = TreeNode(int(val))
                if isLeftChild:
                    queue[index].left = node
                else:
                    queue[index].right = node
                queue.append(node)
            
            if not isLeftChild:
                index += 1
            isLeftChild = not isLeftChild
            
        return root

"""
Definition for a point.
class Point:
    def __init__(self, a=0, b=0):
        self.x = a
        self.y = b
"""
 
DIRECTIONS = (
    (1, 2),
    (-1, 2),
    (2, 1),
    (-2, 1),
    (-1, -2),
    (1, -2),
    (-2, -1),
    (2, -1),
)
 
 
class Solution:
    """
    @param grid: a chessboard included 0 (false) and 1 (true)
    @param source: a point
    @param destination: a point
    @return: the shortest path 
    """
    def shortestPath(self, grid, source, destination):
        if not grid or not grid[0]:
            return -1
            
        n, m = len(grid), len(grid[0])
        if grid[destination.x][destination.y]:
            return -1
        if n * m == 1:
            return 0
        if source.x == destination.x and source.y == destination.y:
            return 0
        
        forward_queue = collections.deque([(source.x, source.y)])
        forward_set = set([(source.x, source.y)])
 
        backward_queue = collections.deque([(destination.x, destination.y)])
        backward_set = set([(destination.x, destination.y)])
        
        distance = 0
        while forward_queue and backward_queue:
            distance += 1
            if self.extend_queue(forward_queue, forward_set, backward_set, grid):
                return distance
                
            distance += 1
            if self.extend_queue(backward_queue, backward_set, forward_set, grid):
                return distance
 
        return -1
                
    def extend_queue(self, queue, visited, opposite_visited, grid):
        for _ in range(len(queue)):
            x, y = queue.popleft()
            for dx, dy in DIRECTIONS:
                new_x, new_y = (x + dx, y + dy)
                if not self.is_valid(new_x, new_y, grid, visited):
                    continue
                if (new_x, new_y) in opposite_visited:
                    return True
                queue.append((new_x, new_y))
                visited.add((new_x, new_y))
                
        return False
        
    def is_valid(self, x, y, grid, visited):
        if x < 0 or x >= len(grid):
            return False
        if y < 0 or y >= len(grid[0]):
            return False
        if grid[x][y]:
            return False
        if (x, y) in visited:
            return False
        return True

FORWARD_DIRECTIONS = (
    (1, 2),
    (-1, 2),
    (2, 1),
    (-2, 1),
)
 
BACKWARD_DIRECTIONS = (
    (-1, -2),
    (1, -2),
    (-2, -1),
    (2, -1),
)
 
class Solution:
    def shortestPath2(self, grid):
        if not grid or not grid[0]:
            return -1
            
        n, m = len(grid), len(grid[0])
        if grid[n - 1][m - 1]:
            return -1
        if n * m == 1:
            return 0
            
        forward_queue = collections.deque([(0, 0)])
        forward_set = set([(0, 0)])
        backward_queue = collections.deque([(n - 1, m - 1)])
        backward_set = set([(n - 1, m - 1)])
        
        distance = 0
        while forward_queue and backward_queue:
            distance += 1
            if self.extend_queue(forward_queue, FORWARD_DIRECTIONS, forward_set, backward_set, grid):
                return distance
                
            distance += 1
            if self.extend_queue(backward_queue, BACKWARD_DIRECTIONS, backward_set, forward_set, grid):
                return distance
 
        return -1
                
    def extend_queue(self, queue, directions, visited, opposite_visited, grid):
        for _ in range(len(queue)):
            x, y = queue.popleft()
            for dx, dy in directions:
                new_x, new_y = (x + dx, y + dy)
                if not self.is_valid(new_x, new_y, grid, visited):
                    continue
                if (new_x, new_y) in opposite_visited:
                    return True
                queue.append((new_x, new_y))
                visited.add((new_x, new_y))
                
        return False
        
    def is_valid(self, x, y, grid, visited):
        if x < 0 or x >= len(grid):
            return False
        if y < 0 or y >= len(grid[0]):
            return False
        if grid[x][y]:
            return False
        if (x, y) in visited:
            return False
        return True

class Solution:
    """
    @param: start: a string
    @param: end: a string
    @param: dict: a set of string
    @return: An integer
    """
    def ladderLength(self, start, end, wordSet):
        if start == end:
            return 1
        
        wordSet.add(start)
        wordSet.add(end)
        graph = self.construct_graph(wordSet)
        
        forward_queue = collections.deque([start])
        forward_set = set([start])
        backward_queue = collections.deque([end])
        backward_set = set([end])
 
        distance = 1
        while forward_queue and backward_queue:
            distance += 1
            if self.extend_queue(graph, forward_queue, forward_set, backward_set):
                return distance
            distance += 1
            if self.extend_queue(graph, backward_queue, backward_set, forward_set):
                return distance
        
        return -1
        
    def extend_queue(self, graph, queue, visited, opposite_visited):
        for _ in range(len(queue)):
            word = queue.popleft()
            for next_word in graph[word]:
                if next_word in visited:
                    continue
                if next_word in opposite_visited:
                    return True
                queue.append(next_word)
                visited.add(next_word)
        return False
            
    def construct_graph(self, wordSet):
        graph = {}
        for word in wordSet:
            graph[word] = self.get_next_words(word, wordSet)
        return graph
    
    def get_next_words(self, word, wordSet):
        next_word_set = set()
        for i in range(len(word)):
            prefix = word[:i]
            suffix = word[i + 1:]
            chars = list('abcdefghijklmnopqrstuvwxyz')
            chars.remove(word[i])
            for char in chars:
                next_word = prefix + char + suffix
                if next_word in wordSet:
                    next_word_set.add(next_word)
        return next_word_set

class Solution:
    def findLadders(self, start, end, dict):
 
        from collections import defaultdict
        dict = set(dict)
        #将end添加进dict,防止结果为[]
        if end not in dict:
            return []
        res = []
        # 记录单词下一步能转到的单词
        next_word_dict = defaultdict(list)
        # 记录到start距离
        distance = {}
        distance[start] = 0
        
        # 暴力匹配,当前字符串修改一个字母后的新字符串存在于dict中
        def next_word(word):
            ans = []
            for i in range(len(word)):
                       #97=ord('a')，123=ord('z')+1  
                for j in range(97, 123):
                    tmp = word[:i] + chr(j) + word[i + 1:]
                    if tmp != word and tmp in dict:
                        ans.append(tmp)
            return ans
        # 求到start的距离
        def bfs():
            q = collections.deque()
            q.append(start)
            step = 0
            flag = False #标记是否找到结果
            while len(q) is not 0:
                step += 1
                n=len(q)
                for i in range(n):
                    word=q[0]
                    q.popleft()
                    for nextword in next_word(word):
                        next_word_dict[word].append(nextword)
                       #当下一跳是end时，就可以结束搜索
                        if nextword == end:
                            flag = True
                        #如果没被添加过，则进行添加
                        if nextword not in distance:
                            distance[nextword] = step
                            q.append(nextword)
                if flag:
                    break
        # 遍历所有从start到end的路径
        def dfs(tmp, step):
            if tmp[-1] == end:
                res.append(tmp)
                return
            for word in next_word_dict[tmp[-1]]:
                if distance[word] == step + 1:
                    dfs(tmp + [word], step + 1)
        #bfs搜start--end的最短路径           
        bfs()
        #dfs输出距离最短的路径
        dfs([start], 0)
        return res