Bài giảng Duyệt đồ thị theo chiều rộng

6.4. DUYỆT ĐỒ THỊ THEO CHIỀU RỘNGDanh 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.1VÍ DỤ 6.4Duyệt đồ thị theo chiều rộng:73561011121315121489426.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 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}36.4. DUYỆT ĐỒ THỊ THEO CHIỀU RỘNG (tiếp)	 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 ;46.4. DUYỆT ĐỒ THỊ THEO CHIỀU RỘNG (tiếp)	18 BEGIN {Chương trình chính }	19	 for v  V do Duyet [v] := false ;	20	 for v  V do 	21	 if ! Duyet [v] then D_RONG (v) ;	22 END .Độ phức tạp: O(n+m).5VÍ DỤ 6.5Đồ thị và quá trình duyệt theo chiều rộng:1258364791066.5. MỘT SỐ ỨNG DỤNG CỦA PHÉP DUYỆT ĐỒ THỊBài toán đường điBài toán tìm các mảng liên thông7BÀI TOÁN ĐƯỜNG ĐICho G = (V, E) là một đồ thị vô hướng và hai đỉnh a, b  V.Bài toán: Tìm đường đi từ đỉnh a đến đỉnh b trên đồ thị G (nếu có).8BÀI TOÁN ĐƯỜNG ĐI (tiếp)1. Thuật toán Warshall đã trả lời: có đường đi từ đỉnh a đến đỉnh b  AS[a, b] = true.2. Dùng phép duyệt đồ thị tìm đường đi (nếu có) từ đỉnh a đến đỉnh b.9BÀI TOÁN ĐƯỜNG ĐI (tiếp)Sau lời gọi thủ tục D_SAU(a) hoặc D_RONG(a) Nếu Duyet[b] = false thì không có đường đi từ đỉnh a đên đỉnh b.Nếu Duyet[b] = true thì b thuộc cùng mảng liên thông với a và có đường đi từ a đến b. Dùng thêm một biến mảng Truoc để khôi phục đường đi, Truoc [u] ghi đỉnh đến trước đỉnh u trên đường duyệt từ a tới u. 10BÀI TOÁN ĐƯỜNG ĐI (tiếp)Sửa dòng lệnh 6 trong thủ tục D_SAU(a)6 if ! Duyet [u] then begin Truoc [u] := v ; D_SAU(u) end ; Sửa các dòng lệnh 11-15 trong thủ tục D_RONG (v):11 if ! Duyet [u] then12 	begin 13	 enqueue u into Q ;14	 Duyet [u] := true ; Truoc [u] := z15	end ; 11BÀI TOÁN ĐƯỜNG ĐI (tiếp)Khôi phục đường đi cần tìm: b  a1 = Truoc[b]  a2 = Truoc[a1]  . . . .  aĐường đi tìm được theo thuật toán duyệt theo chiều rộng là đường đi ngắn nhất từ đỉnh a đến đỉnh b.12VÍ DỤ 6.6Đồ thị và quá trình duyệt theo chiều rộng:Đường đi từ 1  10: 10  9  6  2  11258364791013BÀI TOÁN TÌM CÁC MẢNG LIÊN THÔNGBài toán: Tìm số mảng liên thông p của đồ thị G và xác định xem mỗi mảng liên thông bao gồm những đỉnh nào.12435678914BÀI TOÁN TÌM CÁC MẢNG LIÊN THÔNG (tiếp)Do thủ tục D_SAU(v) hoặc D_RONG(v) duyệt tất cả các đỉnh thuộc cùng mảng liên thông với đỉnh v nên số mảng liên thông p của đồ thị G bằng số lần gọi các thủ tục D_SAU(v) hoặc D_RONG(v).	Dùng thêm biến mảng Mang[v] ghi chỉ số của mảng liên thông chứa v.15BÀI TOÁN TÌM CÁC MẢNG LIÊN THÔNG (tiếp)	Dùng biến p đếm số mảng liên thông và gán chỉ số cho các mảng liên thông tìm được. Khởi tạo: p := 0 ; Thêm lệnh gán: Mang [v] := p ; trong thủ tục Thăm_đỉnh(v). 16BÀI TOÁN TÌM CÁC MẢNG LIÊN THÔNG (tiếp)Sửa lại chương trình chính của thuật toán duyệt:1 BEGIN { Chương trình chính }2 for v  V do Duyet [v] := false ;3	 p := 0 ;4	 for v  V do 5	 if ! Duyet [v] then 6 	 begin p := p + 1 ; 7	 D_SAU (v) ; { D_RONG (v) ; }8 	 end 9 END .17BÀI TOÁN TÌM CÁC MẢNG LIÊN THÔNG (tiếp)Khi kết thúc chương trình: Biến p cho số mảng liên thông. Các giá trị Mang[v] , v  V cho phép liệt kê tất cả các đỉnh trong từng mảng liên thông.18VÍ DỤ 6.7Xét đồ thị:56789124319VÍ DỤ 6.7 (tiếp)Quá trình duyệt và tìm các mảng liên thông:20