Graphs — BFS (ลุยเป็นชั้น)

หมวดก่อนหน้าเราลุยลึกด้วย DFS มาแล้ว คราวนี้มารู้จักคู่หูของมันคือ BFS (Breadth-First Search) หรือการลุยเป็นชั้น แทนที่จะพุ่งลึกไปทางเดียวจนสุด BFS จะแผ่ออกไปทีละวงรอบตัว เหมือนคลื่นน้ำที่กระเพื่อมออกจากจุดที่โยนก้อนหินลงไป จุดนี้ทำให้ BFS เก่งเรื่องหา shortest path (ระยะทางสั้นที่สุด) เป็นพิเศษ

BFS ทำงานยังไง

BFS traverse (เดินไล่) graph โดยเยี่ยม node (โหนด) ที่อยู่ ใกล้ จุดเริ่มก่อน แล้วค่อยขยายไปไกลขึ้นทีละชั้น ชั้นแรกคือเพื่อนบ้าน (neighbor) ตรงของจุดเริ่ม (ห่าง 1 ก้าว) ชั้นถัดไปคือเพื่อนบ้านของเพื่อนบ้าน (ห่าง 2 ก้าว) ไปเรื่อย ๆ เพราะมันแผ่ออกเป็นวงตามระยะทาง พอ BFS ไปถึงเป้าหมายครั้งแรก เรารับประกันได้เลยว่านั่นคือ shortest path (เส้นทางที่สั้นที่สุด, ก้าวน้อยที่สุด) นี่คือเหตุผลที่โจทย์แนว หาจำนวนก้าวน้อยสุด ระยะสั้นสุด เวลาน้อยสุด มักใช้ BFS

เครื่องมือคู่กับ BFS คือ queue (คิว) แบบเข้าก่อนออกก่อน เราใช้ deque จาก collections เพราะมัน pop (ดึง) ของจากหัว queue ได้เร็ว O(1) หลักการคือ push (ใส่) node ที่จะเริ่มลง queue แล้ว iterate (วน) pop ออกจากหัว queue มาประมวลผล พร้อม append (ต่อท้าย) เพื่อนบ้านที่ยังไม่ visited (เคยเยือน) เข้าท้าย queue ทำจน queue หมด และเหมือน DFS เราต้องมี visited กันเดินซ้ำเสมอ

from collections import deque

# template BFS บนกราฟ
def bfs(start, graph):
    queue = deque([start])
    visited = {start}              # ทำเครื่องหมายตั้งแต่ใส่คิว
    steps = 0
    while queue:
        # ดึงทั้งชั้นออกมาพร้อมกัน เพื่อนับจำนวนก้าว (ชั้น)
        for _ in range(len(queue)):
            node = queue.popleft() # ดึงจากหัวคิว
            # ... ทำอะไรกับ node ตรงนี้ ...
            for nxt in graph[node]:
                if nxt not in visited:
                    visited.add(nxt)   # ทำเครื่องหมายทันทีที่ใส่คิว
                    queue.append(nxt)  # โยนเข้าท้ายคิว
        steps += 1                 # จบหนึ่งชั้น = ขยับไปอีกหนึ่งก้าว

BFS บน grid สองมิติ

โจทย์ BFS เจอบ่อยมากในรูป grid (ตาราง) สองมิติ เช่นแผนที่ เขาวงกต ทุ่งนา เรามองแต่ละช่อง (r, c) เป็น node และช่องที่อยู่ติดกัน 4 ทิศ (บน ล่าง ซ้าย ขวา) เป็น neighbor โดยไม่ต้องสร้าง adjacency list (ลิสต์เพื่อนบ้าน) เลย แค่คำนวณพิกัด neighbor สด ๆ ตอนเดิน

# เพื่อนบ้าน 4 ทิศบน grid: บน ล่าง ซ้าย ขวา
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

rows, cols = len(grid), len(grid[0])
for dr, dc in directions:
    nr, nc = r + dr, c + dc
    # เช็คว่าไม่หลุดขอบตารางก่อนเสมอ
    if 0 <= nr < rows and 0 <= nc < cols:
        # ... ช่อง (nr, nc) เป็นเพื่อนบ้านที่ใช้ได้ ...
        pass

อีกเทคนิคที่หมวดนี้ใช้คือ multi-source BFS คือเริ่มจากหลายจุดพร้อมกัน แค่ push จุดเริ่มทุกจุดเข้า queue ตั้งแต่ต้น แล้ว BFS แผ่ออกพร้อมกันหมด เหมาะกับโจทย์ที่มีต้นตอลามหลายจุด เช่นไฟไหม้ หรือของเน่าที่ลามพร้อมกันหลายที่