Thuật toán BFS (Breadth-First Search) là gì?
Tìm kiếm theo chiều rộng (BFS) là một thuật toán được sử dụng để vẽ biểu đồ dữ liệu hoặc cây tìm kiếm hoặc các cấu trúc chuyển ngang. Dạng đầy đủ của BFS là tìm kiếm theo chiều rộng.
Thuật toán truy cập và đánh dấu hiệu quả tất cả các nút chính trong biểu đồ theo chiều rộng chính xác. Thuật toán này chọn một nút duy nhất (điểm ban đầu hoặc điểm nguồn) trong đồ thị và sau đó truy cập tất cả các nút lân cận với nút đã chọn. Hãy nhớ rằng, BFS truy cập từng nút một.
Khi thuật toán truy cập và đánh dấu nút bắt đầu, sau đó nó sẽ di chuyển đến các nút không được truy cập gần nhất và phân tích chúng. Sau khi truy cập, tất cả các nút đều được đánh dấu. Các bước lặp này tiếp tục cho đến khi tất cả các nút của biểu đồ đã được truy cập và đánh dấu thành công.
Trong hướng dẫn về Thuật toán này, bạn sẽ học:
- Thuật toán BFS (Breadth-First Search) là gì?
- Đường truyền biểu đồ là gì?
- Kiến trúc của thuật toán BFS
- Tại sao chúng ta cần Thuật toán BFS?
- Thuật toán BFS hoạt động như thế nào?
- Ví dụ về thuật toán BFS
- Quy tắc của thuật toán BFS
- Các ứng dụng của thuật toán BFS
Đường truyền biểu đồ là gì?
Đường ngang đồ thị là một phương pháp thường được sử dụng để xác định vị trí đỉnh trong đồ thị. Nó là một thuật toán tìm kiếm nâng cao có thể phân tích đồ thị với tốc độ và độ chính xác cùng với việc đánh dấu trình tự của các đỉnh đã thăm. Quá trình này cho phép bạn nhanh chóng truy cập từng nút trong biểu đồ mà không bị khóa trong một vòng lặp vô hạn.
Kiến trúc của thuật toán BFS
- Trong các mức dữ liệu khác nhau, bạn có thể đánh dấu bất kỳ nút nào là nút bắt đầu hoặc nút ban đầu để bắt đầu duyệt. BFS sẽ truy cập vào nút và đánh dấu nó là đã truy cập và đặt nó vào hàng đợi.
- Bây giờ BFS sẽ truy cập các nút gần nhất và chưa được truy cập và đánh dấu chúng. Các giá trị này cũng được thêm vào hàng đợi. Hàng đợi hoạt động trên mô hình FIFO.
- Theo cách tương tự, các nút gần nhất và chưa được truy cập còn lại trên biểu đồ được phân tích được đánh dấu và thêm vào hàng đợi. Các mục này sẽ bị xóa khỏi hàng đợi khi nhận được và kết quả là được in ra.
Tại sao chúng ta cần Thuật toán BFS?
Có nhiều lý do để sử dụng Thuật toán BFS để sử dụng khi tìm kiếm tập dữ liệu của bạn. Một số khía cạnh quan trọng nhất khiến thuật toán này trở thành lựa chọn đầu tiên của bạn là:
- BFS hữu ích để phân tích các nút trong biểu đồ và xây dựng đường đi ngắn nhất qua các nút này.
- BFS có thể duyệt qua đồ thị với số lần lặp nhỏ nhất.
- Kiến trúc của thuật toán BFS rất đơn giản và mạnh mẽ.
- Kết quả của thuật toán BFS có độ chính xác cao so với các thuật toán khác.
- Các lần lặp BFS diễn ra liền mạch và không có khả năng thuật toán này vướng vào vấn đề vòng lặp vô hạn.
Thuật toán BFS hoạt động như thế nào?
Truyền qua đồ thị yêu cầu thuật toán phải truy cập, kiểm tra và / hoặc cập nhật mọi nút chưa được truy cập trong một cấu trúc dạng cây. Các đường đi qua biểu đồ được phân loại theo thứ tự mà chúng truy cập vào các nút trên biểu đồ.
Thuật toán BFS bắt đầu hoạt động từ nút đầu tiên hoặc nút bắt đầu trong một biểu đồ và duyệt nó một cách triệt để. Khi nó đi qua nút ban đầu thành công, thì đỉnh tiếp theo không được duyệt trong biểu đồ sẽ được truy cập và đánh dấu.
Do đó, bạn có thể nói rằng tất cả các nút liền kề với đỉnh hiện tại đều được truy cập và duyệt qua trong lần lặp đầu tiên. Một phương pháp luận hàng đợi đơn giản được sử dụng để triển khai hoạt động của thuật toán BFS và nó bao gồm các bước sau:
Bước 1)
Mỗi đỉnh hoặc nút trong đồ thị đã biết. Ví dụ: bạn có thể đánh dấu nút là V.
Bước 2)
Trong trường hợp đỉnh V không được truy cập thì hãy thêm đỉnh V vào Hàng đợi BFS
Bước 3)
Bắt đầu tìm kiếm BFS và sau khi hoàn thành, Đánh dấu đỉnh V là đã thăm.
Bước 4)
Hàng đợi BFS vẫn không trống, do đó loại bỏ đỉnh V của đồ thị khỏi hàng đợi.
Bước 5)
Lấy tất cả các đỉnh còn lại trên đồ thị kề với đỉnh V
Bước 6)
Đối với mỗi đỉnh liền kề, giả sử V1, trong trường hợp nó chưa được truy cập thì hãy thêm V1 vào hàng đợi BFS
Bước 7)
BFS sẽ truy cập V1 và đánh dấu nó là đã thăm và xóa nó khỏi hàng đợi.
Ví dụ về thuật toán BFS
Bước 1)
Bạn có một biểu đồ gồm bảy số khác nhau, từ 0 - 6.
Bước 2)
0 hoặc 0 đã được đánh dấu là nút gốc.
Bước 3)
0 được truy cập, đánh dấu và chèn vào cấu trúc dữ liệu hàng đợi.
Bước 4)
Còn lại 0 nút liền kề và không được truy cập sẽ được truy cập, đánh dấu và chèn vào hàng đợi.
Bước 5)
Các phép lặp đi ngang được lặp lại cho đến khi tất cả các nút được truy cập.
Quy tắc của thuật toán BFS
Dưới đây là các quy tắc quan trọng để sử dụng thuật toán BFS:
- Một cấu trúc dữ liệu hàng đợi (FIFO-First in First Out) được sử dụng bởi BFS.
- Bạn đánh dấu bất kỳ nút nào trong biểu đồ là nút gốc và bắt đầu duyệt dữ liệu từ đó.
- BFS đi qua tất cả các nút trong biểu đồ và tiếp tục thả chúng khi đã hoàn thành.
- BFS truy cập vào một nút không được truy cập liền kề, đánh dấu nó là xong và chèn nó vào hàng đợi.
- Loại bỏ đỉnh trước đó khỏi hàng đợi trong trường hợp không tìm thấy đỉnh liền kề.
- Thuật toán BFS lặp lại cho đến khi tất cả các đỉnh trong đồ thị được duyệt thành công và được đánh dấu là đã hoàn thành.
- Không có vòng lặp nào do BFS gây ra trong quá trình truyền dữ liệu từ bất kỳ nút nào.
Các ứng dụng của thuật toán BFS
Chúng ta hãy xem xét một số ứng dụng trong cuộc sống thực mà việc triển khai thuật toán BFS có thể mang lại hiệu quả cao.
- Đồ thị không trọng số: Thuật toán BFS có thể dễ dàng tạo đường đi ngắn nhất và cây bao trùm tối thiểu để thăm tất cả các đỉnh của đồ thị trong thời gian ngắn nhất có thể với độ chính xác cao.
- Mạng P2P: BFS có thể được triển khai để định vị tất cả các nút gần nhất hoặc lân cận trong mạng ngang hàng. Điều này sẽ tìm thấy dữ liệu cần thiết nhanh hơn.
- Trình thu thập thông tin web : Công cụ tìm kiếm hoặc trình thu thập thông tin web có thể dễ dàng xây dựng nhiều cấp chỉ mục bằng cách sử dụng BFS. Việc triển khai BFS bắt đầu từ nguồn, là trang web, sau đó nó truy cập tất cả các liên kết từ nguồn đó.
- Hệ thống Điều hướng: BFS có thể giúp tìm tất cả các vị trí lân cận từ vị trí chính hoặc nguồn.
- Phát sóng mạng: Một gói tin đã quảng bá được hướng dẫn bởi thuật toán BFS để tìm và đến tất cả các nút mà nó có địa chỉ.
Tóm lược
- Truyền qua biểu đồ là một quá trình duy nhất yêu cầu thuật toán phải truy cập, kiểm tra và / hoặc cập nhật mọi nút chưa được truy cập trong một cấu trúc dạng cây. Thuật toán BFS hoạt động trên nguyên tắc tương tự.
- Thuật toán rất hữu ích để phân tích các nút trong biểu đồ và xây dựng đường đi ngắn nhất đi qua các nút này.
- Thuật toán duyệt qua đồ thị với số lần lặp nhỏ nhất và thời gian ngắn nhất có thể.
- BFS chọn một nút duy nhất (điểm ban đầu hoặc điểm nguồn) trong biểu đồ và sau đó truy cập tất cả các nút lân cận với nút đã chọn. BFS truy cập từng nút một.
- Dữ liệu được truy cập và đánh dấu được BFS xếp vào hàng đợi. Hàng đợi hoạt động trên cơ sở xuất trước. Do đó, phần tử được đặt trong biểu đồ đầu tiên sẽ bị xóa đầu tiên và kết quả là được in ra.
- Thuật toán BFS không bao giờ có thể bị mắc vào một vòng lặp vô hạn.
- Do độ chính xác cao và triển khai mạnh mẽ, BFS được sử dụng trong nhiều giải pháp đời thực như mạng P2P, Trình thu thập thông tin web và Phát sóng mạng.