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

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

1. Chương 3 CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ
2. Phần 3.1 TÌM KIẾM THEO CHIỀU SÂU (Depth First Search – DFS)
3. Ý tưởng n B1. Xuất phát từ 1 đỉnh cho trước nào đó. n B2. Xử lý đỉnh này và đánh dấu để không xử lý lần sau. n 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. n B4. Quay lại B2 cho đến khi không còn đỉnh trong danh sách. VD: 1 2 3 n Bắt đầu từ 1. Đưa các đỉnh kề với 1 vào DS: 2, 4, 5 n 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ị 6/14/2021 3
4. Cài đặt DFS n Phân tích: u Dùng cấu trúc Stack u Sử dụng mảng đánh dấu là mảng 1 chiều: l int danhdau[maxV]; l Quy ước: – danhdau[i] = 0; đỉnh i chưa được xét – danhdau[i] = 1; đỉnh i đã được xét Lý thuyết đồ thị 6/14/2021 4
5. 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 =1; i ) if (!danhdau[i] && g.mtke[v][i] != 0) Push(st,v); } } } Lý thuyết đồ thị 6/14/2021 5
6. Cài đặt DFS (tt) 1 2 3 n Đưa 1 vào Stack n Lấy 1 ra xử lý, đưa 5, 4, 2 vào Stack n Lấy 2 ra xử lý, đưa 5, 3 vào Stack n Lấy 3 ra xử lý, đưa 6, 3 vào Stack n Lấy 5 ra xử lý, đưa 4 vào Stack 4 5 6 n Lấy 4 ra xử lý. Không đưa gì vào Stack 54 n Lấy 6 ra xử lý. Không đưa gì vào Stack 36 n Lấy 5 ra. Không xử lý (vì đã xử lý rồi) Stack 25 n Lấy 4 ra. Không xử lý n Lấy 5 ra. Không xử lý 4 15 Thứ tự duyệt: 1 2 3 5 4 6 Lý thuyết đồ thị 6/14/2021 6
7. Ví dụ về DFS n Á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ị 6/14/2021 7
8. Phần 3.2 TÌM KIẾM THEO CHIỀU RỘNG (Breadth First Search - BFS)
9. Ý tưởng n B1. Xuất phát từ 1 đỉnh cho trước nào đó. n B2. Xử lý đỉnh này và đánh dấu để không xử lý lần sau. n 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 n B4. Quay lại B2 cho đến khi không còn đỉnh trong danh sách. VD: 1 2 3 n Bắt đầu từ 1. Đưa các đỉnh kề với 1 vào DS: 2, 4, 5 n 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ị 6/14/2021 9
10. Cài đặt DFS n Phân tích: u Dùng cấu trúc Queue u Sử dụng mảng đánh dấu là mảng 1 chiều: l int danhdau[maxV]; l Quy ước: – danhdau[i] = 0; đỉnh i chưa được xét – danhdau[i] = 1; đỉnh i đã được xét Lý thuyết đồ thị 6/14/2021 10
11. 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<=g.nV; i++) danhdau[i] = 0; // chua co dinh nao duoc xet Khoitao(q); // Khoi tao Queue // Bat dau Push(q,s); // Dua s vao Queue while (!isEmpty(q)) //Trong khi Queue chua rong { int v = Pop (q); // Lay v ra khoi Queue if (danhdau[v] != 1) // Neu v chua xet { cout<<v<<“ “; danhdau[v] = 1; for (i=1; i<=g.nV; i++) if (!danhdau[v] && g.mtke[v][i] != 0) Push(q,v); } } } Lý thuyết đồ thị 6/14/2021 11
12. Cài đặt BFS (tt) 1 2 3 n Đưa 1 vào Queue n Lấy 1 ra xử lý, đưa 5, 4, 2 vào Queue n Lấy 2 ra xử lý, đưa 5, 3 vào Queue n Lấy 4 ra xử lý, đưa 5 vào Queue 4 5 6 n Lấy 5 ra xử lý, đưa 3 vào Queue 6 n Lấy 3 ra xử lý. Đưa 6 vào Queue 3 n Lấy 5 ra. Không xử lý (vì đã xử lý rồi) 5 n Lấy 5 ra. Không xử lý 5 Queue n Lấy 3 ra. Không xử lý 3 n Lấy 6 ra xử lý. Không đưa gì vào Queue 5 4 21 Thứ tự duyệt: 1 2 4 5 3 6 Lý thuyết đồ thị 6/14/2021 12
13. Ví dụ về BFS n Á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 3 9 2 4 5 6 8 10 7 Đáp án: t u s v Đỉnh x không được duyệt Lý thuyết đồ thị 6/14/2021 13
14. Phần 3.3 ỨNG DỤNG CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ
15. Hàm DFS bằng đệ quy n Do nguyên tắc gọi hàm đệ quy cũng giống như nguyên tắc hoạt động của Stack nên ta có thể dùng đệ quy thay cho Stack để viết hàm DFS n Chú ý: u Mảng danhdau bắt buộc phải khai báo bên ngoài hàm đệ quy u Phần khởi tạo mảng danhdau cũng vẫn được thực hiện nhưng phải để ở bên ngoài hàm đệ quy (thường khởi tạo ở trong hàm main). int danhdau[maxV] void DFS(DOTHI g, int s) // s la dinh xuat phat { if (danhdau[s] ==1) return; cout<<s<<“ da duoc duyet \n“; danhdau[s] = 1; for (int v = 1; v<=g.nV; v++) if (danhdau[v] == 0&&g.mtke[s][v]!=0) DFS(g,v); } Lý thuyết đồ thị 6/14/2021 15
16. Áp dụng DFS để kiểm tra liên thông n Ý tưởng: u Áp dụng cho đồ thị vô hướng u Áp dụng DFS, bắt đầu từ đỉnh bất kỳ, nếu duyệt qua được tất cả các đỉnh thì đồ thị là liên thông u Cụ thể: l Sử dụng thêm biến dem để đếm số đỉnh được duyệt l Nếu duyệt xong mà đếm bằng g.nV (số đỉnh của đồ thị) thì có nghĩa là tất cả các đỉnh được duyệt
17. Áp dụng DFS để kiểm tra liên thông (tt) int danhdau[maxV] void DFS_lt(DOTHI g, int s, int &dem) // s la dinh xuat phat { //Khoi tao mang danh dau trong ham main hoac ben ngoai ham nay cout<<s<<“ da duoc duyet \n“; dem++; danhdau[s] = 1; for (int v = 1; v<=g.nV; v++) if (danhdau[v] == 0) DFS(g,v); } int isLienThong(DOTHI g) { if (g.type == 1) return 0; // khong xet do thi co huong int dem = 0; for (int v = 1; v<= g.nV; v++) danhdau[v] = 0; DFS_lt(g,1,dem); if (dem == g.nV) return 1; // do thi lien thong return 0; }
18. Áp dụng DFS để tìm đường đi n Ý tưởng: