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 rộng (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 rộng là thứ tự nào dưới đây?
Trả lời:
Đáp án đúng: B
Ta sẽ thực hiện duyệt đồ thị theo chiều rộng bắt đầu từ đỉnh 1 (do không có đỉnh nào được chỉ định trước). Khi duyệt, ta sẽ ưu tiên thăm các đỉnh theo thứ tự từ điển (tức là số nhỏ hơn được thăm trước).
1. **Bắt đầu từ đỉnh 1:** Đưa 1 vào hàng đợi và đánh dấu đã thăm.
2. **Các đỉnh kề của 1:** Các đỉnh kề của 1 là 2, 3, và 6. Theo thứ tự từ điển, ta thăm 2, sau đó 3, sau đó 6. Đưa 2, 3, 6 vào hàng đợi.
3. **Thăm đỉnh 2:** Các đỉnh kề của 2 là 1, 3, 5, và 6. 1 đã thăm. 3 và 6 đã được đưa vào hàng đợi. Vậy ta chỉ cần đưa 5 vào hàng đợi.
4. **Thăm đỉnh 3:** Các đỉnh kề của 3 là 1 và 2, cả hai đều đã thăm.
5. **Thăm đỉnh 6:** Các đỉnh kề của 6 là 1, 2, 4, 5. 1 và 2 đã thăm. 5 đã được đưa vào hàng đợi. Ta đưa 4 vào hàng đợi.
6. **Thăm đỉnh 5:** Các đỉnh kề của 5 là 2, 4, 6. Cả 3 đều đã thăm.
7. **Thăm đỉnh 4:** Các đỉnh kề của 4 là 5, 6. Cả 2 đều đã thăm
Như vậy, thứ tự các đỉnh được thăm là: 1, 2, 3, 6, 5, 4.
