# 廣度優先搜索 (BFS)

廣度優先搜索通常使用 Queue (佇列) 來實現

## 二元樹的廣度優先搜索

def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
        output = []
        if not root:
            return output
        queue = [root]
        while queue:
            length = len(queue)
            ans = []
            for i in range(length):
                node = queue.pop(0)
                ans.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            if ans:
                output.append(ans)
        return output

## 圖的廣度優先搜索

### 鄰接列表

graph = [[1,2,4],[0,3],[0],[1],[0,5],[4]]
visit = [0] * len(graph)
queue = [0]

while queue:
    node = queue.pop(0)
    visit[node] = True
    print(node)
    for neighbor in graph[node]:
        if not visit[neighbor]:
            queue.append(neighbor)