Bình luận

Thông báo

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Test link

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

14 min read

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 DFSbê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:
No pain, no gain !

Bạn có thể thích những bài đăng này

  • Hế lô các bạn, hôm trước mình có đọc được bình luận của một bạn trên blog của mình muốn mình làm hướng dẫn thêm footer cho bản Median UI 1.6. Thì ngày hôm nay, mình sẽ hướng dẫn cá…
  • Hướng Dẫn Tạo Widget Social Media Hế lô các bạn, chào mừng các bạn đã đến với bài viết tiếp theo trong chuyên mục Blogger Tricks. Hôm nay mình sẽ tiếp tục chia sẻ cho các bạ…
  • Thuật Toán Sắp Xếp Cơ Bản Hế lô các bạn, như tiêu đề thuật toán sắp xếp cũng là một thuật toán rất quan trọng trong việc học lập trình mà mỗi lập trình viên đều phải biết. N…
  • Hế lô các bạn, như các bạn đã thấy ở cuối mỗi bài viết của mình hay bài viết của một blog bất kì đều thường có đánh giá 5 sao. Nếu như các bạn chưa biết cách thêm nó vào như…
  • Thuật Toán Sắp Xếp Hế lô các bạn. Tiếp tục series thuật toán chúng ta sẽ tìm hiểu tiếp về thuật toán sắp xếp. Hôm nay mình sẽ chia sẻ tiếp cho các bạn thêm 2 cách sắp xếp nữ…
  • Hiệu Ứng Thả Tim Khi Click Chuột Hí các bạn, chào mừng các bạn đã đến với bài viết tiếp theo của mình. Tiếp tục chuyên mục Blogger Tricks mình sẽ chia sẻ cho các bạn code th…

Đăng nhận xét

© 2025Phạm Văn Linh. All rights reserved. Developed by Jago Desain
-->

Đã phát hiện Ad Blocker

Vui lòng tắt trình chặn quảng cáo của bạn để tiếp tục!

  1. Click on the AdBlock icon in your browser.
    Nhấp vào biểu tượng AdBlock trong trình duyệt của bạn.
    Adblock
  2. Choose, Don't run on pages on this domain.
    Chọn "Always".
    Adblock
  3. The browser icon should have turned green.
    Biểu tượng trình duyệt phải chuyển sang màu xanh lá.
    Adblock
  4. Refresh the page if it didn't refresh automatically. Thanks!
    Làm mới trang nếu nó không tự động làm mới. Cảm ơn bạn rất nhiều!
  1. Click on the AdBlock Plus icon in your browser.
    Nhấp vào biểu tượng AdBlock Plus trong trình duyệt của bạn.
    Adblock
  2. Click the "This Website" button.
    Nhấp vào nút "Trang web này".
    Adblock
  3. The browser icon should have turned grey.
    Biểu tượng trình duyệt phải chuyển sang màu xám.
    Adblock