Những lỗi thường gặp trong giải thuật đồ thị
Với các bài toán đồ thị, lỗi thường không nằm ở thuật toán chính mà đến từ cách đánh chỉ số, quên reset biến, mô hình hóa sai hoặc giả định nhầm về hướng cạnh và tính liên thông.
1. Dựng đồ thị sai
Trước khi debug BFS, DFS hay Dijkstra, tôi luôn kiểm tra lại mô hình đồ thị. Đây là đồ thị có hướng hay vô hướng? Đỉnh đánh số từ 0 hay từ 1? Mỗi cạnh có trọng số, có thể lặp lại, hay bị ràng buộc bởi thứ tự input?
2. Quên reset trạng thái giữa các test
Đây là lỗi rất hay gặp trong thi đấu. Các mảng như visited, dist và adjacency list
phải được reset đúng cách khi đề có nhiều test case.
3. Dùng sai kiểu duyệt cho bài toán
- BFS dùng cho đường đi ngắn nhất trên đồ thị không trọng số.
- Dijkstra dùng cho đồ thị trọng số không âm.
- DFS hữu ích khi khai thác cấu trúc, tính liên thông và các hướng duyệt mang tính đệ quy.
4. Bỏ qua các trường hợp biên
Bây giờ tôi luôn thử với đỉnh cô lập, thành phần không liên thông, self-loop, nhiều cạnh trùng nhau và input rất nhỏ. Những trường hợp đó bóc lộ giả định sai rất nhanh.
Checklist trước khi nộp bài
- Đồ thị có hướng hay vô hướng?
- Tất cả mảng đã được reset chưa?
- Đỉnh bắt đầu có hợp lệ không?
- Đồ thị có thể không liên thông không?
- Thuật toán được chọn có phù hợp với trọng số cạnh không?Giữ checklist ngắn này trong đầu giúp tôi tiết kiệm thời gian hơn nhiều so với việc vá lỗi mù quáng sau một lần nộp sai.