Breadth-First Search

ปัญหา

คำถามหลายข้อเกี่ยวกับสิ่งที่เชื่อมกันอยู่ ถามหาจำนวนก้าวที่น้อยที่สุด: จำนวน hop ที่น้อยที่สุดระหว่าง router สองตัว ต้องแนะนำต่อกันกี่ทอดกว่าคนสองคนจะรู้จักกัน จำนวนครั้งที่น้อยที่สุดที่ต้องขยับเพื่อแก้ puzzle หรือทางที่สั้นที่สุดออกจากเขาวงกตที่ทุกทางเดินมีต้นทุนเท่ากัน แต่ละข้อคือ shortest path ในกราฟแบบ ไม่มี weight ที่ความยาวของ path คือจำนวน edge ของมัน

การไล่ตาม path ไปทีละเส้นตอบคำถามนี้ไม่ได้ จำนวน path โตเร็วมาก และ path แรกที่การค้นหาบังเอิญเจออาจยาว: ถ้าเดินแบบ depth-first บนกราฟในไดอะแกรมจาก A โดยเลือกเพื่อนบ้านตามลำดับตัวอักษร จะไปถึง H ครั้งแรกผ่าน A, B, E, F, H คือ 4 edge ทั้งที่ 3 ก็พอ ถ้าจะรู้ว่า path หนึ่งสั้นที่สุด การค้นหาต้องตัด path ที่สั้นกว่าทิ้งให้หมด และวิธีที่ง่ายที่สุดคือดูทุกอย่างที่ห่างไป 1 edge ก่อนอะไรก็ตามที่ห่างไป 2 edge

ทำงานยัง⁠ไง

BFS เก็บของไว้สามอย่าง: queue แบบ first-in, first-out ของ node ที่รอขยาย map dist ที่เก็บระยะห่างจากจุดเริ่มของแต่ละ node ที่เจอแล้ว และ map parent ที่เก็บเพื่อนบ้านที่เจอมัน

1. ใส่จุดเริ่มลงใน queue พร้อม dist[start] = 0
2. หยิบ node ที่อยู่หน้า queue ออกมา เพื่อนบ้านแต่ละตัวที่ยังไม่มี dist ให้ตั้ง dist เป็นมากกว่าของ node ปัจจุบันหนึ่ง จด node ปัจจุบันเป็น parent ของมัน แล้วต่อท้าย queue
3. ทำซ้ำจน queue ว่าง ตอนนี้ทุก node ที่ไปถึงได้จากจุดเริ่มจะมีทั้ง dist และ parent ส่วน node อื่นไม่มีสักอย่าง

บนกราฟในไดอะแกรม queue จะผ่านสถานะเหล่านี้ เริ่มจากตัวหน้า: A, B C, C D E, D E F, E F G, F G H, G H, H แล้วก็ว่าง ลำดับที่ node ออกจาก queue คือ A B C D E F G H ก็คือวง 0 แล้วตามด้วยวง 1, 2 และ 3

ทำไมครั้งแรกที่ไปถึงถึงสั้นที่สุด

queue มีแค่ node บางตัวที่ระยะ d ตามด้วยบางตัวที่ระยะ d + 1 เสมอ ไม่มีอย่างอื่น: แต่ละ node ที่เพิ่มเข้าไปห่างออกไปหนึ่งก้าวจาก node ที่กำลังขยาย และ node นั้นมีระยะน้อยที่สุดใน queue ทำให้ node ออกจาก queue ตามลำดับระยะ และทุก node ที่ระยะ d ถูกขยายก่อน node ไหนก็ตามที่ระยะ d + 1 พอ BFS ไปถึง node หนึ่งเป็นครั้งแรก มันไปถึงจากวงแรกสุดที่แตะ node นั้น เลยไม่มี path ที่ใช้ edge น้อยกว่านี้ ถ้ามี path แบบนั้น node นั้นก็ต้องถูกเจอจากวงก่อนหน้าไปแล้ว ในกราฟแบบไม่มีทิศทาง ผลที่ตามมาอีกข้อคือทุก edge เชื่อม node สองตัวที่ระยะต่างกันไม่เกินหนึ่ง ในไดอะแกรม E–F เชื่อม node สองตัวของวง 2 ส่วน edge อื่นทุกเส้นเชื่อมวงที่อยู่ติดกัน

จด node ตอนที่มันเข้า queue

map dist ทำหน้าที่เป็น visited set ไปด้วย และ BFS จด node ตอนที่ enqueue ไม่ใช่ตอน dequeue ในขั้นที่ 2 ตัว F กับ H ถูกเจอ (โดย C และโดย E) ตอนที่ยังรออยู่ใน queue พอ E ตรวจ F และ F ตรวจ H การตรวจก็ไม่ผ่านและไม่มีอะไรถูกเพิ่ม ถ้ารอจดจน node ออกจาก queue การตรวจทั้งสองครั้งจะเพิ่มสำเนาที่สองเข้าไป: บนกราฟนี้ queue จะรับ 10 entry แทน 8 และโตไปถึง 4 node แทน 3 และโดยทั่วไปมันอาจเก็บได้หนึ่ง entry ต่อ edge แทนที่จะเป็นหนึ่งต่อ node ถ้าไม่ตรวจเลย การค้นหาจะไม่มีวันจบ เพราะทุก edge แบบไม่มีทิศทางพากลับไปที่เดิมทันที: A ไป B แล้วกลับไป A

Path จาก parent link

parent ของ node คือ node ที่ตอนขยายแล้วเจอมัน parent link เลยประกอบกันเป็น tree ที่มีจุดเริ่มเป็น root เรียกว่า BFS tree ไล่ตามมันย้อนกลับจากเป้าหมายแล้วกลับลำดับผลลัพธ์ ก็จะได้ shortest path: H ← E ← B ← A กลายเป็น A → B → E → H เหมือนในขั้นที่ 3 โดยใช้หนึ่งก้าวต่อหนึ่ง edge ของ path

ถ้ามี shortest path หลายเส้นที่ยาวเท่ากัน BFS จะเก็บเส้นที่เจอก่อน และนั่นขึ้นกับลำดับของ adjacency list ตัว path A → C → F → H ก็มี 3 edge เหมือนกัน แต่ B อยู่ก่อน C ในรายการ ทำให้ E ลูกของ B ถูก dequeue ก่อน F ลูกของ C และไปถึง H ก่อน ถ้าจะนับหรือแสดงทุก shortest path ให้จดเพื่อนบ้าน u ทุกตัวที่ dist[u] == dist[v] - 1 เป็น parent แทนที่จะจดแค่ตัวแรก

Adjacency list, matrix และ O(V + E)

ถ้าใช้ adjacency list แต่ละ node ที่ไปถึงได้ถูก enqueue และ dequeue ครั้งเดียว และ list ของมันถูกอ่านครั้งเดียว การรันหนึ่งรอบเลยใช้ V dequeue บวกหนึ่งการตรวจต่อหนึ่ง entry ใน list: 2E ครั้งในกราฟแบบไม่มีทิศทาง และ E ครั้งในกราฟแบบมีทิศทาง การรันในไดอะแกรม dequeue 8 ครั้งและตรวจ 18 ครั้งสำหรับ 9 edge ถ้าใช้ adjacency matrix การหาเพื่อนบ้านของ node หนึ่งต้องสแกนแถวที่มี V ช่อง BFS เลยใช้ O(V²) ไม่ว่าจะมี edge น้อยแค่ไหน แบบนี้ใช้ได้กับกราฟเล็กที่หนาแน่น แต่เปลืองกับกราฟใหญ่ที่เบาบางอย่างแผนที่ถนน เครือข่าย และ social graph ที่ปกติเป็นแบบนั้น คือแต่ละ node มีเพื่อนบ้านแค่ไม่กี่ตัวหรือไม่กี่ร้อยตัวจาก node หลายล้านตัว

Grid และกราฟแบบ implicit

