宽度优先搜索算法总结

• 在DSF和BSF之间，能用BSF尽量用BSF算法，因为DSF的递归算法使用到了栈，而栈的深度是有限制的，在python中的上限是1000，否则会导致栈溢出
• DSF主要借用栈来实现递归算法，而BSF则是使用队列来实现
• BSF尽量构建双端队列（deque）来实现算法目的，因为用queue会涉及多线程加锁导致变慢
• BSF使用的场景包括：连通块问题，层级遍历问题和拓扑排序问题
• BSF在初始化构建队列（deque）时，一定要绑定构建访问记录

BSF模版结构：
-1. 初始化队列（deque）和访问记录
-2.while循环访问队列+每次pop队列中一个节点+for循环访问的这个pop出节点的邻居节点
-3.判断节点邻居节点是否被访问
-4.若邻居节点未被访问，添加到队列中并将该邻居节点记录到访问记录中

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
BFS算法模版
"""
import collections

"""
# step1:初始化
# 注意：这个queue和标记永不分离，一旦进入队列，立刻要被标记已被访问
"""
queue = collections.deque() # 定义一个双端队列，保证每次加入队列的node会一个个出
distance = {node : 0} # 用来记录队列中的节点是否被访问

"""
# step2: 不断访问队列
# while循环+每次pop队列中的一个点出来
"""
while queue: # 如果队列没被访问完就继续访问
    node = queue.popleft() # 从队列的左边一个个提出来
    for neighbor in node.get_neighbor(): # 依次找到节点的邻居节点
        if neighbor in distance: # 如果这个邻居节点已被访问，则跳过
            continue
        # 注：同上，这里queue和标记永不分离，一旦进入队列，立刻要被标记已被访问，否则会有重复元素出现
        distance[neighbor] = distance[node] + 1 # 如果邻居节点没被访问，则记录到distance中，并加上访问消耗
        queue.append(neighbor) # 最后将没访问的邻居节点加入队列中，等待访问这个邻居节点


"""
#样例
"""
# ex1: cloneGraph
# 定义主函数
def cloneGraph(self, node):
    # step 1: find nodes
    nodes = self.find_nodes_by_bfs(node)
    # step 2: copy nodes
    mapping = self.copy_nodes(nodes)
    # step 3: copy edges
    self.copy_edges(nodes, mapping)

    return mapping[node]

def find_nodes_by_bfs(node):
    queue = collections.deque([node])
    visited = set([node])

    while queue:
        curt_node = queue.popleft()
        for neighor in curt_node.neighors:
            if neighbor in visited:
                continue
            visited.add(neighbor)
            queue.append(neighbor)
    return list(visited)

def copy_nodes(self, nodes):
    mapping = {}
    for node in nodes:
        mapping[node] = UndirectedGraphNode(node.label)
    return mapping

def copy_edges(self, nodes, mapping):
    for node in nodes:
        new_node = mapping[node]
        for neighbor in node.neighbors:
            new_neighbor = mapping(neighbor)
            new_node.neighbors.append(new_neighbor)

# ex2: Word Ladder
def ladderLength(self, start, end, dict):
    dict.add(end)
    queue = collections.deque([start])
    visited = set([start])

    distance = 0
    while queue:
        distance += 1
        size = len(queue)
        for i in range(size):
            word = queue.popleft()
            if word == end:
                return distance
            for next_word in self.get_next_words(word, dict):
                if next_word in visited:
                    continue
                visted.add(next_word)
                queue.append(next_word)
    return 0

def get_next_words(self, word, dict):
    next_words = []
    for i in range(len(word)):
        left, right = word[:i], word[i+1:]
        for char in 'abcdefghijklmnopqrstuvwxyz':
            if word[i] == char:
                continue
            new_word = left + char + right
            if new_word in dict:
                next_words.append(new_word)
    return next_words

# ex3: number of Islands
DIRECTIONS = [(1,0),(0,1),(0,-1),(-1,0)]

class Solution:
    def numIslands(self, grid):
        # 特殊情况处理
        if not grid or not grid[0]:
            return 0

        islands = 0
        visited = set()

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] and (i,j) not in visited:
                    self.bfs(grid, i, j, visited)
                    island += 1
        return islands

    def bfs(self, grid, i, j, visited):
        queue = collections.deque((x,y))
        visited.add((x,y))

        while queue:
            x, y = queue.popleft()
            for delta_x, delta_y in DIRECTIONS:
                next_x = x + delta_x
                next_y = y + delta_y
                if not self.is_valid(grid, next_x, next_y, visited):
                    continue
                visited.add((next_x, next_y))

    def is_valid(self, grid, x, y, visited):
        n, m = len(grid), len(grid[0])
        # 如果出界，返回False
        if not (0<= x <n and 0<= y <m):
            return False
        # 如果已经bsf过，不要再次bsf
        if (x,y) in visited:
            return False
        # 如果是1，为true，反之为false
        return grid[x][y]

# ex4: Knight shortest Path
OFFSETS =  [(-2,-1),(-2,1),(-1,2),(1,2),
            (2,1),(2,-1),(1,-2),(-1,-2)]
class Solution1:
    def shortestPath(self, grid, source, destination):
        queue = collections.deque(source.x, source.y)
        disToSrcMap = {(source.x, source.y): 0}

        while queue:
            x, y = queue.popleft()
            if (x, y) == (destination.x, destination.y):
                return disToSrcMap[(x,y)]
            for dx, dy in OFFSETS:
                next_x, next_y = x + dx, y + dy
                if not self.is_valid(next_x, next_y, grid):
                    continue
                if (next_x, next_y) in disToSrcMap:
                    continue
                queue.append((next_x, next_y))
                disToSrcMap[(next_x, next_y)] = disToSrcMap[(x,y)] + 1
        return -1

    def is_valid(self, x, y, grid):
        n, m = len(grid), len(grid[0])
        if x < 0 or x >= n or y <0 or y>=m:
            return False
        else:
            return True

# ex5: course schedule ii
def findOrder(self, numCourses, prerequisites):
    graph = [[] for i in range(numCourses)]

    # 1. 统计每个点的入度
    in_degree = [0] * numCourses
    for node_in, node_out in prerequisites:
        graph[node_out] = node_in
        in_degree[node_out] += 1

    # 2.每个入度为0的点放入队列作为起始点
    queue = collections.deque()
    for i in range(len(in_degree)):
        if in_degree[i] == 0:
            queue.append(i)
    # 记录已修课程
    num_choose = 0
    # 记录拓扑顺序
    topo_order = []

    # 3.顺序查找队列课程
    while queue:
        now_pos = queue.popleft()
        topo_order.append(now_pos)
        num_choose += 1
        for next_pos in graph[now_pos]:
            in_degree[next_pos] -= 1
            if in_degree[next_pos] == 0:
                queue.append(next_pos)
    return topo_order if num_choose == numCourses else []

# ex6: topological sorting
class Solution2:
    def topSort(self, graph):
        #1.统计每个点的入度
        node_to_indegree = self.get_indegree(graph)

        #2.将每个入度为0的点放入队列
        start_node = [x for x in graph if node_to_indegree[x] == 0]
        queue = collections.deque(start_node)
        # 记录拓扑顺序
        order = []

        #3. 不断从队列中拿出点
        while queue:
            node = queue.popleft()
            order.append(node)
            for neighbor in node.neighbors:
                node_to_indegree[neighbor] -= 1
                if node_to_indegree[neighbor] == 0:
                    queue.append(neighbor)

        return order

    def get_indegree(self, graph):
        node_to_indegree = {x:0 for x in graph}

        for node in graph:
            for neighbor in node.neighbors:
                node_to_indegree[neighbor] += 1
        return node_to_indegree