BFS算法整理(python实现)

广度优先算法(Breadth-First-Search),简称BFS,是一种图形搜索演算算法。

1. 算法的应用场景

2. 算法的模板

2.1 针对树的BFS模板

  • 无需分层遍历
from collections import deque

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


def level_order_tree(root, result):
    if not root:
        return
    # 这里借助python的双向队列实现队列
    # 避免使用list.pop(0)出站的时间复杂度为O(n)
    queue = deque([root])

    while queue:
        node = queue.popleft()
        # do somethings
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result


if __name__ == "__main__":
    tree = TreeNode(4)
    tree.left = TreeNode(9)
    tree.right = TreeNode(0)
    tree.left.left = TreeNode(5)
    tree.left.right = TreeNode(1)

    print(level_order_tree(tree, []))
    # [4, 9, 0, 5, 1]
  • 需要分层遍历
def level_order_tree(root):
    if not root:
        return
    q = [root]
    while q:
        new_q = []
        for node in q:
            # do somethins with this layer nodes...
            # 判断左右子树
            if node.left:
                new_q.append(node.left)
            if node.right:
                new_q.append(node.right)
        # 记得将旧的队列替换成新的队列
        q = new_q
    # 最后return想要返回的东西
    return xxx

2.2 针对图的BFS

  • 无需分层遍历的图
from collections import deque
def bsf_graph(root):
    if not root:
        return
    # queue和seen为一对好基友,同时出现
    queue = deque([root])
    # seen避免图遍历过程中重复访问的情况,导致无法跳出循环
    seen = set([root])
    while queue:
        head = queue.popleft()
        # do somethings with the head node
        # 将head的邻居都添加进来
        for neighbor in head.neighbors:
            if neighbor not in seen:
                queue.append(neighbor)
                seen.add(neighbor)
    return xxx
  • 需要分层遍历的图
def bsf_graph(root):
    if not root:
        return 
    queue = [root]
    seen = set([root])
    while queue:
        new_queue = []
        for node in queue:
            # do somethins with the node
            for neighbor in node.neighbors:
                if neighbor not in seen:
                    new_queue.append(neighbor)
                    seen.add(neighbor)
    return xxx
            

2.3 拓扑排序

在图论中,由一个有向无环图的顶点组成的序列,当且仅当满足下列条件时,称为该图的一个拓扑排序(英语:Topological sorting)。

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

每个顶点出现且只出现一次;
若A在序列中排在B的前面,则在图中不存在从B到A的路径。
实际应用

  • 检测编译时的循环依赖
  • 制定有依赖关系的任务的执行顺序(例如课程表问题)

算法流程

  1. 统计所有点的入度,并初始化拓扑排序序列为空。
  2. 将所有入度为0的点,放到如BFS初始的搜索队列中。
  3. 将队列中的点一个一个释放出来,把访问其相邻的点,并把这些点的入度-1.
  4. 如何发现某个点的入度为0时,则把这个点加入到队列中。
  5. 当队列为空时,循环结束。

算法实现

class Solution():
    def top_sort(self, graph):
        node_to_indegree = self.get_indegree(graph)
        # 初始化拓扑排序序列为空
        order = []
        start_nodes = [node for node in graph if node_to_indegree[node] == 0]
        
        queue = collection.deque(start_nodes)
        while queue:
            head = queue.popleft()
            order.append(node)
            for neighbor in head.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
扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