Thuật toán BFS

Thuật toán BFS sử dụng cấu trúc

• Hàng đợi

• Ngăn xếp

• Cả hàng đợi và ngăn xếp

• Không sử dụng cấu trúc nào cả

Khi thực hiện thuật toán BFS thăm các đỉnh của đồ thị trong hình vẽ (bắt đầu từ đỉnh 1) thì

• Đỉnh được thăm sau đỉnh 2 là đỉnh 3

• Đỉnh được thăm sau đỉnh 2 là đỉnh 5

• Đỉnh được thăm sau đỉnh 2 là đỉnh 4

• Đỉnh được thăm sau đỉnh 2 là đỉnh 6

Khi sử dụng thuật toán BFS thăm đồ thị như trong hình vẽ (bắt đầu từ đỉnh 1), tại thời điểm ta đang ở đỉnh 4 ta sẽ lần lượt thăm các đỉnh:

• 3, 5, 6

• 5, 6

• 3, 6

• 6

Khi sử dụng thuật toán BFS thăm đồ thị như trong hình vẽ (bắt đầu từ đỉnh 1), tại thời điểm ta đang ở đỉnh 2 ta sẽ lần lượt thăm các đỉnh:

• 3, 4, 5

• 3, 4

• 4, 5

• 5, 3, 4

Xuất phát từ đỉnh t đi thăm các đỉnh còn lại của đồ thị bằng thuật toán BFS, trật tự dãy đỉnh được thăm là

• t, s, u, v, w, r, x, z, q, y

• t, s, r, q, u, v, w, x, y, z

• t, s, u, v, r, q, w, x, z, y

• t, s, u, v, w, r, q, x, y, z

Từ đỉnh i đi thăm các đỉnh còn lại của đồ thị bằng BFS thì dãy đỉnh được thăm theo thứ tự là:

• i, e, d, h, f, a, c, g, b

• i, e, d, h, f, g, c, a, b

• i, d, e, h, f, a, b, c, g

• i, d, e, h, a, c, f, g, b

Từ đỉnh 0 đi thăm các đỉnh còn lại của đồ thị trong hình vẽ bằng thuật toán BDS, trật tự thăm đỉnh là:

• 0, 3, 2, 5, 4, 1

• 0, 2, 3, 4, 5, 1

• 0, 2, 3, 5, 4, 1

• 0, 5, 4, 2, 3, 1

Cấu trúc hàng đợi cho phép

• phần tử vào trước, ra trước

• phần tử vào sau, ra trước

• vào/ra tùy ý

• không phải các lựa chọn này

Thuật toán BFS được thiết kế chuyên dụng để

• Tìm đường đi ngắn nhất giữa hai đỉnh của đồ thị

• Tìm đường đi dài nhất giữa hai đỉnh của đồ thị

• Tìm tất cả các đường đi giữa hai đỉnh của đồ thị

• Không phải các lựa chọn này

Từ đỉnh 0, đi thăm đồ thị trong hình bằng thuật toán BFS, trật tự thăm đỉnh là

• 0, 1, 2, 3, 5, 4, 6, 7

• 0, 1, 2, 3, 5, 6, 7, 4

• 0, 1, 2, 3, 5, 4, 7, 6

• 0, 1, 2, 3, 6, 7, 5, 4