Thuật Toán Tìm Kiếm Theo Chiều Rộng BFS

THUẬT TOÁN DUYỆT CHIỀU RỘNG BFS

Bài trước mình đã đăng về thuật toán DFS thì bài này sẽ là BFS (Breadth First Search) duyệt đồ thị theo chiều rộng.

Thuật Toán Tìm Kiếm Theo Chiều Rộng BFS

THUẬT TOÁN

MÔ TẢ THUẬT TOÁN:

• BFS: duyệt theo chiều rộng xuất phát từ đỉnh u 
• Thăm các đỉnh nằm trong danh sách kề của u mà chưa được thăm (gọi là các đỉnh mức 1) 
• Thăm các đỉnh nằm trong danh sách kề của các đỉnh mức 1 mà chưa được thăm (gọi là các đỉnh mức 2) 
• Thăm các đỉnh nằm trong danh sách kề của các đỉnh mức 2 mà chưa được thăm (gọi là các đỉnh mức 3) 
• . . . 
• Sử dụng cấu trúc hàng đợi (queue)
• Thuật toán được code trên ngôn ngữ C++

VÍ DỤ:

Vẫn là ví dụ về đồ thị có hướng ở bài trước nhé =)))

CODE MẪU:

	#include<iostream>
	#include<vector>
	#include<queue>
	#include<list>
	using namespace std;
	void bfs(vector<list<int>> adj) {
	queue<int> Q; // Hàng đợi lưu các đỉnh lần lượt theo mức 1, 2, 3...
	vector<bool> visited(adj.size()); // Đánh dấu các đỉnh đã được duyệt
	Q.push(1); // Bắt đầu từ đỉnh số 1
	visited[1] = true;
	// Vòng lặp đến khi Q là rỗng
	while(!Q.empty()) {
	int u = Q.front();
	Q.pop();
	visited[u] = true;
	cout << u << " ";
	// Kiểm tra các đỉnh mức 1 của u và thêm lần lượt vào cuối hàng đợi
	for (int v : adj[u]) {
	if (!visited[v]) {
	Q.push(v);
	visited[v] = true;
	}
	}
	}
	cout << endl;
	}
	int main() {
	int n = 7; // số đỉnh
	vector<list<int>> adj; //adj[i] là danh sách lưu các đỉnh kề của i
	adj.resize(n + 1);
	adj[1].push_back(3);
	adj[1].push_back(6);
	adj[3].push_back(4);
	adj[3].push_back(7);
	adj[6].push_back(2);
	adj[6].push_back(3);
	adj[6].push_back(4);
	adj[4].push_back(5);
	adj[4].push_back(7);
	adj[2].push_back(4);
	adj[2].push_back(5);
	bfs(adj);
	}

view raw BFS.cpp hosted with ❤ by GitHub

Kết quả: 1 3 6 4 7 2 5

SO SÁNH DFS VÀ BFS:

Dưới đây là so sáng kết quả của 2 thuật toán trên cùng một đồ thị. Hình bên trái là duyệt theo DFS và bên phải là duyệt theo BFS.

LỜI KẾT

Trên đây mình đã chia sẻ những hiểu biết của mình về thuật toán duyệt chiều rộng BFS. Nếu có gì sai sót các bạn có thể để lại comment ở bên dưới để mình chỉnh sửa. Cảm ơn các bạn đã đọc bài viết !

Đánh Giá Bài Viết: