L31 — Duyệt đồ thị: BFS & DFS
Ba module tương tác: (1) so sánh thứ tự thăm BFS (theo tầng) vs DFS (đâm sâu) trên cùng đồ thị; (2) đếm đảo bằng flood fill; (3) lan tỏa multi-source BFS (cam thối).
1. BFS vs DFS trên đồ thị
Chọn nguồn rồi bấm BFS hoặc DFS. Quan sát: BFS loang theo tầng (cùng level cùng lúc), DFS đâm sâu một nhánh rồi backtrack.
Nguồn: 0 (click đỉnh để đổi)
chưa thăm
trong queue/stack
đang thăm
đã xong
Sẵn sàng. Chọn BFS hoặc DFS.
thứ tự thăm: —
2. Số đảo — Flood Fill
1 = đất, 0 = nước. Mỗi lần gặp ô đất chưa thăm → một đảo mới, flood fill 4 hướng "dìm" cả cụm. Số đảo: 0.
Sẵn sàng.
3. Multi-source BFS — Cam thối
2 = cam thối (nguồn), 1 = cam tươi, 0 = trống. Mỗi phút, mọi cam thối lây sang cam tươi kề (4 hướng) đồng thời. Phút: 0 · Cam tươi còn lại: 0.
Sẵn sàng. Tất cả nguồn (số 2) vào queue cùng lúc.