# BFS/DFS
(本篇以樹為主)

## 觀念
>edges = [ [0, 1], [0, 2], [1, 3], [1, 4],
[2, 5], [5, 6], [6, 7], [7, 2],# 形成一個循環
[4, 8], [8, 9]
]
#### 快速將節點建立字典

from collections import defaultdict

def build_graph(edges):
    graph = defaultdict(list) # 建立value為list的字典
    for u, v in edges:# u=0,v=1
        graph[u].append(v)
        graph[v].append(u) # 如果是無向圖
    return graph

> 輸出:defaultdict(<class 'list'>, {0: [1, 2], 1: [0, 3, 4], 2: [0, 5, 7], 3: [1], 4: [1, 8], 5: [2, 6], 6: [5...略

#### BFS
廣度優先遍歷

from collections import deque # 雙向佇列

def bfs(graph, start):# graph為字典
    visited = set() # 用集合避免無限循環
    q = deque([start])
    while q:
        node = q.popleft()
        if node in visited:
            continue
        visited.add(node)
        for neighbor in graph[node]:# 這個節點的鄰居 neighbor，都加入佇列 q，等待後續處理。
            q.append(neighbor)
    return visited

# 建樹
給定一個層序遍歷的 list `P=[1,null,2]`(一個只有右節點的樹)

from collections import deque

# 定義二元樹節點類別
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val # 根節點
        self.left = left
        self.right = right

## deque 建樹

# 從層序遍歷的 list 建立二元樹
def build_tree(li):
    if not li:
        return None

    root = TreeNode(li[0])
    q = deque([root]) # 初始放入根節點
    i = 1

    while i < len(li):
        node = q.popleft()

        # 確認有東西後再建立節點
        if i < len(li) and li[i] is not None:
            node.left = TreeNode(li[i])
            q.append(node.left)
        i += 1

        if i < len(li) and li[i] is not None:
            node.right = TreeNode(li[i])
            q.append(node.right)
        i += 1

    return root

## index 建樹
很快，不過只適用於「中間沒 None」或你保證 list 是完整對應的層序結構

def build_tree_index(li):
    if not li:
        return None
    nodes = [TreeNode(val) if val is not None else None for val in li]
    for i in range(len(li)):
        if nodes[i]:
            l = 2 * i + 1
            r = 2 * i + 2
            if l < len(li):
                nodes[i].left = nodes[l]
            if r < len(li):
                nodes[i].right = nodes[r]
    return nodes[0]

這時候`print(build_tree(p))` 會是`<__main__.TreeNode object at 0x0000014D6B029390>`
:::spoiler 要讓他變可視化要下面這段程式碼

def print_tree(root):
    if not root:
        return
    q = deque([root])
    while any(q):
        node = q.popleft()
        print(node.val if node else 'None', end=' ')
        if node:
            q.append(node.left)
            q.append(node.right)
       
print(print_tree(build_tree(p)))

:::
# BFS
呈上，用剛剛建的樹來跑一次BFS!

def bfs(start):
    queue = [start]
    result = []

    while queue:
        curr = queue.pop(0)
        result.append(curr.val)

        if curr.left:
            queue.append(curr.left)

        if curr.right:
            queue.append(curr.right)

    return result

#測試
result = bfs(build_tree(p))
print(result)

# DFS
深度優先

def dfs(node):
    if not node:
        return []
    
    result = [node.val]  # 先處理當前節點（Pre-order）
    result += dfs(node.left)  # 再處理左子樹
    result += dfs(node.right)  # 最後處理右子樹
    return result

#測試
result = dfs(build_tree(q))
print("dfs",result)

# 無向迷宮圖
1. 判斷要用dfs/bfs遍歷
2. 建立上下左右`[(-1,0),(1,0),(0,-1),(0,1)]` (i-1 = 往上一列)
3. 建立visited[]

:::spoiler 如果對角線也能走
directions = [(-1, 0), (1, 0), (0, -1), (0, 1),
(-1, -1), (-1, 1), (1, -1), (1, 1)]
:::
## 遍歷模板

for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
    nx = x + dx
    ny = y + dy
    # 接著你可以檢查 (nx, ny) 是否有效或是牆壁等

練習：https://hyc.eshachem.com/counting-rooms/