DUYỆT ĐỒ THỊ THEO CHIỀU RỘNG

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.
VÍ DỤ 6.4
Duyệt đồ thị theo chiều rộng:
7
3
5
6
10
11
12
13
15
1
2
14
8
9
4
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 :=  ;
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
dequeue z from Q ; { Loại z ra khỏi
đầu hàng đợi Q}
6.4. DUYỆT ĐỒ THỊ THEO CHIỀU RỘNG (tiếp)
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 ;

6.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).

VÍ DỤ 6.5
Đồ thị và quá trình duyệt theo chiều rộng:
1
2
5
8
3
6
4
7
9
10
6.5. MỘT SỐ ỨNG DỤNG
CỦA PHÉP DUYỆT ĐỒ THỊ

Bài toán đường đi
Bài toán tìm các mảng liên thông
BÀI TOÁN ĐƯỜNG ĐI
Cho 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ó).
BÀ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.
BÀ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.

BÀ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] then
12 begin
13 enqueue u into Q ;
14 Duyet [u] := true ; Truoc [u] := z
15 end ;
BÀ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.

VÍ DỤ 6.6
Đồ thị và quá trình duyệt theo chiều rộng:













Đường đi từ 1  10: 10  9  6  2  1
BÀI TOÁN TÌM CÁC MẢNG
LIÊN THÔNG
Bà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.
1
2
4
3
5
6
7
8
9
BÀ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.
BÀ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).

BÀ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 .
BÀ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.
VÍ DỤ 6.7
Xét đồ thị:
VÍ DỤ 6.7 (tiếp)
Quá trình duyệt và tìm các mảng liên thông: