DFS & BFSthầy Phúc

Bài học cho học sinh chuyên tin

Duyệt đồ thị:
DFS và BFS

Hai thuật toán, một ý tưởng. Cả hai đều đi thăm mọi đỉnh đến được từ một đỉnh cho trước. Chúng chỉ khác nhau ở một câu hỏi duy nhất: đỉnh nào được lấy ra xử lý tiếp theo?

Trang này dạy các em bằng hình vẽ và trình mô phỏng bấm từng bước, không phải bằng cách đọc code rồi tin. Cuối mỗi bài có 3 bài LeetCode kèm đáp án ẩn.

Bắt đầu từ phần cơ bản →Xem ngay hai thuật toán cạnh nhau
12345678
Đồ thị mẫu dùng xuyên suốt cả trang: 8 đỉnh, 8 cạnh, xuất phát từ đỉnh 1.

Cùng một đồ thị, hai thứ tự thăm

Đây là toàn bộ sự khác biệt, gói trong một hình. Số nhỏ màu đen cạnh mỗi đỉnh là thứ tự đỉnh đó được thăm.

DFS — đi sâu trước

1122364355677488
Thứ tự thăm: 1 → 2 → 4 → 7 → 5 → 3 → 6 → 8. DFS lao xuống hết nhánh bên trái (1-2-4-7) rồi mới quay lại.

BFS — đi rộng trước

tầng 0tầng 1tầng 2tầng 31122334455667788
Thứ tự thăm: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8. BFS quét sạch từng tầng: tầng 1 là {2,3}, tầng 2 là {4,5,6}, tầng 3 là {7,8}.

Lộ trình

  1. Cơ bản — đồ thị là gì, danh sách kề, vì sao bắt buộc phải có mảngdaTham, và lưới cũng là đồ thị.
  2. DFS — bản đệ quy, bản ngăn xếp, các lỗi thường gặp, 3 bài LeetCode: đếm đảo, đếm tỉnh, phát hiện chu trình.
  3. BFS — hàng đợi, khái niệm tầng, vì sao BFS cho đường đi ngắn nhất, 3 bài LeetCode: duyệt theo tầng, đường ngắn nhất trong lưới, BFS đa nguồn.
  4. So sánh — chạy song song hai thuật toán trên cùng đồ thị, và bảng quyết định "bài này nên dùng cái nào".