Thuật toán Dijkstra được dùng để:

Cả thuật toán Prim và Kruskal đều là các thuật toán tham lam được sử dụng để tìm cây khung nhỏ nhất (Minimum Spanning Tree - MST) của một đồ thị liên thông có trọng số. Điểm giống nhau cốt lõi giữa hai thuật toán này là cả hai đều cố gắng xây dựng cây khung bằng cách chọn các cạnh có trọng số nhỏ nhất một cách tham lam, đồng thời đảm bảo không tạo ra chu trình (cycle) trong cây khung đang xây dựng.

Phân tích các đáp án:

• Đáp án 1: Dừng khi kết nạp được tất cả các cạnh vào cây khung. - Sai. Cây khung chỉ chứa n-1 cạnh (với n là số đỉnh của đồ thị).


• Đáp án 2: Dừng khi kết nạp được n đỉnh và n cạnh vào cây khung - Sai. Cây khung có n đỉnh và n-1 cạnh.


• Đáp án 3: Thuật toán chọn các cạnh có trọng số tối thiểu, liên thuộc với các đỉnh đã thuộc cây khung và không tạo ra chu trình. - Gần đúng. Mô tả đúng việc chọn cạnh nhỏ nhất và không tạo chu trình, nhưng "liên thuộc với các đỉnh đã thuộc cây khung" đúng hơn với Prim, còn Kruskal chọn cạnh nhỏ nhất bất kì không quan trọng là liên thuộc đỉnh nào đã có.


• Đáp án 4: Thuật toán xây dựng cây khung ngắn nhất. - Đúng. Đây là mục tiêu chung của cả hai thuật toán. Cả Prim và Kruskal đều tìm cách xây dựng cây khung có tổng trọng số các cạnh là nhỏ nhất có thể.

Vậy, đáp án chính xác nhất là 4, vì nó thể hiện mục tiêu chung của cả hai thuật toán.

Trong thuật toán Ford-Fulkerson để giải bài toán luồng cực đại, bước tăng luồng được thực hiện trên các cạnh nằm trên đường đi tăng (đường đi đánh dấu). Đường đi tăng là đường đi từ đỉnh phát (source) đến đỉnh thu (sink) mà trên đó ta có thể tăng luồng. Thuật toán sẽ lặp đi lặp lại việc tìm đường đi tăng và tăng luồng trên đường đi đó cho đến khi không còn đường đi tăng nào nữa. Do đó, đáp án chính xác là các cạnh nằm trên đường đi đánh dấu.

Thuật toán BFS (Breadth-First Search) duyệt đồ thị theo chiều rộng. Bắt đầu từ đỉnh H, ta duyệt các đỉnh kề với H, sau đó duyệt các đỉnh kề với các đỉnh vừa duyệt, cứ tiếp tục như vậy cho đến khi duyệt hết các đỉnh của đồ thị.

Các bước thực hiện thuật toán BFS(H) như sau:

1. Bắt đầu từ H.

2. Các đỉnh kề với H là G, F, E.

3. Các đỉnh kề với G là B.

4. Các đỉnh kề với F là D, K.

5. Các đỉnh kề với E là A.

6. Các đỉnh kề với K là I.

7. Các đỉnh kề với B là C.

Vậy thứ tự duyệt các đỉnh là: H, G, F, E, B, D, K, A, C, I.

Vậy đáp án đúng là: H, G, F, E, B, D, K, A, C, I.

Thuật toán DFS (Depth-First Search - Tìm kiếm theo chiều sâu) bắt đầu từ đỉnh 1, sau đó duyệt theo chiều sâu đến các đỉnh kề chưa được thăm. Thứ tự duyệt như sau:

• Bắt đầu từ đỉnh 1.


• Đỉnh 1 có các đỉnh kề 2 và 7. Ta chọn duyệt đỉnh 2 trước (vì nó nhỏ hơn).


• Từ đỉnh 2, các đỉnh kề chưa thăm là 3.


• Từ đỉnh 3, các đỉnh kề chưa thăm là 6.


• Từ đỉnh 6, các đỉnh kề chưa thăm là 9.


• Từ đỉnh 9, các đỉnh kề chưa thăm là 8.


• Quay lại đỉnh 1, đỉnh kề chưa thăm là 7.


• Từ đỉnh 7, các đỉnh kề chưa thăm là 4.


• Từ đỉnh 4, các đỉnh kề chưa thăm là 5.


• Từ đỉnh 5, đỉnh kề chưa thăm là 10.

Vậy thứ tự duyệt các đỉnh là: 1, 2, 3, 6, 9, 8, 7, 4, 5, 10.