pylist

Breadth First Search

模板和要點

基本模板:BFS on tree

# Init
q = deque([root]) # 用作 queue
# loop
while q: # 当 q 不为空
    node = q.popleft() # 当前节点
    # 对当前节点进行操作
    # 遍历子节点:
        # append 到 q

要点


基本模板的变体

# Init
## 处理 root
q = deque([root]) # 用作 queue
# loop
while q: # 当 q 不为空
    node = q.popleft() # 当前节点
    # 遍历子节点:
        # 对当前子节点进行操作
        # append 到 q

要点


进阶 1,分层遍历

# Init
q = deque([root]) # 用作 queue
layer = 0 #!! 当前层 index
# loop
while q: # 当 q 不为空
    for _ in range(len(q)): #!! index `_` 不重要
        node = q.popleft() # 当前节点
        # 对当前节点进行操作
        # 遍历子节点:
            # append 到 q
    layer += 1 #!! 层 index 加一

要点


进阶 2,图上的 BFS,加入查重

# Init
q = deque([root]) # 用作 queue
qed = set(q) #!! 用于记录进入过 q 的节点
layer = 0 # 当前层 index
# loop
while q: # 当 q 不为空
    for _ in range(len(q)): # index `_` 不重要
        node = q.popleft() # 当前节点
        # 对当前节点进行操作
        # 遍历子节点:
            if 子节点 not in qed: #!! 之前是否进入过 q
                # append 到 q
                #!! add 到 qed
    layer += 1 # 层 index 加一

要点


进阶 3, Topology sorting

# 定义
graph = dict() #!! key: node label, value [label of neighbors dicts]
indegree = dict() #!! key: node label, value int indegree
# 初始化
q = deque([]) #!! 中包含所有indegree == 0 的 node
# BFS loop
while q: # 当 q 不为空
    node = q.popleft() # 当前节点
    # 对当前节点进行操作, 记述或者记录
    # 遍历子节点 nei:
        indegree[nei] -= 1 #!! 入度减一
        if indegree[nei] == 0: #!! 如果入度已经减为零
            q.append(nei) # append 到 q

要点

Examples

MISC