Thuật toán tìm kiếm theo chiều rộng

      49

Lý thuyết thuật toán tìm kiếm theo chiều rộng BFS bằng C/C++ và Java


Để xem lý thuyết đồ thị với các định nghĩa về đường đi, chu trình, đồ thị liên thông bạn có thể xem ở đây.

Bạn đang xem: Thuật toán tìm kiếm theo chiều rộng

Lý thuyết về thuật toán tìm kiếm theo chiều sâu bạn có thể xem ở đây.

Xem thêm: Cách Làm Bài Văn Nghị Luận Xã Hội Về Hiện Tượng Đời Sống, Nghị Luận Xã Hội Về Hiện Tượng Đời Sống

Khác với thuật toán tìm kiếm theo chiều sâu, thuật toán tìm kiếm theo chiều rộng thay thế việc sử dụng stack bằng hàng đợi queue. Trong thủ tục này, đỉnh được nạp vào hàng đợi đầu tiên là v, các đỉnh kề với v ( v1, v2,..., vk) được nạp vào queue kế tiếp. Quá trình duyệt tiếp theo được bắt đầu từ các đỉnh còn có mặt trong hàng đợi.

Để ghi nhận trạng thái duyệt các đỉnh của đồ thị, ta cũng vẫn sử dụng mảng chuaxet<> gồm n phần tử thiết lập giá trị ban đầu là TRUE. Nếu đỉnh i của đồ thị đã được duyệt, giá trị chuaxet sẽ nhận giá trị FALSE. Thuật toán dừng khi hàng đợi rỗng.

Thủ tục BFS dưới đây thể hiện quá trình thực hiện của thuật toán:

void BFS(int u){ queue = φ; u Thủ tục BFS sẽ thăm tất cả các đỉnh cùng thành phần liên thông với u. Để thăm tất cả các đỉnh của đồ thị, chúng ta chỉ cần thực hiện đoạn chương trình dưới đây:

for (u=1; u≤n; u++) chuaxet = TRUE;for (u∈V ) if (chuaxet ) BFS(u);

Đồ thị - Tìm kiếm theo chiều rộng BFS

*

Kết quả duyệt: 1,2,3,11,4,6,12,13,7, 8, 9,10, 5.

BFS.IN

130 1 1 0 0 0 0 0 0 0 1 0 01 0 0 1 0 1 0 0 0 0 0 0 01 0 0 1 0 0 0 0 0 0 0 0 00 1 1 0 0 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 1 1 0 0 00 1 0 1 0 0 1 1 0 0 0 0 00 0 0 0 0 1 0 0 0 0 0 0 00 0 0 0 0 1 0 0 0 1 0 0 00 0 0 0 1 0 0 0 0 0 0 0 10 0 0 0 1 0 0 1 0 0 0 0 01 0 0 0 0 0 0 0 0 0 0 1 10 0 0 0 0 0 0 0 0 0 1 0 10 0 0 0 0 0 0 0 1 0 1 1 0

Chạy tay


STT
Các đỉnh đã duyệt

Chương trình cài đặt bằng C/C++

#include#includeusing namespace std;#define MAX 100 #define TRUE 1 #define FALSE 0 int G, n, chuaxet, QUEUE; void Init(){ freopen("BFS.IN","r",stdin); cin>>n; cout>G; } } for(int i=1; i

Chương trình cài đặt bằng Java

package simplecodecjava.blogspot.com;import java.io.BufferedReader;import java.io.File;import java.io.FileNotFoundException;import java.io.FileReader;import java.io.IOException;public class BFSAlgorithm { static final int MAX = 100; int G<><> = new int;/* ma trận kề*/ boolean chuaxet<> = new boolean;/*mảng đánh dấu đỉnh đã được thăm.*/ int QUEUE<> = new int; /*hàng đợi*/ int n; void init() { File file = new File(getClass().getResource("BFS.IN").getPath()); BufferedReader reader = null; try { reader = new BufferedReader(new FileReader(file)); n = Integer.parseInt(reader.readLine()); for (int i = 1; i