Chương 3: CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ

Duyệt đồ thị theo chiều sâu * Ý tưởng: - Từ đỉnh v1 nào đó chưa thăm, thăm v1, rồi tìm đỉnh v2 (chưa thăm) kề với v1, thăm v2… Thuật toán lặp
Nội dung trích xuất từ tài liệu:
Chương 3: CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊChương 3CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ1. Duyệt đồ thị theo chiều sâu* Ý tưởng:- Từ đỉnh v1 nào đó chưa thăm, thăm v1, rồi tìm đỉnh v2 (chưa thăm) kề với v1, thăm v2… Thuật toán lặp lại việc thăm cho tới khi tất cả các đỉnh đều được thăm.- Nếu tại một đỉnh vi nào đó, không còn đỉnh nào kề với vi là chưa thăm thì quay trở lại tiếp tục tìm đỉnh kề chưa thăm khác của vi-1. A B Nếu bắt đầu từ đỉnh A, thì thứ tự thăm có thể là: E A, C, B, D, E D C* Thuật toán:void DFS1(v){ Tham(v); ChuaTham[v]=false; //ghi nhận là đã thăm v để về sau không thăm nữa. For (u∈ Ke(v)) // xét tất cả các đỉnh u kề với v If (ChuaTham[u]) DFS1(u); //neu u chua thăm, thăm u}void DFS(){ for (v ∈ V) ChuaTham[v]=true; //ban đầu tất cả các đỉnh đều chưa thăm. for (v∈ V) //xét tất cả các dinh if (ChuaTham[v]) DFS1(v); // neu đỉnh v chua tham thi tham v}* Ví dụ : Xét đồ thị cho trong hình 1 gồm 13 đỉnh, các đỉnh được đánh số từ 1 đến 13 như sau: Hình 1 1Giả thiết rằng các đỉnh trong danh sách kề của đỉnh v (Ke(v)) được sắp xếp theo thứ tự tăng dần củachỉ số. Khi đó chỉ số mới (trong ngoặc) của các đỉnh được đánh lại theo thứ tự chúng được thămtrong thuật toán tìm kiếm theo chiều sâu.* Nhận xét:- Mỗi đỉnh sẽ được thăm đúng một lần.- DFS1(v) thăm tất cả các đỉnh thuộc cùng một thành phần liên thông chứa đỉnh v. Số lần DFS gọi DFS1 chính là số thành phần liên thông của đồ thị.- Độ phức tạp của thuật toán là O(n+m).2. Duyệt đồ thị theo chiều rộng* Ý tưởng:- Từ đỉnh v nào đó chưa thăm, thăm v, cất tất cả các đỉnh u (chưa thăm) kề với v vào hàng đợi. Lấy từ hàng đợi một đỉnh u, thăm u, rồi lại cất tất cả các đỉnh t (chưa thăm) kề với u vào hàng đợi… Thuật toán lặp lại việc thăm cho tới khi hàng đợi rỗng.- Nếu tại một đỉnh x nào đó, không còn đỉnh nào kề với x là chưa thăm thì quay trở lại tiếp tục tìm đỉnh kề chưa thăm khác của y (y là đỉnh trước khi đến x).* Thuật toán:void BFS1(v){ queue= φ ; //khoi tạo queue là rỗng push(queue,v); //cất v vào queue ChuaTham[v]=false; //ghi nhận là đã thăm v để về sau không thăm nữa. while (queue ≠ φ ) // xét tất cả các đỉnh u kề với v { v=pop(queue);//lay v tu queue Tham(v); For (u∈ Ke(v)) // xét tất cả các đỉnh u kề với v If (ChuaTham[u]) { push(queue,u); ChuaTham[u]=false; } }}void BFS() 2{ for (v ∈ V) ChuaTham[v]=true; //ban đầu tất cả các đỉnh đều chưa thăm. for (v∈ V) //xét tất cả các dinh if (ChuaTham[v]) BFS1(v); // neu đỉnh v chua tham thi tham v}* Ví dụ:Xét đồ thị xét trong hình 1, chỉ số mới (trong ngoặc) của các đỉnh được đánh lại theo thứ tự chúngđược thăm trong thuật toán tìm kiếm theo chiều rộng.* Nhận xét:- Mỗi đỉnh sẽ được thăm đúng một lần.- DFS1(v) thăm tất cả các đỉnh thuộc cùng một thành phần liên thông chứa đỉnh v. Số lần DFS gọi DFS1 chính là số thành phần liên thông của đồ thị.- Độ phức tạp của thuật toán là O(n+m).3. Tìm đường đi và kiểm tra tính liên thônga) Bài toán tìm đường đi giữa hai đỉnh:Giả sử s và t là hai đỉnh nào đó của đồ thị. Hãy tìm đường đi từ s đến t.* Ý tưởng:Gọi thủ tục DFS(s) hoặc (BFS(s)) để thăm tất cả các đỉnh thuộc cùng một thành phần liên thông vớis. Nếu sau khi thực hiện xong thủ tục mà Chuaxet[t]=true thì không có đường đi từ s đến t, ngược lạithì có đường đi từ s đến t. Để ghi nhận đường đi, ta dùng thêm biến Truoc[v] để ghi nhận đỉnh đitrước đỉnh v trong đường đi từ s đến v.* Cài đặt:- DFS1(v) cần sửa như sau:…..If (ChuaTham[u]){ Truoc[u]:=v; DFS1(u); //neu u chua thăm, thăm u}- BFS(v) cần sửa như sau: 3…..If (ChuaTham[u]){ Truoc[u]:=v; push(queue,u); ChuaTham[u]=false;}Chú ý: Đường đi tìm theo BFS là đường đi ngắn nhất theo số cạnh từ s đến t nhưng DFS thì không.b) Tìm các thành phần liên thông của đồ thị:Hãy cho biết đồ thị gồm bao nhiêu thành phần liên thông và từng thành phần liên thông của nó là gồmnhững đỉnh nào?* Ý tưởng:- Số thành phần liên thông bằng số lần gọi đến thủ tục DFS1() hoặc BFS1().- Ta dùng biến numConnect để đếm số thành phần liên thông và dùng biến Index[v] để ghi nhận chỉ số của thành phần liên thông chứa đỉnh v (có thể dùng biến ChuaTham[v] thay cho biến Index[v] )BÀI TẬP CHƯƠNG 3* Bài 1 : Các miền trên bảngCho một bảng chữ nhật chia thành MxN ô vuông (M dòng, N cột). Mỗi ô vuông ghi một số nguyêndương (trong khoảng từ 1 đến 255). Một miền của ...