JavaScript is required

Cho đồ thị vô hướng G. Hỏi kết luận “duyệt theo chiều sâu trên G từ đỉnh s luôn cho ta đường đi ngắn nhất theo số cạnh từ s đến tất cả các đỉnh cùng thành phần liên thông với s” là đúng hay sai?

A.

SAI

B.
B. ĐÚNG
Trả lời:

Đáp án đúng: B


Duyệt theo chiều sâu (DFS) không đảm bảo tìm được đường đi ngắn nhất (theo số cạnh) giữa hai đỉnh trong đồ thị vô hướng. DFS tập trung vào việc khám phá sâu vào một nhánh trước khi quay lui, do đó có thể tìm thấy một đường đi dài hơn đường đi ngắn nhất có thể có. Đường đi ngắn nhất theo số cạnh thường được tìm bằng thuật toán tìm kiếm theo chiều rộng (BFS).

Câu hỏi liên quan