[Thuật toán – Java] Chương trình mô phỏng thuật toán tìm kiếm theo chiều rộng (BFS) và chiều sâu (DFS)

Tháng Sáu 9, 2014 nguyenvanquan7826 TT Đồ thị 15 responses

Chương trình dưới đây mô tả 2 thuật toán tìm kiếm theo chiều rộng (BFS – Breadth-first search) và chiều sâu (DFS – Depth-first search) trên đồ họa, có các bước đi và màu sắc đẹp.

Giao diện của chương trình khi khởi động sẽ như thế này:

duyệt đồ thị theo chiều sâu và chiều rộng

Chương trình có 4 phần chính. Phần trên (top) là tiêu đề chương trình, phần dưới (bottom) là tên mềnh =)). Phần bên trái (left) là bảng điều khiển. Phần bên phải là phần vẽ đồ thị.
Bạn lưu ý đến phần bên trái (bảng điều khiển). Trước tiên bạn cần chọn thuật toán để duyệt đồ thị, sau đó nhập số điểm của đồ thị (tối đa 10 điểm, nếu bạn muốn sửa thì vào code sửa lại) và các cạnh của nó. Các điểm của đồ thị sẽ được bố trí theo hình tròn để tránh các đường đi trùng nhau gây khó quan sát. Sau khi bạn nhập xong các đầu vào thì cuối cùng là chọn điểm bắt đầu chạy.

Dưới đây là hình ảnh khi duyệt đồ thị theo BFS và DFS.

duyệt đồ thị theo chiều rộng

duyệt đồ thị theo chiều sâu

Màu của điểm đầu là vàng, màu điểm cuối cùng là đỏ. Khi duyệt thì thứ tự duyệt sẽ được đánh số. VD với đồ thị trên, khi duyệt BFS sẽ là 1->2->4->5->3

Các bạn có thể download mã nguồn hoặc file jar. Lưu ý bạn cần cài JDK mới chạy được file jar.
Mọi thắc mắc hoặc góp ý xin liên hệ với mình. Rất vui khi các bạn quan tâm góp ý.