Python 題目

PROBLEM

廣度優先搜尋 (BFS)

一題一題刷

概念

廣度優先搜尋是一種層級式的遍歷方式，會先訪問完同一層的所有節點，再訪問下一層。

程式碼實作

from collections import defaultdict, deque

def bfs(Tree, start_node):
    queue = deque([start_node])  # 使用 queue 儲存待訪問節點
    
    while queue:
        now_node = queue.popleft()  # 取出隊列最前面的節點
        print(now_node, end=" ")
        
        for next_node in Tree[now_node]:  # 將所有子節點加入隊列
            queue.append(next_node)

# 建立樹結構（與 DFS 相同）
tree = defaultdict(list)
root = ""

while True:
    try:
        st, *sts = input().split()
        if root == "":
            root = st
        tree[st].extend(sts)
    except:
        break

bfs(tree, root)

特點