Bài giảng Tin học: Các thuật toán duyệt đồ thị

CHƯƠNG 6CÁC THUẬT TOÁN DUYỆT ĐỒ THỊ1NỘI DUNGCá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ị26.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âuDuyệt đồ thị theo chiều rộng3KHÁ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.4VÍ DỤ 5.1ABDHCEGF12345678Thứ tự duyệt: A, B, D, H, E, G, F, C	56.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.66.2. THUẬT TOÁN DUYỆT ĐỒ THỊ (tiếp)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.76.3. DUYỆT ĐỒ THỊ THEO CHIỀU SÂUDanh 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.8VÍ DỤ 6.2Thứ tự duyệt của các đỉnh trên đồ thị:43121156789121013141596.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úc106.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.116.3. DUYỆT ĐỒ THỊ THEO CHIỀU SÂU (tiếp)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 ;126.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.136.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án146.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 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 }156.3. DUYỆT ĐỒ THỊ THEO CHIỀU SÂU (tiếp) 	 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 ;16VÍ DỤ 6.3Đồ thị và quá trình duyệt theo chiều sâu1258364791017