Bài giảng Toán rời rạc - Chương 3: Duyệt đồ thị

Chương 3Duyệt đồ thịNội dungKhái niệm duyệt đồ thịThuật toán duyệt đồ thịDuyệt đồ thị theo chiều sâuDuyệt đồ thị theo chiều rộngDuyệ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.Ví dụABDHCEGF12345678Thứ tự duyệt: A, B, D, H, E, G, F, C	Thuật toán duyệtCho đồ 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.Thuật toán duyệt (tt)Thuật toán1)     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 DS5)     Nếu DS   thì quay lên bước 2)6)     Dừng.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.Ví dụ (DFS)Tư tưởng giải thuật1. 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úcGiải thuật DFSThuậ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.Giải thuật DFS (tt)Thuật toán 6.11 procedure D_SAU (v) ;2 begin3	 Thăm_đỉnh (v) ;4	 Duyet [v] := true ; 5	 for u  DK[v] do6	 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.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ánGiải thuật DFS (tt)Thuật toán cải tiến: 1 procedure D_SAU_2 (v) ;2 begin3 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   do8 begin9	 while  u  DK[top(S)] do10	 if ! Duyet [u] then11	 begin12	 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ụKết quả duyệt chiều sâu:12583647910Giả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.Ví dụ735610111214151213894Giải thuật BFSThuật toán 6.3 (Breadth-First Search )1 procedure D_RONG (v) ;2 begin3	 Q :=  ;enqueue v into Q ; { Nạp v vào cuối hàng đợi Q }5	Duyet [v] := true ;6	while Q   do7	 begin 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] do11	if ! Duyet [u] then12	 	 begin13	 enqueue u into Q ;14	 Duyet [u] := true 15	 end 16	 end 17 end ;Ví dụ12583647910