JavaScript is required

Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(G) là:

Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(G) là:  (ảnh 1)

 

A.

G, H, I, N, K, B, A, C, D, E, F

B.

G, H, N, K, B, A, D, C, E, F, I

C.

G, H, N, K, B, A, C, D, E, I, F

D.

G, A, B, C, D, E, F, N, K, H, I

Trả lời:

Đáp án đúng: B


Thuật toán DFS (Depth-First Search - Tìm kiếm theo chiều sâu) duyệt đồ thị bằng cách đi sâu vào từng nhánh của đồ thị cho đến khi không còn đỉnh kề chưa được thăm, sau đó quay lui (backtrack) để khám phá các nhánh khác. Trong trường hợp này, bắt đầu từ đỉnh G, ta có thể duyệt theo thứ tự sau: 1. **G:** Bắt đầu từ đỉnh G. 2. **H:** Duyệt đến đỉnh H kề với G. 3. **N:** Duyệt đến đỉnh N kề với H. 4. **K:** Duyệt đến đỉnh K kề với N. 5. **B:** Duyệt đến đỉnh B kề với K. 6. **A:** Duyệt đến đỉnh A kề với B. 7. **C:** Duyệt đến đỉnh C kề với A. 8. **D:** Duyệt đến đỉnh D kề với C. 9. **E:** Duyệt đến đỉnh E kề với D. 10. **I:** Duyệt đến đỉnh I kề với K. 11. **F:** Duyệt đến đỉnh F kề với E. Vậy, thứ tự duyệt đúng là: G, H, N, K, B, A, C, D, E, I, F

Câu hỏi liên quan