Bài giảng Lý thuyết đồ thị - Chương 3: Duyệt đồ thị - Trần Cao Đệ

Nội dung text: Bài giảng Lý thuyết đồ thị - Chương 3: Duyệt đồ thị - Trần Cao Đệ

1. Chương 3 Duyệt đồ thị
2. Nội dung ⚫ 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. Duyệt đồ thị là gì? ⚫ 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ụ 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. Thuật toán duyệt ⚫ 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. Thuật toán duyệt (tt) ⚫ 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. Duyệt chiều sâu (Depth First Search) ⚫ 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ụ (DFS)
9. Tư tưởng giải thuật 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. Giải thuật DFS ⚫ 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. Giải thuật DFS (tt) 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 ; 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.
12. Giải thuật DFS (tt) 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
13. Giải thuật DFS (tt) 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 } 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 ;
14. Ví dụ ⚫ Kết quả duyệt chiều sâu: 2 5 8 1 6 3 9 4 7 10
15. Giải thuật BFS (Breadth First Search) ⚫ 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.
16. Ví dụ 8 9 11 1 2 5 4 6 1 3 10 1 15 2 7 13 4
17. Giải thuật BFS ⚫ 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} 9 Thăm_đỉnh (z) ; 10 for u DK[z] do 11 if ! Duyet [u] then 12 begin 13 enqueue u into Q ; 14 Duyet [u] := true 15 end 16 end 17 end ;
18. Ví dụ 2 5 8 1 6 3 9 4 7 10