Nội dung

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:  Bắt đầu từ 1. Đưa các đỉnh kề với 2 1 3 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, … Thứ tự: 1 2 3 5 4 6  4 5 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; – danhdau[i] = 1; đỉnh i chưa được xét đỉ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<=g.nV; i++) danhdau[i] = 0; // chua co dinh nao duoc xet Khoitao(st); // Khoi tao Stack // Bat dau Push(st,s); // Dua s vao Stack while (!isEmpty(st)) //Trong khi Stack chua rong { int v = Pop (st); // Lay v ra khoi Stack if (danhdau[v] != 1) // Neu v chua xet { cout<=1; i--) if (!danhdau[i] && g.mtke[v][i] != 0) Push(st,v); } } } 5 Cài đặt DFS (tt)           Đư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 Lấy 4 ra xử lý. Không đưa gì vào Stack Lấy 6 ra xử lý. Không đưa gì vào Stack Lấy 5 ra. Không xử lý (vì đã xử lý rồi) Lấy 4 ra. Không xử lý Lấy 5 ra. Không xử lý Thứ tự duyệt: 1 2 1 4 6 5 4 5 3 6 5 2 4 1 5 2 3 3 5 Stack 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 Đáp án: 0 1 2 3 4 9 5 6 7 8 10 x Đá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:  Bắt đầu từ 1. Đưa các đỉnh kề với 2 1 3 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, … Thứ tự: 1 2 4 5 3 6  4 5 6 9 Cài đặt BFS  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; – danhdau[i] = 1; đỉnh i chưa được xét đỉnh i đã được xét 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<=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<

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.