Bài giảng Lý thuyết đồ thị - Chương 3: Các thuật toán tìm kiếm trên đồ thị và ứng dụng - Nguyễn Trần Phi Phượng

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ị và ứng dụng - Nguyễn Trần Phi Phượng

1. Chương 3 CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ VÀ ỨNG DỤNG
2. 3.1 Tìm kiếm theo chiều sâu trên đồ thị Depth First Search ƒ B1. Xuất phát từ 1 đỉnh cho trướcnàođó. ƒ B2. Xử lý đỉnh này và đánh dấu để không xử lý lầnsau. ƒ B3. Đưatấtcả các đỉnh kề với nó vào danh sách xử lý và chọn1 đỉnh để xử lý tiếp theo. ƒ B4.QuaylạiB2chođến khi không còn đỉnh trong danh sách. VD: ƒ Bắt đầutừ 1. Đưa các đỉnh kề với 1 vào DS: 2, 4, 5 1 2 3 ƒ Chọn2để xử lý. Đưa các đỉnh kề với 2 vào DS: 3, 4, 5, Thứ tự:123546 4 5 6 17/03/2011 Lý thuyết đồ thị 2
3. 3.1 Tìm kiếm theo chiều sâu trên đồ thị Phân tích: – Dùng cấu trúc Stack –Sử dụng mảng đánh dấulàmảng 1 chiều: • int danhdau[maxV]; •Quyước: – danhdau[i] = 0; đỉnh i chưa đượcxét – danhdau[i] = 1; đỉnh i đã đượcxét 17/03/2011 Lý thuyết đồ thị 3
4. 3.1 Tìm kiếm theo chiều sâu trên đồ thị 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,i); } } } 17/03/2011 Lý thuyết đồ thị 4
5. 3.1 Tìm kiếm theo chiều sâu trên đồ thị 1 2 3 ƒ Đưa 1 vào Stack ƒ Lấy1raxử lý, đưa 5, 4, 2 vào Stack ƒ Lấy2raxử lý, đưa 5, 3 vào Stack ƒ Lấy3raxử lý, đưa 6, 5 vào Stack 4 5 6 ƒ Lấy5raxử lý, đưa 4 vào Stack ƒ Lấy4raxử lý. Không đưa gì vào Stack 54 ƒ Lấy6raxử lý. Không đưa gì vào Stack 36 25 Stack ƒ Lấy 5 ra. Không xử lý (vì đãxử lý rồi) 4 ƒ Lấy 4 ra. Không xử lý 15 ƒ Lấy 5 ra. Không xử lý Thứ tự duyệt: 1 2 3 5 4 6 17/03/2011 Lý thuyết đồ thị 5
6. 3.1 Tìm kiếm theo chiều sâu trên đồ thị ƒÁp dụng DFS, hãy thể hiệnthứ tự duyệt các đỉnh trong đồ thị sau: u 0 t v s x Đáp án: 012349567810 Đáp án: tusv Đỉnh x không được duyệt 17/03/2011 Lý thuyết đồ thị 6
7. 3.2 Tìm kiếm theo chiều rộng trên đồ thị Breadth First Search ƒ B1. Xuất phát từ 1 đỉnh cho trướcnàođó. ƒ B2. Xử lý đỉnh này và đánh dấu để không xử lý lầnsau. ƒ B3. Đưatấtcả các đỉnh kề với nó vào danh sách xử lý và lầnlượtxử lý các đỉnh kề với đỉnh đang xét. ƒ B4.QuaylạiB2chođến khi không còn đỉnh trong danh sách. VD: ƒ Bắt đầutừ 1. Đưa các đỉnh kề với 1 vào DS: 2, 4, 5 1 2 3 ƒ Chọn2để xử lý. Đưa các đỉnh kề với 2 vào DS: 3, 4, 5, Thứ tự:124536 4 5 6 17/03/2011 Lý thuyết đồ thị 7
8. 3.2 Tìm kiếm theo chiều rộng trên đồ thị Phân tích: – Dùng cấu trúc Queue –Sử dụng mảng đánh dấulàmảng 1 chiều: • int danhdau[maxV]; •Quyước: – danhdau[i] = 0; đỉnh i chưa đượcxét – danhdau[i] = 1; đỉnh i đã đượcxét 17/03/2011 Lý thuyết đồ thị 8
9. 3.2 Tìm kiếm theo chiều rộng trên đồ thị 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[i] && g.mtke[v][i] != 0) Push(q,i); } } } 17/03/2011 Lý thuyết đồ thị 9
10. 3.2 Tìm kiếm theo chiều rộng trên đồ thị 1 2 3 ƒ Đưa 1 vào Queue ƒ Lấy1raxử lý, đưa 2, 4, 5 vào Queue ƒ Lấy2raxử lý, đưa 3, 5 vào Queue ƒ Lấy4raxử lý, đưa 5 vào Queue 4 5 6 6 ƒ Lấy5raxử lý, đưa 3 vào Queue 3 ƒ Lấy3raxử lý. Đưa 6 vào Queue 5 ƒ Lấy 5 ra. Không xử lý (vì đãxử lý rồi) 5 Queue ƒ Lấy 5 ra. Không xử lý 3 ƒ Lấy 3 ra. Không xử lý 5 ƒ Lấy6raxử lý. Không đưa gì vào Queue 4 21 Thứ tự duyệt: 1 2 4 5 3 6 17/03/2011 Lý thuyết đồ thị 10
11. 3.2 Tìm kiếm theo chiều rộng trên đồ thị ƒÁp dụng BFS, hãy thể hiệnthứ tự duyệtcácđỉnh trong đồ thị sau: u 0 t v s x Đáp án: 013924568107 Đáp án: tusv Đỉnh x không được duyệt 17/03/2011 Lý thuyết đồ thị 11
12. 3.3 Tìm đường đi và kiểm tra tính liên thông Bài toán tìm đường đigiữahaiđỉnh. Giả sử svàtlàhaiđỉnh nào đócủa đồ thị. Hãy tìm đường đi từ s đếnt. Thủ tục DFS(s) (BFS(s)) sẽ cho phép thămtấtcả các đỉnh thuộc cùng một thành phần liên thông vớis.Vìvậy, sau khi thựchiện xong thủ tục, nếu danhdau[t]=0 thì không có đường đi từ s đếnt. 17/03/2011 Lý thuyết đồ thị 12
13. 3.3 Tìm đường đi và kiểm tra tính liên thông Kiểm tra tính liên thông. –Ápdụng cho đồ thị vô hướng –Ápdụng DFS, bắt đầutừđỉnh bấtkỳ,nếuduyệt qua đượctấtcả các đỉnh thì đồ thị là liên thông –Cụ thể: •Sử dụng thêm biếndemđể đếmsốđỉnh được duyệt •Nếuduyệtxongmàđếmbằng g.nV (sốđỉnh của đồ thị) thì có nghĩalàtấtcả các đỉnh được duyệt 17/03/2011 Lý thuyết đồ thị 13
14. 3.3 Tìm đường đi và kiểm tra tính liên thông int danhdau[maxV] void DFS_lt(DOTHI g, int s, int &dem) // s la dinh xuat phat { dem++; danhdau[s] = 1; for(intv=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(intv=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; } 17/03/2011 Lý thuyết đồ thị 14