Kênh Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
Monday, March 10, 2014

Thuật toán DFS – Tìm kiếm theo chiều sâu

1. Mô tả:
- Đây là thuật toán tìm các đỉnh bằng cách duyệt theo chiều sâu.
- Xuất phát từ 1 đỉnh và đi mãi cho đến khi không thể đi tiếp, sau đó đi về lại đỉnh đầu.
Trong quá trình quay lại:
+ nếu gặp đường đi khác thì đi cho đến khi không đi tiếp được nữa
+ nếu không tìm ra đường đi nào khác thì ngừng việc tìm kiếm.
- Trong quá trình đi đến đỉnh khác, thuật toán sẽ lưu lại đỉnh cha vừa đi qua để khi đi ngược lại từ đỉnh Kết thúc đến đỉnh Xuất phát, ta có thể xem được đường đi từ đỉnh Kết thúc đến đỉnh Bắt Đầu (có thể số lần đi không ít nhất, các bạn có thể tham khảo thuật toán BFS).
- Sở dĩ thuật toán này tìm được đường đi là nhờ vào cơ chế tô màu và lưu đỉnh cha. Quá trình tô màu khiến 1 đỉnh không thể xét 2 lần trở lên và có thể xem được đường đi từ đỉnh Kết Thúc đến đỉnh Xuất phát dựa vào việc lưu đỉnh cha.
- Sau đây là minh họa về thuật toán:
Hình 1 đi từ đỉnh bắt đầu, đi cho đến khi không đi được nữa.
1
Hình 1
2
Hình 2
3
Hình 3
4
Hình 4
5
Hình 5
Hình 6 do không đi được nữa nên quay ngược về lại đỉnh bắt đầu.
6
Hình 6
7
Hình 7
Hình 8 khi quay lại đến đỉnh D, gặp đỉnh H vẫn chưa được tô màu, tìm được đường đi mới.
8
Hình 8
Hình 9 sau khi đi qua đỉnh H, không thể đi tiếp được nữa nên tiến hành quay lại đến đỉnh xuất phát.
9
Hình 9
2. Cài đặt:
1
Hình 10
 - Hình 11: khởi tạo các mảng và duyệt từng đỉnh theo chiều sâu
2
Hình 11
 - Hình 12: Visit là hàm duyệt theo chiều sâu, với tham số u là đỉnh sẽ duyệt
3
Hình 12
 - Hình 13Xem kết quả
4
Hình 13
- Hình 14In đường đi từ đỉnh Xuất phát đến đỉnh kết thúc dựa vào mảng Back
5
Hình 14

0 comments:

Post a Comment

Popular Posts