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

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

Share:

0 Nhận xét

Categories

. . . 1 [English | DVD] Trọn Bộ DVD Effortless English 3 Ajax 1 Andengine 3 Android 41 Android Studio Cài đặt và phím tắt thông dụng 1 API 1 App Android 1 Applicaiton Chat Multi Client 1 ASP.NET 9 Bài tập lập trình C/C++ có lời giải 1 Bài tập thuật toán C/C++ Và Tuyển tập đề thi olympic 2 Bắt đầu Học Lập Trình 4 Blogger 2 C/C++ 16 C# 21 Câu hỏi phỏng vấn Android 1 Cocos2d-JS 3 Cocos2d-x 3 Code game android 3 Công Cụ Lập Trình 13 Công nghệ 3 Cosos2d 1 CSS 1 Cuộc sống 15 Custom Button trong Android 2 Design Patterns 3 DevExpress 1 Đồ Án 1 DOREMON - NOBITA 2 Dự án 1 Ebook Android 1 English 8 Example Custom Android 1 facebook 1 Fedora 2 Freelancer 1 Game Android 4 Game Android AndEngine 1 Giới thiệu về Ajax 1 Hiệu ứng lắc trong android 1 Hướng dẫn cài đặt Mac OS trên VMware 1 Hướng dẫn download tài liệu miễn phí của website tailieu.vn 1 Hướng dẫn lập trình android 11 Hướng dẫn lập trình Windows Phone 3 Hướng đối tượng 2 Internet được khôi phục 1 Internet of Things 1 iOS 33 Java 9 Kiểm thử phần mềm 1 Kinh nghiệm lập trình 17 Kỹ Năng 1 Lập trình Android FPT Software Training 1 Lập Trình Game Đa Nền Tảng 2 Lập trình game mobile 2 Lập trình iOS FPT Software Training 1 Lập trình mạng 2 LẬP TRÌNH VIÊN CHUYÊN NGHIỆP TRÊN THIẾT BỊ DI ĐỘNG 2 Laptop 1 Libgdx 1 LinQ 3 Linux 6 Load CSDL SQL server ASP.NET 1 Lỗi Eclipse Ctr + Space 1 Mạng Xã Hôi 1 máy thật PC 1 Mbook TIN HỌC A 1 Mbook TIN HỌC B 1 mỗi bài 20 câu 1 NGAN-HANG-DE-THI-TRAC-NGHIEM-ASP.NET 1 Nguyên tắc ngón tay cái trong thiết kế ứng dụng cho điện thoại 1 Nhập môn lập trình C 14 Những câu hỏi phỏng vấn "xương" nhất 1 Những điểm mới kỳ thi THPT quốc gia 2015 1 Object C 1 Phần mềm 3 PHP 2 Phương pháp luyện thi TOEIC 1 Python 2 Review Game 1 SEO 4 Share Acc Fshare 1 Share VIP Miễn phí 1 Sinh viên mới tốt nghiệp – viết gì trong CV 1 Socket Android Client to PC Server C# 2 Socket Chat nhiều Client với server C# 2 Source code 4 Source code game C# 1 Source code game iOS 2 T3H-KHTN 7 Tài Liệu Android 7 Tài Liệu C# 4 Tài liệu hướng dẫn lập trình game với cocos2d-x 1 Tài Liệu iOS 7 Tài Liệu IT 3 Tài Liệu Java 2 Tài liệu Lập trình iOS Tiếng Việt đầy đủ TTTH đại học khoa học tự nhiên 1 Tài Liệu PHP 1 TÀI LIỆU THIẾT KẾ SỐ 1 Tài Liệu Windows Phone 1 Tạo Group Mail Google 1 Tạo hiệu ứng trong lập trình iOS 1 Tạo tên CoCaCoLa 1 Thắc mắc C/C++ 3 THẬP PHÂN sang NHỊ PHÂN không sử dụng MẢNG 1 Thiết kế giao diện Android - App Calculation Android Studio 1 Thiết kế giao diện phần mềm 1 Thuật ngữ cơ bản trong lập trình game AndEngine 1 Thuật toán 5 Thuật toán điều phối FCFS 1 Tiếng Anh 2 Tin Tức 1 Toàn bộ tài liệu ĐTVT 5 năm học 1 Tổng hợp những nơi người lái xe hay bị mắc lỗi tại TPHCM 1 Tutorials Android 2 Tuyến cáp quang AAG đã sửa xong 1 Unity 1 Vim 1 Visual Studyo 2013 1 WEB 1 Website nén JS và CSS tốt nhất 1 Websites Developer 2 Windows 10 Technical Preview 1 Windows Phone 5 WPF 1 XAMARIN 1 Xóa project appcompat_v 1