Bài giảng Lý thuyết đồ thị: Chương 3 - Các thuật toán tìm kiếm trên đồ thị

Bài giảng Lý thuyết đồ thị: Chương 3 - Các thuật toán tìm kiếm trên đồ thị trình bày về tìm kiếm theo chiều sâu (Depth First Search – DFS); tìm kiếm theo chiều rộng (Breadth First Search - BFS); ứng dụng các thuật toán tìm kiếm trên đồ thị. Mời các bạn tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết đồ thị: Chương 3 - Các thuật toán tìm kiếm trên đồ thị Chương 3 CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ Phần 3.1 TÌM KIẾM THEO CHIỀU SÂU (Depth First Search – DFS) Ý tưởng  B1. Xuất phát từ 1 đỉnh cho trước nào đó.  B2. Xử lý đỉnh này và đánh dấu để không xử lý lần sau.  B3. Đưa tất cả các đỉnh kề với nó vào danh sách xử lý và chọn 1 đỉnh để xử lý tiếp theo.  B4. Quay lại B2 cho đến khi không còn đỉnh trong danh sách. VD: 2 1 3  Bắt đầu từ 1. Đưa các đỉnh kề với 1 vào DS: 2, 4, 5  Chọn 2 để xử lý. Đưa các đỉnh kề với 2 vào DS: 3, 4, 5, … 4 5 6 Thứ tự: 1 2 3 5 4 6 Lý thuyết đồ thị 11/26/15 3 Cài đặt DFS  Phân tích:  Dùng cấu trúc Stack  Sử dụng mảng đánh dấu là mảng 1 chiều:  int danhdau[maxV];  Quy ước: – danhdau[i] = 0; đỉnh i chưa được xét – danhdau[i] = 1; đỉnh i đã được xét Lý thuyết đồ thị 11/26/15 4 Cài đặt DFS (tt) void DFS(DOTHI g, int s) // s la dinh xuat phat { int danhdau[maxV]; Stack st; //Khoi tao for (int i = 1; i Cài đặt DFS (tt) 1 2 3  Đưa 1 vào Stack  Lấy 1 ra xử lý, đưa 5, 4, 2 vào Stack  Lấy 2 ra xử lý, đưa 5, 3 vào Stack  Lấy 3 ra xử lý, đưa 6, 3 vào Stack  Lấy 5 ra xử lý, đưa 4 vào Stack 4 5 6  Lấy 4 ra xử lý. Không đưa gì vào Stack 4 5  Lấy 6 ra xử lý. Không đưa gì vào Stack 3 6  Lấy 5 ra. Không xử lý (vì đã xử lý rồi) Stack 5 2  Lấy 4 ra. Không xử lý  Lấy 5 ra. Không xử lý 4 1 5 Thứ tự duyệt: 1 2 3 5 4 6 Lý thuyết đồ thị 11/26/15 6 Ví dụ về DFS  Áp dụng DFS, hãy thể hiện thứ tự duyệt các đỉnh trong đồ thị sau: u 0 t v s x Đáp án: 0 1 2 3 4 9 5 6 7 8 10 Đáp án: t u s v Đỉnh x không được duyệt Lý thuyết đồ thị 11/26/15 7 Phần 3.2 TÌM KIẾM THEO CHIỀU RỘNG (Breadth First Search - BFS) Ý tưởng  B1. Xuất phát từ 1 đỉnh cho trước nào đó.  B2. Xử lý đỉnh này và đánh dấu để không xử lý lần sau.  B3. Đưa tất cả các đỉnh kề với nó vào danh sách xử lý và lần lượt xử lý các đỉnh kề với đỉnh đang xét  B4. Quay lại B2 cho đến khi không còn đỉnh trong danh sách. VD: 2 1 3  Bắt đầu từ 1. Đưa các đỉnh kề với 1 vào DS: 2, 4, 5  Chọn 2 để xử lý. Đưa các đỉnh kề với 2 vào DS: 3, 4, 5, … 4 5 6 Thứ tự: 1 2 4 5 3 6 Lý thuyết đồ thị 11/26/15 9 Cài đặt DFS  Phân tích:  Dùng cấu trúc Queue  Sử dụng mảng đánh dấu là mảng 1 chiều:  int danhdau[maxV];  Quy ước: – danhdau[i] = 0; đỉnh i chưa được xét – danhdau[i] = 1; đỉnh i đã được xét Lý thuyết đồ thị 11/26/15 10 Cài đặt BFS (tt) void BFS(DOTHI g, int s) // s la dinh xuat phat { int danhdau[maxV]; Queue q; //Khoi tao for (int i = 1; i Cài đặt BFS (tt) 1 2 3  Đưa 1 vào Queue  Lấy 1 ra xử lý, đưa 5, 4, 2 vào Queue  Lấy 2 ra xử lý, đưa 5, 3 vào Queue  Lấy 4 ra xử lý, đưa 5 vào Queue 4 5 6  Lấy 5 ra xử lý, đưa 3 vào Queue 6  Lấy 3 ra xử lý. Đưa 6 vào Queue 3  Lấy 5 ra. Không xử lý (vì đã xử lý rồi) 5  Lấy 5 ra. Không xử lý 5 Queue  Lấy 3 ra. Không xử lý 3  Lấy 6 ra xử lý. Không đ ...