1
Chương 3
Các Thuật Toán Duyệt Đồ Thị
(Graph Searching, Graph Traversal)
2
Các thuật toán duyệt đồ thị
•Duyệt đồ thị: Graph Searching hoặc Graph Traversal
•Duyệt qua mỗi đỉnh và mỗi cạnh của đồ thị
•Ứng dụng:
•Cần để khảo sát các tính chất của đồ thị
•Là thành phần cơ bản của nhiều thuật toán trên đồ thị
•Hai thuật toán duyệt cơ bản:
•Tìm kiếm theo chiều rộng (Breadth First Search – BFS)
•Tìm kiếm theo chiều sâu (Depth First Search – DFS)
3
Ý tưởng chung của các thuật toán duyệt
Ý tưởng chung:
•Trong quá trình thực hiện thuật toán, mỗi đỉnh ở một trong ba trạng thái:
•Chưa thăm, thể hiện bởi màu trắng
•Đã thăm (nhưng chưa duyệt xong), thể hiện bởi màu xám
•Đã duyệt xong, thể hiện bởi màu đen
•Trạng thái của đỉnh sẽ biến đổi theo qui tắc sau:
•Thoạt đầu mỗi đỉnh đều có màu trắng (chưa thăm - not visited).
•Đỉnh đã được thăm sẽ chuyển thành màu xám (trở thành đã thăm nhưng chưa duyệt
xong - visited).
•Khi tất cả các đỉnh kề của một đỉnh vlà đã được thăm, đỉnh vsẽ có màu đen (đã
duyệt xong – discovered).
4
Tìm kiếm theo chiều rộng
Breadth-first Search (BFS)
5
Tìm kiếm theo chiều rộng
Breadth-first Search
•Input: Đồ thị G = (V, E),vô hướng hoặc có hướng.
•Output:
•d[v]=khoảng cách (độ dài của đường đi ngắn nhất) từ s(là
đỉnh xuất phát tìm kiếm) đến v, với mọi vV.d[v]=nếu v
không đạt tới được từ s.
•
[v]=uđỉnh đi trước vtrong đường đi từ s(là đỉnh xuất phát
tìm kiếm) đến vcó độ dài d[v].
•Xây dựng cây BFS với gốc tại schứa tất cả các đỉnh đạt tới được
từ s.