Mã giả
Bài học 4 trên 9 trong khóa học Tìm kiếm theo chiều rộng, thuật toán đồ thị của Coddy.
bfs(n, edges, start):
build adjacency (sort each list ascending)
visited = all false
queue = [start]; visited[start] = true
order = []
while queue not empty:
node = queue.dequeue() # take from the FRONT
order.add(node)
for nb in adj[node]:
if not visited[nb]:
visited[nb] = true
queue.enqueue(nb)
return order- Điểm khác biệt duy nhất so với DFS là cấu trúc chứa dữ liệu: dùng hàng đợi (FIFO) thay vì ngăn xếp (LIFO).
- Một cách đơn giản để viết hàng đợi là dùng một mảng với chỉ số head di chuyển dần: lấy phần tử khỏi hàng đợi bằng cách đọc
queue[head]rồi tănghead.
Tự làm thử
Bài học này không có thử thách code.
Bài học này có một bài trắc nghiệm ngắn. Bắt đầu bài học để trả lời và theo dõi tiến độ.
Tất cả bài học trong Tìm kiếm theo chiều rộng, thuật toán đồ thị
Tự luyện tập: Trình biên dịch C online