1
CHƯƠNG 6
CÁC THUẬT TOÁN
DUYỆT ĐỒ THỊ
2
NỘI DUNG
Cá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ị
3
6.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âu
Duyệt đồ thị theo chiều rộng
4
KHÁ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.
5
VÍ DỤ 5.1
A
B
D
H
C
EG
F
1
234
5
6
7
8
Thứ tự duyệt: A, B, D, H, E, G, F, C