การค้นหาแบบความกว้างก่อน (BFS) คืออะไร?

Question

IT Interview Practice · Accepted Answer

**BFS** สำรวจกราฟทีละระดับ โดยเยี่ยมชมเพื่อนบ้านทั้งหมดของโหนดก่อนที่จะเดินไปลึก ใช้ **คิว** และค้นหา **เส้นทางที่สั้นที่สุด** (ขอบน้อยที่สุด) ในกราฟที่ไม่มีน้ำหนัก

## แนวคิด

เริ่มต้นที่แหล่งที่มา ใส่ลงในคิว จากนั้นทำซ้ำโดยนำโหนดออกจากคิว เยี่ยมชมเพื่อนบ้านที่ยังไม่เยี่ยมชม และใส่พวกเขาลงในคิว ชุด `visited` ป้องกันการเยี่ยมชมซ้ำ

## ตัวอย่าง

```python
from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()        # FIFO: explore nearest first
        order.append(node)
        for nbr in graph[node]:
            if nbr not in visited:
                visited.add(nbr)
                queue.append(nbr)
    return order

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
bfs(graph, 'A')                        # -> ['A', 'B', 'C', 'D']
```

## ความซับซ้อน

- **เวลา:** O(V + E) — แต่ละจุดยอดและขอบหนึ่งครั้ง
- **พื้นที่:** O(V) สำหรับคิวและชุดที่เยี่ยมชม

## เมื่อใช้ / อันตราย

ใช้ BFS สำหรับ **เส้นทางที่สั้นที่สุดในกราฟที่ไม่มีน้ำหนัก** การแยกตามระดับ และการค้นหาส่วนประกอบที่เชื่อมต่อ ใช้หน่วยความจำมากกว่า DFS (พรมแนวทั้งหมดในครั้งเดียว) ติดตามอยู่เสมอ `visited` หรือคุณอาจติดอยู่ในลูปไม่สิ้นสุดจากวัฏจักร

## เหตุใดจึงสำคัญ

BFS คืออัลกอริทึมสำหรับเส้นทางที่สั้นที่สุดเมื่อขอบแต่ละด้านมีความสำคัญเท่าเทียมกัน — การกำหนดเส้นทาง การแมกเสบ็กเวบ ระดับการแยกในเครือข่ายสังคม

โครงสร้างที่ใช้คิวและเดินทีละระดับเป็นรูปแบบการสำรวจพื้นฐาน

การรู้ BFS เทียบกับ DFS ให้คุณเลือกเครื่องมือที่เหมาะสมสำหรับความสามารถในการเข้าถึง เส้นทาง และปัญหาการจัดลำดับ

แนวคิด

ตัวอย่าง

ความซับซ้อน

เมื่อใช้ / อันตราย

เหตุใดจึงสำคัญ

คำถามที่เกี่ยวข้อง