Bài giảng Toán rời rạc 2 - Chương 3: Tìm kiếm trên đồ thị
TÌM KIẾM TRÊN ĐỒ THỊ
Toán rời rạc 2
Nội dung
• Thuật toán tìm kiếm theo chiều sâu trên đồ thị.
• Thuật toán tìm kiếm theo chiều rộng trên đồ thị.
• Ứng dụng của thuật toán tìm kiếm theo chiều sâu.
• Ứng dụng của thuật toán tìm kiếm theo chiều rộng.
2
Thuật toán tìm kiếm theo chiều
sâu (Depth First Search)
DFS
Tư tưởng
• Trong quá trình tìm kiếm, ưu tiên “chiều sâu” hơn “chiều
rộng”
– Đi xuống sâu nhất có thể trước khi quay lại
• Bắt đầu tại một đỉnh v0 nào đó, chọn một đỉnh u bất kỳ
kề với v0 và lấy nó làm đỉnh duyệt tiếp theo.
– Cách duyệt tiếp theo được thực hiện tương tự như đối với đỉnh
v0 với đỉnh bắt đầu là u.
• Để kiểm tra việc duyệt mỗi đỉnh đúng một lần, chúng ta
sử dụng một mảng chuaxet[] gồm n phần tử (tương ứng
với n đỉnh):
– Nếu đỉnh thứ u đã được duyệt, phần tử tương ứng trong mảng
chuaxet[u] có giá trị FALSE.
– Ngược lại, nếu đỉnh chưa được duyệt, phần tử tương ứng trong
mảng có giá trị TRUE.
4
Biểu diễn thuật toán DFS
• DFS(u) có thể được mô tả bằng thủ tục đệ qui như sau:
Thuật toán DFS (u): //u là đỉnh bắt đầu duyệt
Begin
<Thăm đỉnh u>; //Duyệt đỉnh u
chuaxet[u] := FALSE; //Xác nhận đỉnh u đã duyệt
for each v Ke(u) do //Lấy mỗi đỉnh v Ke(u).
If (chuaxet[v] ) then //Nếu đỉnh v chưa duyệt
DFS(v); //Duyệt theo chiều sâu bắt từ đỉnh v
EndIf;
EndFor;
End.
5
Thuật toán DFS(u) dùng ngăn xếp
(khử đệ qui)
6
Độ phức tạp thuật toán DFS
• Độ phức tạp thuật toán DFS(u) phụ thuộc vào
phương pháp biểu diễn đồ thị
– Độ phức tạp thuật toán là O(n2) trong trường hợp đồ
thị biểu diễn dưới dạng ma trận kề, với n là số đỉnh
của đồ thị.
– Độ phức tạp thuật toán là O(n.m) trong trường hợp
đồ thị biểu diễn dưới dạng danh sách cạnh, với n là
số đỉnh của đồ thị, m là số cạnh của đồ thị.
– Độ phức tạp thuật toán là O(max(n, m)) trong trường
hợp đồ thị biểu diễn dưới dạng danh sách kề, với n là
số đỉnh của đồ thị, m là số cạnh của đồ thị.
7
Kiểm nghiệm thuật toán DFS (1/3)
• Ví dụ 1: Cho đồ thị gồm 13 đỉnh như hình vẽ.
Hãy kiểm nghiệm thuật toán DFS(1).
8
Kiểm nghiệm thuật toán DFS (2/3)
9
Kiểm nghiệm thuật toán DFS (3/3)
10
Ví dụ 2
• Cho đồ thị gồm 13
đỉnh được biểu diễn
dưới dạng ma trận kề
như hình bên phải.
Hãy cho biết kết quả
thực hiện thuật toán
trong DFS bắt đầu tại
đỉnh u=1? Chỉ rõ trạng
thái của ngăn xếp và
tập đỉnh được duyệt
theo mỗi bước thực
hiện của thuật toán?
11
Ví dụ 2: Kiểm nghiệm thuật toán DFS(1)
12
Cài đặt thuật toán
• Hàm Init(): đọc dữ liệu theo khuôn dạng từ file dothi.in và thiết
lập mảng chuaxet[u] =True (u=1, 2,..,n).
• Hàm DFS_Dequi: Cài đặt thuật toán DFS(u) bằng đệ qui.
• Hàm DFS_Stack: Cài đặt thuật toán DFS(u) dựa vào stack.
13
Xem code minh họa
Thuật toán tìm kiếm theo chiều
rộng (Breadth First Search)
Tư tưởng
• Trong quá trình tìm kiếm, ưu tiên “chiều rộng” hơn “chiều
sâu”
• Tìm kiếm xung quanh trước khi đi xuống sâu hơn
• Đỉnh được nạp vào hàng đợi đầu tiên là u
– Các đỉnh kề với u là ( v1, v2, . . ., vk) được nạp vào hàng đợi nếu
như nó chưa được xét đến.
• Quá trình duyệt tiếp theo được bắt đầu từ các đỉnh còn
có mặt trong hàng đợi.
• Thuật toán dừng khi hàng đợi rỗng.
15
Thuật toán BFS
16
Độ phức tạp thuật toán BFS
• Độ phức tạp thuật toán BFS(u) phụ thuộc vào
phương pháp biểu diễn đồ thị
– Độ phức tạp thuật toán là O(n2) trong trường hợp đồ
thị biểu diễn dưới dạng ma trận kề, với n là số đỉnh
của đồ thị.
– Độ phức tạp thuật toán là O(n.m) trong trường hợp
đồ thị biểu diễn dưới dạng danh sách cạnh, với n là
số đỉnh của đồ thị, m là số cạnh của đồ thị.
– Độ phức tạp thuật toán là O(max(n, m)) trong trường
hợp đồ thị biểu diễn dưới dạng danh sách kề, với n là
số đỉnh của đồ thị, m là số cạnh của đồ thị.
17
Kiểm nghiệm thuật toán BFS (1/2)
• Ví dụ 3. Cho đồ thị
gồm 13 đỉnh được
biểu diễn dưới dạng
ma trận kề như hình
bên phải. Hãy cho biết
kết quả thực hiện thuật
toán BFS bắt đầu tại
đỉnh u=1? Chỉ rõ trạng
thái của hàng đợi và
tập đỉnh được duyệt
theo mỗi bước thực
hiện của thuật toán?
18
Kiểm nghiệm thuật toán BFS (2/2)
19
Lưu ý
• Với đồ thị vô hướng
– Nếu DFS(u) = V hoặc BFS(u) = V, ta có thể kết
luận đồ thị liên thông
• Với đồ thị có hướng
– Nếu DFS(u) = V hoặc BFS(u) = V, ta có thể kết
luận đồ thị liên thông yếu
20
Tải về để xem bản đầy đủ
52 trang
27760
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc 2 - Chương 3: Tìm kiếm trên đồ thị", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_toan_roi_rac_2_chuong_3_tim_kiem_tren_do_thi.pdf
