Bài giảng Lý thuyết đồ thị: Chương 6 - PGS.TS. Hoàng Chí Thành

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:37

Thêm vào BST

Báo xấu

15
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Lý thuyết đồ thị: Chương 6 Các thuật toán duyệt đồ thị, cung cấp cho người đọc những kiến thức như: 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ị. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Lý thuyết đồ thị: Chương 6 - PGS.TS. Hoàng Chí Thành

CHƯƠNG 6 CÁC THUẬT TOÁN DUYỆT ĐỒ THỊ 1
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ị 2
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 3
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. 4
VÍ DỤ 5.1 3 2 D 4 B H 1 5 A E 8 G 6 C 7 F Thứ tự duyệt: A, B, D, H, E, G, F, C 5
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
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. 7
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. 8
VÍ DỤ 6.2 Thứ tự duyệt của các đỉnh trên đồ thị: 13 14 6 8 2 12 1 3 11 5 9 7 4 10 15 9
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 10
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. 11
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 ; 12
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. 13
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 14
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 } 15
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 15 end ; 16 pop(S) {Loại bỏ phần tử ở đỉnh của S} 17 end 18 end ; 16
VÍ DỤ 6.3 Đồ thị và quá trình duyệt theo chiều sâu 2 5 8 1 6 3 9 4 7 10 17
6.4. DUYỆT ĐỒ THỊ THEO CHIỀU RỘNG Danh sách DS được tổ chức theo kiểu hàng đợi (danh sách vào trước - ra trước – FIFO). - Việc duyệt có tính chất “lan rộng”. - Đỉnh được duyệt xong ngay sau khi ta đã xét hết tất cả các đỉnh kề với nó. - Đỉnh được xét càng sớm thì sớm trở thành duyệt xong. 1
VÍ DỤ 6.4 Duyệt đồ thị theo chiều rộng: 8 9 1 1 2 5 1 3 1 3 6 1 1 1 0 2 5 7 14 4 2
6.4. DUYỆT ĐỒ THỊ THEO CHIỀU RỘNG (tiếp)  Thuật toán 6.3 (Breadth-First Search ) 1 procedure D_RONG (v) ; 2 begin 3 Q :=  ; 4 enqueue v into Q ; { Nạp v vào cuối hàng đợi Q } 5 Duyet [v] := true ; 6 while Q   do 7 begin 8 dequeue z from Q ; { Loại z ra khỏi đầu hàng đợi Q} 3