Bài 7: Duyệt đồ thị

Tham khảo Video sau đây :

1. Duyệt theo chiều sâu (`DFS`)

🤔 Ý TƯỞNG

Khởi điểm từ một đỉnh, đi theo các cạnh xa nhất có thể.

Trở lại định sau của cạnh xa nhất, tiếp tục duyệt như trước cho tới đến đỉnh cuối cùng.

Ví dụ

💡 MẸO

Được xuất phát từ đỉnh bất kỳ, nhưng nên chọn nhỏ nhất

Chọn a ⇨ b ⇨ c ⇨ g ⇨ d ⇨ e ⇨ f ⇨ h (nhỏ tới lớn)

hoặc

Chọn a ⇨ g ⇨ e ⇨ b ⇨ h ⇨ e ⇨ f ⇨ d (lớn tới nhỏ)

🤔 Ý TƯỞNG

Đinh "gần" ưu tiên thăm trước

Ví dụ

💡 MẸO

Được xuất phát từ đỉnh bất kỳ, nhưng nên chọn nhỏ nhất

Chọn a ⇨ b ⇨ c ⇨ g ⇨ d ⇨ h ⇨ e ⇨ f

hoặc

Chọn d ⇨ h ⇨ e ⇨ b ⇨ f ⇨ c ⇨ a ⇨ g

💡 FACT

Thực chất BFS theo cơ chế Hàng đợi còn DFS theo cớ chế Ngăn Xếp