Đồ thị vô hướng G = (V, E) được gọi là liên thông nếu.

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 các nhánh con trước khi khám phá các nút lân cận ở cùng mức. Bắt đầu từ đỉnh A, ta sẽ duyệt theo thứ tự ưu tiên các đỉnh kề chưa được thăm. Trong trường hợp có nhiều đỉnh kề chưa thăm, ta có thể chọn duyệt theo thứ tự bảng chữ cái (hoặc một thứ tự ưu tiên nào đó được quy định trước).

Áp dụng DFS bắt đầu từ A:
1. A được thăm.
2. Các đỉnh kề của A là B, C, K. Chọn B (theo thứ tự abc) thăm trước.
3. Các đỉnh kề của B là D, I. Chọn D thăm trước.
4. Các đỉnh kề của D là F. Chọn F thăm.
5. Các đỉnh kề của F là H. Chọn H thăm.
6. Từ H đến G.
7. Từ G đến E.
8. Quay lại B, thăm I.
9. Từ I thăm N.
10. Từ N thăm K.
11. Cuối cùng thăm C.

Vậy thứ tự duyệt đúng là: A, B, D, F, H, G, E, I, N, K, C

Thuật toán Kruskal được sử dụng để tìm cây khung nhỏ nhất của một đồ thị có trọng số. Thuật toán này hoạt động bằng cách thêm các cạnh vào cây khung theo thứ tự trọng số tăng dần, miễn là việc thêm cạnh đó không tạo ra chu trình.

Bước 1: Sắp xếp các cạnh theo trọng số tăng dần.
Bước 2: Chọn cạnh có trọng số nhỏ nhất. Kiểm tra xem cạnh này có tạo thành chu trình với các cạnh đã chọn trước đó hay không. Nếu không tạo thành chu trình, thêm cạnh này vào cây khung. Ngược lại, bỏ qua cạnh này.
Bước 3: Lặp lại bước 2 cho đến khi có đủ (V-1) cạnh, với V là số đỉnh của đồ thị.

Áp dụng thuật toán Kruskal cho đồ thị đã cho, ta có cây khung nhỏ nhất với tập cạnh là: T = {(1,2), (1, 4), (2, 3), (4,5) ,(2, 6), (6, 7)}.

Thuật toán Prim để tìm cây khung nhỏ nhất bắt đầu từ một đỉnh, sau đó mở rộng cây bằng cách thêm các cạnh có trọng số nhỏ nhất mà kết nối cây hiện tại với một đỉnh chưa thuộc cây. Ta thực hiện thuật toán Prim như sau:

1. Bắt đầu từ đỉnh 1:
* Các cạnh kề với đỉnh 1 là (1,2) = 5 và (1,8) = 4. Chọn cạnh (1,8) vì nó có trọng số nhỏ hơn. Vậy T = {(1,8)}.

2. Mở rộng cây từ đỉnh 8:
* Các cạnh kề với đỉnh 8 là (8,2) = 2, (8,5) = 4, (8,3) = 8, và (1,8) đã có.
* Chọn cạnh (8,2) vì nó có trọng số nhỏ nhất. Vậy T = {(1,8), (8,2)}.

3. Mở rộng cây từ đỉnh 2:
* Các cạnh kề với đỉnh 2 là (2,4) = 7, (1,2) = 5, (8,2) = 2 (đã có).
* Chọn cạnh (2,4) vì nó có trọng số nhỏ hơn các cạnh khác kề với các đỉnh đã có trong cây và đỉnh chưa có trong cây. Vậy T = {(1,8), (8,2), (2,4)}.

4. Mở rộng cây từ đỉnh 4:
* Các cạnh kề với đỉnh 4 là (4,7) = 9, (2,4) = 7 (đã có).
* Chọn cạnh (4,7) vì nó có trọng số nhỏ nhất và kết nối với đỉnh chưa có trong cây. Vậy T = {(1,8), (8,2), (2,4), (4,7)}.

5. Mở rộng cây từ đỉnh 7:
* Các cạnh kề với đỉnh 7 là (7,6) = 1, (4,7) = 9 (đã có), (7,5) = 3.
* Chọn cạnh (7,6) vì nó có trọng số nhỏ nhất. Vậy T = {(1,8), (8,2), (2,4), (4,7), (7,6)}.

6. Mở rộng cây từ đỉnh 6:
* Các cạnh kề với đỉnh 6 là (6,3) = 5, (7,6) = 1 (đã có), (6,5) = 6.
* Chọn cạnh (6,3) vì nó có trọng số nhỏ nhất và kết nối với đỉnh chưa có trong cây. Vậy T = {(1,8), (8,2), (2,4), (4,7), (7,6), (6,3)}.

7. Mở rộng cây từ đỉnh 3:
* Các cạnh kề với đỉnh 3 là (3,8) = 8, (3,6) = 5 (đã có).
* Chọn cạnh (8,5) vì nó có trọng số nhỏ nhất và kết nối với đỉnh chưa có trong cây. Vậy T = {(1,8), (8,2), (2,4), (4,7), (7,6), (6,3), (8,5)}.

Vậy, cây khung nhỏ nhất H = (V, T) có tập cạnh T = {(1,8), (8,2), (2,4), (4,7), (7,6), (6,3), (8,5)}.

So sánh với các đáp án, ta thấy đáp án B phù hợp.