Tutorial — Chặn Một Tuyến Đường

Kết quả cuối cùng phụ thuộc vào việc xử lý một chu trình đầu tiên trong đồ thị. Việc cần làm trước hết là kiểm tra xem đồ thị có sẵn chu trình nào không bằng thuật toán tìm kiếm theo chiều sâu (DFS).

Một chu trình chỉ bị phá vỡ khi ta xóa đi một cạnh trực tiếp tạo nên chu trình đó.

Mọi cạnh nằm bên ngoài một chu trình cụ thể đều không có tác dụng phá vỡ chu trình đó, nên việc xóa một cạnh bất kỳ bên ngoài là vô ích. Vì vậy ta chỉ cần thu hẹp không gian tìm kiếm vào các cạnh tạo nên chu trình đầu tiên vừa tìm được.

Lưu lại các cạnh của chu trình đầu tiên vào một mảng và lặp qua từng cạnh. Với mỗi lần lặp, hãy xóa tạm thời cạnh đó và chạy lại thuật toán duyệt đồ thị DFS để kiểm tra tính không chu trình của phần đồ thị còn lại.