BFS Duyệt đồ Thị Theo Chiều Rộng - 123doc

BFS Duyệt đồ thị theo chiều rộng Breadth First Search Trong lý thuyết đồ thị, tìm kiếm theo chiều rộng (BFS) là một thuật toán tìm kiếm trong đồ thị trong đó việc tìm kiếm chỉ bao gồm 2 thao tác: (a) cho trước một đỉnh của đồ thị; (b) thêm các đỉnh kề với đỉnh vừa cho vào danh sách có thể hướng tới tiếp theo. Có thể sử dụng thuật toán tìm kiếm theo chiều rộng cho hai mục đích: tìm kiếm đường đi từ một đỉnh gốc cho trước tới một đỉnh đích, và tìm kiếm đường đi từ đỉnh gốc tới tất cả các đỉnh khác. Trong đồ thị không có trọng số, thuật toán tìm kiếm theo chiều rộng luôn tìm ra đường đi ngắn nhất có thể. Thuật toán BFS bắt đầu từ đỉnh gốc và lần lượt nhìn các đỉnh kề với đỉnh gốc. Sau đó, với mỗi đỉnh trong số đó, thuật toán lại lần lượt nhìn trước các đỉnh kề với nó mà chưa được quan sát trước đó và lặp lại. Xem thêm thuật toán tìm kiếm theo chiều sâu, trong đó cũng sử dụng 2 thao tác trên nhưng có trình tự quan sát các đỉnh khác với thuật toán tìm kiếm theo chiều rộng.

Duyệt đồ thị theo chiều rộng - Breadth-First

Search (BFS)

Thuật toán sử dụng một cấu trúc dữ liệu hàng đợi để lưu

trữ thông tin trung gian thu được trong quá trình tìm kiếm:

3.Hàng đợi là rỗng thì dừng

4 Nếu hàng đợi không rỗng thì quay về bước 2

1 Chèn đỉnh gốc vào hàng đợi

2 Lấy ra đỉnh đầu tiên trong hàng đợi và quan sát nó.

Nếu đỉnh này đã duyệt, không làm gì cả, quay lại bước 2

Nếu đỉnh này chưa duyệt thì chèn tất cả các đỉnh chưa duyệt kề với nó vào hàng đợi

Sử dụng mảng Đã duyệt, mảng Lưu vết và 1 Squeue

• DaDuyet[i] = 0 > đỉnh i chưa duyệt

• DaDuyet[i] = t > đỉnh i được duyệt theo thứ tự t

• LuuVet[i] = k > đỉnh i được đến từ đỉnh k

• Nếu i là đỉnh bắt đầu thì LuuVet[i] = 1

• Squeue: Lưu lại các đỉnh chuẩn bị xem xét

• Xem ví dụ minh họa ở các slide sau:

12

11t=1

12

11

pop() -> 1

DaDuyet[4] = t++, LuuVet[4]=1 Nếu DaDuyet[12] = 0

DaDuyet[12] = t++, LuuVet[12]=1

push(2) push(4) push(12)

12

11

pop() -> 2

Không làm gì cả

12

11

pop() -> 4

DaDuyet[7] = t++, LuuVet[6]=4

push(6) push(7)

12

11

pop() -> 12

DaDuyet[11] = t++, LuuVet[11]=12

push(0) push(11) 1

10 12

11

12

11

pop() -> 6

DaDuyet[10] = t++, LuuVet[10]=6

push(5) push(10)

12

11

pop() -> 7

12

11

pop() -> 5

DaDuyet[9] = t++, LuuVet[9]=5

push(8) push(9)

12

11

pop() -> 10

12

11

pop() -> 3