Duyệt đồ thị

Mô phỏng này cho thấy máy tính khám phá một đồ thị như thế nào. Học sinh chọn tìm kiếm theo chiều rộng (BFS) hoặc tìm kiếm theo chiều sâu (DFS), chọn nút xuất phát và đặt tốc độ, rồi xem các nút đổi màu khi đang chờ, đang xử lý hoặc đã thăm. Các chỉ số hiển thị số nút đã thăm, kích thước hàng đợi hoặc ngăn xếp và thứ tự thăm, còn một nút bấm sẽ tạo đồ thị ngẫu nhiên mới. Chạy cả hai phương pháp từ cùng một điểm xuất phát cho thấy BFS lan ra theo vòng tròn trong khi DFS đi sâu. Mô phỏng hỗ trợ các bài tin học về cấu trúc dữ liệu và thuật toán.

• Chạy BFS từ nút 1 và đọc chỉ số Thứ tự thăm.
• Chuyển Phương pháp sang DFS với cùng Nút xuất phát và so sánh thứ tự.
• Theo dõi chỉ số Kích thước hàng đợi / ngăn xếp tăng và giảm với mỗi phương pháp.
• Đổi Nút xuất phát và xem toàn bộ quá trình duyệt thay đổi thế nào.
• Nhấn Tạo lại đồ thị và dự đoán thứ tự trước khi chạy.

1. 1Mô tả cách tìm kiếm theo chiều rộng và chiều sâu khám phá một đồ thị.
2. 2Phân biệt hàng đợi với ngăn xếp và gắn mỗi cấu trúc với một phương pháp tìm kiếm.
3. 3Dự đoán thứ tự thăm của một đồ thị nhỏ.
4. 4Giải thích vì sao BFS tìm được đường đi có ít bước nhất.

Câu hỏi giáo viên thường đặt ra