กราฟไม่ต้องมีอยู่จริงเป็นโครงสร้างข้อมูล เขาวงกตหรือแผนที่เกมคือ grid ที่ช่องเป็น node และการเดินไปช่องข้าง ๆ ที่ว่างอยู่เป็น edge ส่วน test ด้านล่างก็รัน bfs ตัวเดิมบนเขาวงกตเล็ก ๆ Flood fill หรือถังสีของโปรแกรมแต่งรูป ก็คือการค้นหาไปตาม pixel ข้าง ๆ ที่สีเดียวกัน Word ladder ที่เปลี่ยนตัวอักษรทีละตัวและต้องได้คำที่มีจริงทุกก้าว ก็คือ BFS บนคำ และ sliding puzzle ก็คือ BFS บนตำแหน่งของกระดาน โดยมีหนึ่ง edge ต่อการเดินที่ถูกกติกาหนึ่งแบบ ตรงนี้เพื่อนบ้านถูกสร้างขึ้นตอนนั้นเลย และ visited set ที่เป็น hash set ของ state (ดู Hash Table) ก็มักเป็นโครงสร้างที่ใหญ่ที่สุดใน memory

รูปแบบอื่น ๆ

• Multi-source BFS เริ่มด้วยหลาย node ใน queue ที่ระยะ 0 และให้ระยะไปถึงจุดเริ่มที่ ใกล้ที่สุด กับทุก node: ทางออกที่ใกล้ที่สุดจากทุกช่องของแผนที่ หรือคลังสินค้าที่ใกล้ที่สุดของทุกเมือง bfs_layers ของ NetworkX รับ list ของจุดเริ่มเพื่อการนี้
• 0-1 BFS รับมือกับ edge ที่ต้นทุนเป็น 0 หรือ 1 ด้วย deque: เพื่อนบ้านที่ข้าม edge 0 ไปอยู่หน้า และตัวที่ข้าม edge 1 ไปอยู่ท้าย deque เลยยังเรียงตามระยะ และ shortest path แบบมี weight ก็ยังใช้ O(V + E) โดยไม่ต้องใช้ priority queue และ node หนึ่งอาจถูก push อีกครั้งถ้าเจอทางไปหามันที่ถูกกว่า
• Bidirectional BFS ค้นหาจากจุดเริ่มและจากเป้าหมายพร้อมกัน แล้วหยุดเมื่อ frontier สองฝั่งมาเจอกัน ถ้าแต่ละ node มีเพื่อนบ้านราว b ตัวและเป้าหมายอยู่ห่างไป d edge แต่ละฝั่งจะลึกไปแค่ราว d/2: ประมาณ 2·b^(d/2) node แทนที่จะเป็น b^d
• Depth-limited BFS หยุดหลังจากจำนวน hop ที่กำหนด: ทุกคนที่อยู่ในระยะสอง hop ทุกหน้าที่อยู่ในระยะสามคลิก bfs_edges ของ NetworkX รับ depth_limit

Component, การระบายสองสี และ tree

• Connected component: รัน BFS จากทุก node ที่ยังไม่ถูก visit แต่ละรอบจะจด component หนึ่งอัน และทุกรอบรวมกันใช้ O(V + E)
• ตรวจ bipartite: ระบายสีแต่ละ node ตามว่าระยะของมันเป็นเลขคู่หรือคี่ กราฟจะแบ่งเป็นสองฝั่งที่ทุก edge ข้ามระหว่างฝั่ง ก็ต่อเมื่อไม่มี edge ไหนเชื่อม node สองตัวในวงเดียวกัน ในไดอะแกรม E กับ F อยู่ที่ระยะ 2 ทั้งคู่และมี edge ร่วมกัน edge นี้ปิด cycle 5 edge คือ A, B, E, F, C กราฟนี้เลยไม่ใช่ bipartite
• Level-order traversal: ใน tree การทำ BFS จาก root จะ visit node ทีละชั้น และไม่ต้องใช้ visited set เพราะแต่ละ node มี parent แค่ตัวเดียว ใช้พิมพ์ tree ทีละชั้น และหา node ที่ตื้นที่สุดที่ผ่านเงื่อนไข เหมือนในตาราง traversal ของ Binary Search Tree ส่วน Binary Heap ก็เก็บ tree ของมันไว้ใน array ตามลำดับนี้พอดี

