Cho đồ thị vô hướng G = (V, E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E = {(1,2),(1,3),(1,6),(2,3),(2,5),(2,6),(4,5),(4,6),(5,6)}. Thực hiện phép duyệt đồ thị G theo chiều sâu (khi xét các đỉnh thì xét theo thứ tự từ điển). Hỏi thứ tự các đỉnh được thăm trong phép duyệt theo chiều sâu là thứ tự nào dưới đây?
Trả lời:
Đáp án đúng: B
Duyệt đồ thị theo chiều sâu (DFS - Depth First Search) bắt đầu từ đỉnh 1. Theo thứ tự từ điển, ta chọn đỉnh kề nhỏ nhất chưa được thăm.
1. Bắt đầu từ đỉnh 1, các đỉnh kề là 2, 3, 6. Chọn đỉnh 2.
2. Từ đỉnh 2, các đỉnh kề chưa thăm là 3, 5, 6. Chọn đỉnh 3.
3. Từ đỉnh 3, các đỉnh kề chưa thăm là 6. Chọn đỉnh 6.
4. Từ đỉnh 6, các đỉnh kề chưa thăm là 4, 5. Chọn đỉnh 4.
5. Từ đỉnh 4, đỉnh kề chưa thăm là 5. Chọn đỉnh 5.
Vậy thứ tự duyệt là: 1, 2, 3, 6, 4, 5.
