tailieunhanh - Bài giảng Lý thuyết đồ thị - Bài 2+3: Các thuật toán tìm kiếm trên đồ thị (tt)

Bài giảng "Lý thuyết đồ thị - Bài 2+3: Các thuật toán tìm kiếm trên đồ thị" cung cấp cho người học các kiến thức: Tìm kiếm theo chiều sâu, tìm kiếm theo chiều rộng, ứng dụng các thuật toán tìm kiếm trên đồ thị. nội dung chi tiết. | Bài giảng Lý thuyết đồ thị - Bài 2+3: Các thuật toán tìm kiếm trên đồ thị (tt) Bài 2, 3 (tt) Các thuật toán tìm kiếm trên đồ thị 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 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 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 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 7 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, .