มาจากไหน

Konrad Zuse เขียนวิธีนี้ไว้ในปี 1945 ในต้นฉบับเรื่องภาษาโปรแกรม Plankalkül: เป็นโปรแกรมที่รับกราฟเป็น list ของคู่ ประมวลผลจุดต่าง ๆ ตามลำดับที่เจอ และต่อจุดที่เพิ่งไปถึงไว้ท้าย list เพื่อแบ่งกราฟเป็นกลุ่มที่เชื่อมกัน ต้นฉบับนี้ไม่ได้ตีพิมพ์จนถึงปี 1972 ต่อมา Edward F. Moore ค้นพบแนวคิดนี้อีกครั้งเพื่อหาทางที่สั้นที่สุดผ่านเขาวงกต ตีพิมพ์ในปี 1959 และ C. Y. Lee ใช้มันในปี 1961 เพื่อเดินสายไฟ: router ของเขาติดป้ายช่องใน grid เป็นระยะห่าง ไล่ออกไปจากจุดเริ่มเป็นคลื่นของตัวเลขที่เพิ่มขึ้น แล้วไล่ path ย้อนกลับจากเป้าหมายตามป้ายที่ลดลง

โค้ด

from collections import deque


def bfs(graph, start):
    """Fewest-edge distances and parent links from start.

    graph maps each node to a list of its neighbours.
    Returns (dist, parent) for every node reachable from start.
    """
    dist, parent = {start: 0}, {start: None}
    queue = deque([start])
    while queue:
        u = queue.popleft()                    # the oldest waiting node
        for v in graph[u]:
            if v not in dist:                  # mark when queued, so v joins only once
                dist[v] = dist[u] + 1
                parent[v] = u
                queue.append(v)
    return dist, parent


def path(parent, target):
    """The start-to-target path, read from parent links (empty if unreachable)."""
    if target not in parent:
        return []
    nodes = []
    while target is not None:
        nodes.append(target)
        target = parent[target]
    return nodes[::-1]


graph = {'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B', 'G'],
         'E': ['B', 'F', 'H'], 'F': ['C', 'E', 'H'], 'G': ['D'], 'H': ['E', 'F']}
dist, parent = bfs(graph, 'A')
print(dist)
print(path(parent, 'H'))
# {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 2, 'G': 3, 'H': 3}
# ['A', 'B', 'E', 'H']

queue เป็น collections.deque เพราะ popleft() ใช้เวลาคงที่ ส่วน list.pop(0) ต้องเลื่อนทุกตัวที่เหลือและใช้ O(n) ส่วน dictionary dist ยังจดลำดับการ visit ไว้ด้วย เพราะ dictionary ของ Python เก็บลำดับการใส่ไว้: list(dist) คือ A ถึง H ตามลำดับในขั้นที่ 2 ส่วน test ตรวจระยะและ parent ทั้งหมดข้างบน กราฟที่ไม่เชื่อมกัน (node ที่ไปไม่ถึงไม่มี entry และได้ path ว่าง) node เดียวทั้งแบบมีและไม่มี self-loop กราฟแบบมีทิศทาง เขาวงกตแบบ grid ขนาด 4 × 8 ที่ทางออกอยู่ห่างไป 12 ก้าว และกราฟสุ่ม 400 อันที่มีไม่เกิน 14 node โดยที่ระยะทั้งหมดตรงกับอัลกอริทึม all-pairs ของ Floyd–Warshall

Complexity

เรื่อง stable และ in place ไม่เกี่ยวกับการค้นหาในกราฟ ระยะนับแค่ edge ถ้า edge มี weight ให้ใช้อัลกอริทึมของ Dijkstra หรือ 0-1 BFS ถ้าทุก weight เป็น 0 หรือ 1

ใช้ตอนไหนดี

• จำนวนก้าวที่น้อยที่สุดในกราฟที่ทุกก้าวมีต้นทุนเท่ากัน: hop ระหว่าง router หรือ service จำนวนทอดที่คนสองคนห่างกัน จำนวนครั้งที่น้อยที่สุดที่ต้องขยับใน puzzle หรือเกม เส้นทางข้าม grid ที่ทุกการเดินเท่ากัน
• ทุกอย่างที่อยู่ในระยะ k ก้าว: เพื่อนของเพื่อน หน้าที่อยู่ในระยะสามคลิกจากหน้าแรก service ที่อยู่ห่างไม่เกินสอง call จากตัวที่กำลังพัง
• งานที่ควรทำจากใกล้ไปไกล: การประมวลผล tree แบบ level-order การหา node ที่ใกล้ที่สุดที่ผ่านเงื่อนไข สัญญาณที่กระจายออกไปทีละรอบ
• Connected component และการระบายสองสี ที่ depth-first search ก็ทำได้ดีพอกัน
• ไม่เหมาะกับ shortest path แบบมี weight (นั่นคืออัลกอริทึมของ Dijkstra) และไม่เหมาะตอนที่กราฟกว้าง คำตอบอยู่ลึก และ memory มีน้อย: depth-first search เก็บแค่ path ปัจจุบัน

ได้อะไร เสียอะไร

• Memory ไปอยู่ที่ frontier BFS เก็บทุก node ที่เจอแล้วแต่ยังไม่ได้ขยาย ถ้าทุกคนมีเพื่อน 200 คน วงที่สองอาจมีได้ถึง 200² = 40,000 คน และวงที่สามได้ถึง 8,000,000 คน (ในความเป็นจริงน้อยกว่านั้น เพราะเพื่อนซ้อนกัน) และ visited set ก็โตตามไปด้วย depth-first search เก็บแค่ path ที่กำลังเดินอยู่ ส่วน iterative deepening (Richard Korf, 1985) รัน depth-first search ที่จำกัดไว้ที่ 1, 2, 3, … edge วิธีนี้หาความลึกที่ใช้ edge น้อยที่สุดได้เท่ากัน โดยใช้ memory แค่สำหรับ path เดียว แลกกับการทำชั้นตื้น ๆ ซ้ำ
• มันนับ edge ไม่ได้นับต้นทุน เวลาเดินทาง ราคา และ latency มองไม่เห็นในสายตาของมัน มันเลยคืนเส้นทาง 18 นาทีในขั้นที่ 4 อย่างมั่นใจ
• ตัวที่เสมอกันขึ้นกับลำดับใน adjacency list ถ้ามี shortest path หลายเส้น เส้นที่ BFS คืนมาขึ้นกับลำดับที่เพื่อนบ้านถูกแสดงไว้ ถ้าผลลัพธ์ต้องทำซ้ำได้เหมือนเดิม ก็ให้กำหนดลำดับนั้นให้ตายตัว
• Visited set ต้องใส่ memory ได้ ในกราฟแบบ implicit อย่างตำแหน่งของ puzzle หรือหน้าเว็บ มันเก็บทุก state ที่เคยเห็น และอาจโตจนใหญ่กว่า queue
• ไม่ต้องห่วงเรื่อง recursion BFS เป็น loop บน queue สาย node ที่ยาวมาก ๆ เลยไม่มีทางทำให้ call stack ล้น ต่างจาก depth-first search แบบ recursive (ดู Recursion)

ข้อควรรู้ตอนลงมือทำ

