Bài giảng Toán rời rạc 2 - Chương 3: Tìm kiếm trên đồ thị - Ngô Xuân Bách
Học viện Công nghệ Bưu chính Viễn thông
Khoa Công nghệ thông tin 1
Toán rời rạc 2
Tìm kiếm trên đồ thị
Ngô Xuân Bách
Nội dung
Thuật toán tìm kiếm theo chiều sâu (Depth-First Search) - DFS)
Thuật toán tìm kiếm theo chiều rộng (Breadth-First Search - BFS)
Một số ứng dụng của DFS và BFS
2
Tìm kiếm theo chiều sâu - DFS
Tư tưởng
o Trong quá trình tìm kiếm, ưu tiên “chiều sâu” hơn “chiều rộng”
o Đi xuống sâu nhất có thể trước khi quay lại
Thuật toán
DFS(푢){ //푢 là đỉnh bắt đầu duyệt
<Thăm đỉnh 푢>; //duyệt đỉnh 푢
푐ℎ푢푎푥푒푡,푢- = 푓푎푙푠푒; //xác nhận đỉnh 푢 đã duyệt
for(푣 ∈ 퐾푒(푢)){
if( 푐ℎ푢푎푥푒푡,푣-)
//nếu 푣 chưa được duyệt
DFS(푣); //duyệt theo chiều sâu từ 푣
}
}
3
DFS sử dụng ngăn xếp
DFS(푢){
Bước 1: Khởi tạo
푠푡푎푐푘 = ∅; //khởi tạo 푠푡푎푐푘 là ∅
p푢푠ℎ(푠푡푎푐푘, 푢); //đưa đỉnh 푢 vào ngăn xếp
<Thăm đỉnh 푢>; //duyệt đỉnh 푢
푐ℎ푢푎푥푒푡,푢- = 푓푎푙푠푒; //xác nhận đỉnh 푢 đã duyệt
Bước 2: Lặp
while(푠푡푎푐푘 ≠ ∅){
푠 = p표푝(푠푡푎푐푘); //lấy đỉnh ở đầu ngăn xếp
for(푡 ∈ 퐾푒(푠)){
if( 푐ℎ푢푎푥푒푡,푡-){ //nếu 푡 chưa được duyệt
<Thăm đỉnh 푡>; //duyệt đỉnh 푡
푐ℎ푢푎푥푒푡,푡- = 푓푎푙푠푒; //푡 đã duyệt
p푢푠ℎ(푠푡푎푐푘, 푠); //đưa 푠 vào ngăn xếp
p푢푠ℎ(푠푡푎푐푘, 푡); //đưa 푡 vào ngăn xếp
beak; //chỉ lấy một đỉnh 푡
}
}
}
Bước 3: Trả lại kết quả
return <tập đỉnh đã duyệt>;
}
4
Độ phức tạp thuật toán DFS
Độ phức tạp thuật toán DFS(푢) phụ thuộc vào phương
pháp biểu diễn đồ thị
Biểu diễn đồ thị bằng ma trận kề
o Độ phức tạp thuật toán là 푂(푛2), 푛 là số đỉnh
Biểu diễn đồ thị bằng danh sách cạnh
o Độ phức tạp thuật toán là 푂(푛. 푚), 푛 là số đỉnh, 푚 là số cạnh
Biểu diễn đồ thị bằng danh sách kề
o Độ phức tạp thuật toán là 푂(max(푛, 푚)), 푛 là số đỉnh, 푚 là số
cạnh
5
Kiểm nghiệm thuật toán DFS (1/2)
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).
(Phương ND, 2013)
6
Kiểm nghiệm thuật toán DFS (2/2)
STT
Trạng thái ngăn xếp
Danh sách đỉnh được duyệt
1
2
1
1
1, 2
1, 2
1, 2, 4
3
1, 2, 4
1, 2, 4, 3
1, 2, 4
1, 2, 4, 6
4
1, 2, 4, 3
5
1, 2, 4, 3
6
1, 2, 4, 3, 6
7
1, 2, 4, 6, 7
1, 2, 4, 3, 6, 7
8
1, 2, 4, 6
1, 2, 4, 3, 6, 7
9
1, 2, 4, 6, 8
1, 2, 4, 3, 6, 7, 8
10
11
12
13
14
15
1, 2, 4, 6, 8, 10
1, 2, 4, 3, 6, 7, 8, 10
1, 2, 4, 3, 6, 7, 8, 10, 5
1, 2, 4, 3, 6, 7, 8, 10, 5, 9
1, 2, 4, 3, 6, 7, 8, 10, 5, 9, 13
1, 2, 4, 3, 6, 7, 8, 10, 5, 9, 13, 11
1, 2, 4, 3, 6, 7, 8, 10, 5, 9, 13, 11, 12
1, 2, 4, 6, 8, 10, 5
1, 2, 4, 6, 8, 10, 5, 9
1, 2, 4, 6, 8, 10, 5, 9, 13
1, 2, 4, 6, 8, 10, 5, 9, 13, 11
1, 2, 4, 6, 8, 10, 5, 9, 13, 11, 12
16- Lần lượt bỏ các đỉnh ra khỏi ngăn xếp
Kết quả duyệt: 1, 2, 4, 3, 6, 7, 8, 10, 5, 9, 13, 11, 12
7
Bài tập 1
Cho đồ thị gồm 13
đỉnh được biểu diễn
dưới dạng ma trận kề
như hình vẽ. Hãy cho
biết kết quả thực hiện
thuật toán DFS(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.
(Phương ND, 2013)
8
Nội dung
Thuật toán tìm kiếm theo chiều sâu (Depth-First Search) - DFS)
Thuật toán tìm kiếm theo chiều rộng (Breadth-First Search - BFS)
Một số ứng dụng của DFS và BFS
9
Tìm kiếm theo chiều rộng - BFS
Tư tưởng
o Trong quá trình tìm kiếm, ưu tiên “chiều rộng” hơn “chiều sâu”
o Tìm kiếm xung quanh trước khi đi xuống sâu hơn
Thuật toán
BFS(푢){
Bước 1: Khởi tạo
푞푢푒푢푒 = ∅; p푢푠ℎ(푞푢푒푢푒, 푢); 푐ℎ푢푎푥푒푡,푢- = 푓푎푙푠푒;
Bước 2: Lặp
while(푞푢푒푢푒 ≠ ∅){
푠 = p표푝(푞푢푒푢푒); <Thăm đỉnh 푠>;
for(푡 ∈ 퐾푒(푠)){
if( 푐ℎ푢푎푥푒푡,푡-){
p푢푠ℎ(푞푢푒푢푒, 푡); 푐ℎ푢푎푥푒푡,푡- = 푓푎푙푠푒;
}
}
}
Bước 3: Trả lại kết quả
return <tập đỉnh đã duyệt>;
}
10
Độ phức tạp thuật toán BFS
Độ phức tạp thuật toán BFS(푢) phụ thuộc vào phương
pháp biểu diễn đồ thị
Biểu diễn đồ thị bằng ma trận kề
o Độ phức tạp thuật toán là 푂(푛2), 푛 là số đỉnh
Biểu diễn đồ thị bằng danh sách cạnh
o Độ phức tạp thuật toán là 푂(푛. 푚), 푛 là số đỉnh, 푚 là số cạnh
Biểu diễn đồ thị bằng danh sách kề
o Độ phức tạp thuật toán là 푂(max(푛, 푚)), 푛 là số đỉnh, 푚 là số
cạnh
11
Kiểm nghiệm thuật toán BFS (1/2)
Cho đồ thị gồm 13
đỉnh được biểu diễn
dưới dạng ma trận kề
như hình vẽ. Hãy cho
biết kết quả thực hiện
thuật toán BFS(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.
(Phương ND, 2013)
12
Kiểm nghiệm thuật toán BFS (2/2)
STT
Trạng thái hàng đợi
Danh sách đỉnh được duyệt
1
2
1
∅
2, 3, 4
3, 4, 6
4, 6, 5
6, 5, 7
5, 7, 12
7, 12, 8
12, 8
8, 10
10
1
3
1, 2
4
1, 2, 3
5
1, 2, 3, 4
6
1, 2, 3, 4, 6
7
1, 2, 3, 4, 6, 5
8
1, 2, 3, 4, 6, 5, 7
9
1, 2, 3, 4, 6, 5, 7, 12
1, 2, 3, 4, 6, 5, 7, 12, 8
1, 2, 3, 4, 6, 5, 7, 12, 8, 10
1, 2, 3, 4, 6, 5, 7, 12, 8, 10, 9
1, 2, 3, 4, 6, 5, 7, 12, 8, 10, 9, 11
1, 2, 3, 4, 6, 5, 7, 12, 8, 10, 9, 11, 13
10
11
12
13
14
9, 11, 13
11, 13
13
∅
Kết quả duyệt: 1, 2, 3, 4, 6, 5, 7, 12, 8, 10, 9, 11, 13
13
Chú ý
Với đồ thị vô hướng
o Nếu 퐷퐹푆(푢) = 푉 hoặc 퐵퐹푆(푢) = 푉, ta có thể kết luận đồ thị liên
thông
Với đồ thị có hướng
o Nếu 퐷퐹푆(푢) = 푉 hoặc 퐵퐹푆(푢) = 푉, ta có thể kết luận đồ thị liên
thông yếu
14
Nội dung
Thuật toán tìm kiếm theo chiều sâu (Depth-First Search) - DFS)
Thuật toán tìm kiếm theo chiều rộng (Breadth-First Search - BFS)
Một số ứng dụng của DFS và BFS
15
Xác định thành phần liên thông của đồ thị
Phát biểu bài toán
o Cho đồ thị vô hướng 퐺 =< 푉, 퐸 >, trong đó 푉 là tập đỉnh, 퐸 là tập
cạnh. Xác định các thành phần liên thông của 퐺?
Thuật toán
Duyet-TPLT(){ //duyệt thành phần liên thông
Bước 1: Khởi tạo
푠표푇푃퐿푇 = 0; //khởi tạo số thành phần liên thông bằng 0
Bước 2: Lặp
for(푢 ∈ 푉){ //lặp trên tập đỉnh
if( 푐ℎ푢푎푥푒푡,푢-){
푠표푇푃퐿푇 = 푠표푇푃퐿푇 + 1;//ghi nhận số TPLT
푩푭푺(풖); // có thể gọi 푫푭푺 풖
<Ghi nhận các đỉnh thuộc TPLT>;
}
}
Bước 3: Trả lại kết quả
return <các TPLT>;
}
16
Bài tập 2
Cho đồ thị vô hướng
được biểu diễn dưới
dạng ma trận kề như
hình vẽ. Xác định các
thành phần liên thông
của đồ thị?
(Phương ND, 2013)
17
Tìm đường đi giữa các đỉnh trên đồ thị (1/4)
Phát biểu bài toán
o Cho đồ thị 퐺 =< 푉, 퐸 > (vô hướng hoặc có hướng), trong đó 푉 là
tập đỉnh, 퐸 là tập cạnh. Hãy tìm đường đi từ 푠 ∈ 푉 đến 푡 ∈ 푉?
Mô tả thuật toán
o Nếu 푡 ∈ 퐷퐹푆(푠) hoặc 푡 ∈ 퐵퐹푆(푠) thì ta có thể kết luận có đường đi
từ 푠 đến 푡 trên đồ thị, ngược lại sẽ không có đường đi
o Để ghi nhận đường đi ta sử dụng mảng 푡푟푢표푐,- gồm 푛 phần tử
(푛 = |푉|)
. Khởi tạo ban đầu 푡푟푢표푐 푢 = 0 với mọi 푢
. Mỗi khi đưa 푣 ∈ 퐾푒(푢) vào ngăn xếp (nếu sử dụng 퐷퐹푆) hoặc hàng đợi
(nếu sử dụng 퐵퐹푆) ta ghi nhận 푡푟푢표푐 푣 = 푢
. Nếu 퐷퐹푆 và 퐵퐹푆 không duyệt được đến đỉnh 푡, khi đó 푡푟푢표푐,푡- = 0 thì
ta kết luận không có đường đi từ 푠 đến 푡
18
Tìm đường đi giữa các đỉnh trên đồ thị (2/4)
Sử dụng thuật toán DFS
DFS(푠){
Bước 1: Khởi tạo
푠푡푎푐푘 = ∅; p푢푠ℎ(푠푡푎푐푘, 푠); 푐ℎ푢푎푥푒푡,푠- = 푓푎푙푠푒;
Bước 2: Lặp
while(푠푡푎푐푘 ≠ ∅){
푢 = p표푝(푠푡푎푐푘); //lấy đỉnh ở ngăn xếp
for(푣 ∈ 퐾푒(푢)){
if( 푐ℎ푢푎푥푒푡,푣-){ //nếu 푣 chưa được duyệt
푐ℎ푢푎푥푒푡,푣- = 푓푎푙푠푒; //푣 đã duyệt
p푢푠ℎ(푠푡푎푐푘, 푢); //đưa 푢 vào ngăn xếp
p푢푠ℎ(푠푡푎푐푘, 푣); //đưa 푣 vào ngăn xếp
풕풓풖풐풄,풗- = 풖; //Ghi nhận 푡푟푢표푐,푣- là 푢
beak; //chỉ lấy một đỉnh 푡
}
}
}
Bước 3: Trả lại kết quả
return <tập đỉnh đã duyệt>;
}
19
Tìm đường đi giữa các đỉnh trên đồ thị (3/4)
Sử dụng thuật toán BFS
BFS(푢){
Bước 1: Khởi tạo
푞푢푒푢푒 = ∅; p푢푠ℎ(푞푢푒푢푒, 푠); 푐ℎ푢푎푥푒푡,푠- = 푓푎푙푠푒;
Bước 2: Lặp
while(푞푢푒푢푒 ≠ ∅){
푢 = p표푝(푞푢푒푢푒);
for(푣 ∈ 퐾푒(푢)){
if( 푐ℎ푢푎푥푒푡,푣-){
p푢푠ℎ(푞푢푒푢푒, 푣);
푐ℎ푢푎푥푒푡,푣- = 푓푎푙푠푒;
풕풓풖풐풄 풗 = 풖;
}
}
}
Bước 3: Trả lại kết quả
return <tập đỉnh đã duyệt>;
}
20
Tải về để xem bản đầy đủ
32 trang
36161
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ị - Ngô Xuân Bách", để 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_ngo_x.pdf
