欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

宽度优先搜索算法(BSF)

程序员文章站 2022-05-20 20:17:27
...

宽度优先搜索算法总结

  • 在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
相关标签: 算法 数据结构