Chương 3: Tìm kiếm trên đồ thị
2
Chương 3 – Tìm kiếm trên đồ thị
Nội dung
Duyệt đồ thịtheo chiều rộng
Duyệt đồ thịtheo chiều sâu
I.
II.
Tìm đường đi
III.
Kiểm tra tính liên thông
IV.
Lý thuyết đồ thị
2
3
Chương 3 – Tìm kiếm trên đồ thị
I. Duyệt đồ thịtheo chiều sâu
Giới thiệu
Duyệt đồ thịlà quá trình đi qua tất cảcác đỉnh của đồ
thịsao cho mỗi đỉnh của nó được viếng thăm đúng
một lần.
Duyệt theo chiều sâu (Depth First Search – DFS)
Duyệt theo chiều rộng (Breadth First Search – BFS)
4
Chương 3 – Tìm kiếm trên đồ thị
I. Duyệt đồ thịtheo chiều sâu
Nguyên lý
Bắt đầu tìm kiếm từmột đỉnh v nào đócủa đồ thị.
Sau đóchọn u là một đỉnh tùy ý kềvới v (với đồ thịcó
hướng thì u là đỉnh sau, v là đỉnh đầu của cung uv)
Lặp lại quá trình này với u cho đến khi không tìm được
đỉnh kềtiếp theo nữa thì trởvềđỉnh ngay trước đỉnh mà
không thể đi tiếp để tìm qua nhánh khác.
5
Chương 3 – Tìm kiếm trên đồ thị
I. Duyệt đồ thịtheo chiều sâu
Thứtựduyệt:
d c b a
g k l
h
f m
e