Sự giống nhau giữa thuật toán Prim và thuật toán Kruskal là:

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.