• Python: ใช้ collections.deque เอกสารของมันบอกว่าการต่อและ pop ที่ปลายไหนก็ได้ใช้ราว O(1) และเตือนว่า list.pop(0) ใช้ O(n) ส่วน NetworkX มี bfs_edges, bfs_tree, bfs_layers (หลายจุดเริ่มพร้อมกัน) และ shortest_path ที่ถ้าไม่ได้ให้ weight จะถอยไปใช้วิธีแบบไม่มี weight ของมัน คือ breadth-first search ส่วน bidirectional_shortest_path ค้นหาจากทั้งสองปลาย
• Graph database: คู่มือ Cypher ของ Neo4j บอกว่า SHORTEST และ shortestPath() หา shortest path ตามจำนวน hop โดยใช้ breadth-first search แบบสองทิศทางจากทั้งสองปลาย ถ้า planner คาดว่ามีจุดเริ่มหนึ่งจุดกับเป้าหมายหนึ่งจุด และใช้ BFS ทิศทางเดียวจากจุดเริ่ม ถ้ามีเป้าหมายได้หลายจุด สำหรับ shortest path แบบมี weight คู่มือชี้ไปที่ library Graph Data Science แทน ก็คือบทเรียนของขั้นที่ 4
• SQL: PostgreSQL ประเมิน recursive common table expression (WITH RECURSIVE) เป็นรอบ ๆ: แต่ละรอบรันส่วน recursive บน row ที่รอบก่อนหน้าสร้างขึ้น คือ working table ของมัน จนกว่าจะมีรอบที่ไม่เพิ่มอะไรเลย คล้ายกับ BFS ที่ขยายออกไปทีละวง ถ้าใช้ UNION แทน UNION ALL row ที่ซ้ำกับผลลัพธ์ก่อนหน้าจะถูกทิ้ง ก็คือ visited set สำหรับ row ส่วนตั้งแต่ PostgreSQL 14 เป็นต้นมา clause SEARCH BREADTH FIRST BY ตามมาตรฐาน SQL จะเพิ่ม column สำหรับเรียงผลลัพธ์ให้เป็นลำดับแบบ breadth-first (มันไม่ได้เปลี่ยนวิธีประเมิน query) และ CYCLE จะจด row ที่ปิด cycle
• Crawler: scheduler ตั้งต้นของ Scrapy เก็บ request ที่รออยู่ใน queue แบบ LIFO เลย crawl แบบ depth-first เอกสารของมันแสดงวิธี crawl แบบ breadth-first ด้วย DEPTH_PRIORITY = 1 และ queue แบบ FIFO และ duplicate filter ก็ทิ้ง request ที่เคยเห็นแล้ว ก็คือ visited set ช่วงต้นของการ crawl ลำดับทั้งสองแบบจะเบลอไปเพราะ request ที่ทำพร้อมกัน ส่วน Marc Najork กับ Janet Wiener crawl หน้าเว็บ 328 ล้านหน้าตามลำดับแบบ breadth-first และพบว่ามันไปถึงหน้าที่มี PageRank สูงได้เร็ว พอกระจายไปหลายเครื่อง frontier ก็กลายเป็น work queue ที่ใช้ร่วมกัน (Competing Consumers) และเมื่อมี worker หลายตัวดึงงานจากมันพร้อมกัน หน้าเว็บก็ออกมาตามลำดับ breadth-first แค่คร่าว ๆ
• Garbage collector: copying collector ของ C. J. Cheney ในปี 1970 คือ BFS บน object graph ที่ไม่ต้องใช้ queue แยก มัน copy object ที่ root ชี้อยู่ไปไว้ในพื้นที่ว่าง แล้วสแกนสำเนาไปตามลำดับ และ copy ทุก object ที่สำเนาชี้ไปและยังไม่ถูก copy ไปไว้ท้ายพื้นที่ ช่วงระหว่าง scan pointer กับท้ายพื้นที่มี object ที่ copy แล้วแต่ยังไม่ได้สแกนอยู่ ช่วงนี้ก็คือ queue ส่วน forwarding address ที่ทิ้งไว้ใน object เก่าแต่ละตัวก็คือเครื่องหมายว่า visit แล้ว
• Build tool: Maven ตัดสิน version ของ dependency ที่ขัดกันด้วย "nearest definition": version ที่อยู่ใกล้ project ที่สุดใน dependency tree ชนะ และถ้าลึกเท่ากัน ตัวที่ประกาศก่อนชนะ ก็คือ version ที่การเดินแบบ breadth-first บน tree เจอก่อน
• Benchmark: benchmark Graph 500 ที่เน้น supercomputing แบบใช้ข้อมูลหนัก จับเวลา breadth-first search บนกราฟใหญ่ที่สร้างขึ้นเป็น kernel หนึ่งของมัน และรายงานผลเป็น edge ที่ traverse ต่อวินาที (TEPS)