Duyệt đồ thị BFS và DFS: thứ tự khám phá, cấu trúc biên và trạng thái đã thăm

🕸️ Đồ thị có nhánh và chu trình

Đồ thị gồm đỉnh và cạnh. Duyệt là quá trình thăm có hệ thống các đỉnh có thể tới từ điểm bắt đầu. Vì một đỉnh có thể được tiếp cận qua nhiều đường hoặc chu trình, cần trạng thái đã thăm để tránh xử lí lặp vô hạn.

BFS và DFS

• BFS: dùng hàng đợi FIFO; khám phá các đỉnh theo số cạnh tăng dần từ nguồn. Trong đồ thị không trọng số, cây cha BFS cho đường đi ít cạnh nhất.
• DFS: dùng ngăn xếp tường minh hoặc đệ quy; đi sâu rồi quay lui. Hữu ích cho phát hiện thành phần, chu trình và thứ tự phụ thuộc trong các biến thể phù hợp.

Đánh dấu lúc nào?

Với BFS, thường đánh dấu khi đưa đỉnh vào hàng đợi để một đỉnh không bị xếp hàng nhiều lần. Lưu mảng cha giúp dựng lại đường đi; chỉ lưu visited thì biết khả năng tới nhưng không biết tuyến cụ thể.

⚠️ Đường ngắn nhất phụ thuộc trọng số

BFS tối ưu số cạnh khi mọi cạnh có chi phí như nhau. Nếu cạnh có trọng số dương khác nhau, cần thuật toán phù hợp như Dijkstra; DFS đầu tiên tới đích không bảo đảm ngắn nhất.