CÁC THUẬT TOÁN DUYỆT ĐỒ THỊ

CHƯƠNG 6


CÁC THUẬT TOÁN
DUYỆT ĐỒ THỊ
NỘI DUNG
Các thuật toán duyệt đồ thị
Một số ứng dụng của các thuật toán duyệt đồ thị
6.1. CÁC PHÉP DUYỆT ĐỒ THỊ
Khái niệm duyệt đồ thị
Thuật toán duyệt đồ thị
Duyệt đồ thị theo chiều sâu
Duyệt đồ thị theo chiều rộng
KHÁI NIỆM DUYỆT ĐỒ THỊ
Duyệt đồ thị là một cách liệt kê tất cả các đỉnh của đồ thị thành một danh sách tuyến tính.
Cho một cách “đi qua” tất cả các đỉnh của đồ thị để
truy nhập, thêm bớt thông tin …
- Duyệt đồ thị không phụ thuộc vào hướng của cạnh.

VÍ DỤ 5.1
6.2. THUẬT TOÁN DUYỆT ĐỒ THỊ
Cho đồ thị G = (V, E) với x0 là một đỉnh của G.

Dùng một cấu trúc dữ liệu kiểu danh sách, kí hiệu là DS, để chứa các đỉnh.
6.2. THUẬT TOÁN DUYỆT ĐỒ THỊ (tiếp)
Thuật toán
1)     Khởi đầu: DS  {x0}
2)     Lấy đỉnh x ra khỏi đầu DS
3)     Duyệt đỉnh x
4) Nạp các đỉnh của F(x) vào DS
5)     Nếu DS   thì quay lên bước 2)
6)     Dừng.
6.3. DUYỆT ĐỒ THỊ THEO CHIỀU SÂU
Danh sách DS được tổ chức theo kiểu stack (danh sách vào sau – ra trước – LIFO).
Mỗi lần duyệt một đỉnh ta duyệt đến tận cùng mỗi nhánh rồi mới chuyển sang duyệt nhánh khác.
VÍ DỤ 6.2
Thứ tự duyệt của các đỉnh trên đồ thị:
6.3. DUYỆT ĐỒ THỊ THEO CHIỀU SÂU (tiếp)
1. Bắt đầu duyệt từ một đỉnh x0 nào đó của đồ thị.
2. Chọn x là đỉnh kề nào đó của x0 và lặp lại quá trình duyệt đối với đỉnh x. Giả sử đang xét đỉnh x.
- Nếu tìm được đỉnh y chưa được duyệt thì xét đỉnh này và bắt đầu từ đó tiếp tục quá trình duyệt
- Nếu không còn đỉnh kề với x chưa được duyệt thì nói rằng đỉnh x đã duyệt xong, quay trở lại tiếp tục duyệt từ đỉnh mà từ đó đến được đỉnh x
- Nếu quay trở lại đúng đỉnh x0 thì phép duyệt kết thúc
6.3. DUYỆT ĐỒ THỊ THEO CHIỀU SÂU (tiếp)
Thuật toán 6.1 (Depth-First Search)
Dữ liệu: Biểu diễn mảng DK các danh sách kề của
đồ thị vô hướng G.
Kết quả: Danh sách các đỉnh của đồ thị G.

6.3. DUYỆT ĐỒ THỊ THEO CHIỀU SÂU (tiếp)
Thuật toán 6.1
1 procedure D_SAU (v) ;
2 begin
3 Thăm_đỉnh (v) ;
4 Duyet [v] := true ;
5 for u  DK[v] do
6 if ! Duyet [u] then D_SAU (u) ;
7 end ;
6.3. DUYỆT ĐỒ THỊ THEO CHIỀU SÂU (tiếp)

8 BEGIN { Chương trình chính }
9 for v  V do Duyet [v] := false ;
10 for v  V do
11 if ! Duyet [v] then D_SAU (v)
12 END.

6.3. DUYỆT ĐỒ THỊ THEO CHIỀU SÂU (tiếp)
Nhận xét:
- Độ phức tạp: O(n+m)
- Đỉnh được thăm càng muộn càng sớm trở thành duyệt xong.
- Dùng một ngăn xếp lưu trữ các đỉnh đang duyệt để cải tiến thuật toán


6.3. DUYỆT ĐỒ THỊ THEO CHIỀU SÂU (tiếp)
Thuật toán cải tiến:
1 procedure D_SAU_2 (v) ;
2 begin
3 S :=  ;
4 Thăm_đỉnh (v) ;
5 Duyet [v] := true ;
6 push v onto S ; {Nạp v lên đỉnh của S }
6.3. DUYỆT ĐỒ THỊ THEO CHIỀU SÂU (tiếp)
7 while S   do
8 begin
9 while  u  DK[top(S)] do
10 if ! Duyet [u] then
11 begin
12 Thăm_đỉnh (u) ;
13 Duyet [u] := true ;
14 push u onto S
end ;
16 pop(S) {Loại bỏ phần tử ở đỉnh của S}
17 end
18 end ;

VÍ DỤ 6.3
Đồ thị và quá trình duyệt theo chiều sâu