Thuật toán tìm kiếm theo chiều rộng đầu tiên (BFS) với VÍ DỤ
Sarah Chen
⚡ Tóm tắt thông minh
Tìm kiếm theo chiều rộng (BFS) là một thuật toán duyệt đồ thị từng cấp một, thăm tất cả các nút lân cận của một nút trước khi đi sâu hơn. Nó sử dụng hàng đợi FIFO và tìm đường đi ngắn nhất trong đồ thị không trọng số mà không có vòng lặp vô hạn.
Thuật toán BFS (Tìm kiếm theo chiều rộng) là gì?
Tìm kiếm theo chiều rộng (BFS) là một thuật toán được sử dụng để vẽ đồ thị dữ liệu hoặc tìm kiếm trong cây hoặc duyệt qua các cấu trúc. Tên đầy đủ của BFS là Tìm kiếm theo chiều rộng (Breadth-first search).
Thuật toán này hiệu quả trong việc truy cập và đánh dấu tất cả các nút chính trong đồ thị theo cách chính xác theo chiều rộng. 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 liền kề với nút đã chọn. Hãy nhớ rằng, BFS truy cập các nút này từng cái một.
Sau khi thuật toán truy cập và đánh dấu nút bắt đầu, sau đó nó di chuyển đến các nút chưa đượ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 lần lặp này tiếp tục cho đến khi tất cả các nút của đồ thị đã được truy cập và đánh dấu thành công.
Truyền tải đồ thị là gì?
Truyền tải đồ thị là một phương pháp thường được sử dụng để xác định vị trí đỉnh trong đồ thị. Đây là một thuật toán tìm kiếm nâng cao có thể phân tích biểu đồ với tốc độ và độ chính xác cùng với việc đánh dấu chuỗi các đỉnh đã truy cập. Quá trình này cho phép bạn truy cập nhanh từng nút trong biểu đồ mà không bị khóa trong vòng lặp vô hạn.
Kiến trúc của thuật toán BFS
- Ở các cấp độ 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. Thuật toán BFS sẽ duyệt qua nút đó, đánh dấu nó là đã được duyệt và đưa nó vào hàng đợi.
- Lúc này, thuật toán BFS sẽ duyệt qua các nút gần nhất và chưa được duyệt, rồi đá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 dựa trên... mô hình FIFO.
- Tương tự như vậy, các nút gần nhất và chưa được truy cập còn lại trên đồ thị sẽ được phân tích, đá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 được nhận và in ra kết quả.
Tại sao chúng ta cần thuật toán BFS?
Có rất nhiều lý do để sử dụng thuật toán BFS để tìm kiếm trong 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 hàng đầu của bạn là:
- BFS rất hữu ích cho việc 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.
- 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 đơ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 gặp phải vấn đề vòng lặp vô hạn.
Thuật toán BFS hoạt động như thế nào?
Truyền tải đồ thị yêu cầu thuật toán truy cập, kiểm tra và/hoặc cập nhật từng nút chưa được truy cập trong cấu trúc dạng cây. Việc duyệt đồ thị được phân loại theo thứ tự chúng truy cập các nút trên đồ thị.
Thuật toán BFS bắt đầu thao tác từ nút đầu tiên hoặc nút bắt đầu trong biểu đồ và duyệt qua nó một cách triệt để. Khi nó đi qua nút ban đầu thành công, thì đỉnh không đi qua tiếp theo trong biểu đồ sẽ được truy cập và đánh dấu.
Do đó, có thể nói rằng tất cả các nút kề với đỉnh hiện tại đều được thăm và duyệt qua trong lần lặp đầu tiên. Phương pháp 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 biểu đồ đều được biết đến. Chẳng hạn, 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, hãy thêm đỉnh V vào hàng đợi BFS.
Bước 3)
Bắt đầu tìm kiếm bằng thuật toán BFS, và sau khi hoàn thành, đánh dấu đỉnh V là đã được thăm.
Bước 4)
Hàng đợi BFS vẫn không trống, do đó hãy loại bỏ đỉnh V của đồ thị khỏi hàng đợi.
Bước 5)
Tìm 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 kề, giả sử là V1, nếu đỉnh đó chưa được thăm thì hãy thêm V1 vào hàng đợi BFS.
Bước 7)
Thuật toán BFS sẽ truy cập V1, đánh dấu nó là đã được truy cập 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 đồ thị gồm bảy số từ 0 đến 6.
Bước 2)
0 hoặc XNUMX đã đượ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ác nút còn lại không kề với nút nào và chưa được thăm sẽ được thăm, đánh dấu và chèn vào hàng đợi.
Bước 5)
Việc lặp lại quá trình duyệt đượ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à những quy tắc quan trọng khi sử dụng thuật toán BFS:
- Hàng đợi (FIFO – Vào trước ra trước) cấu trúc dữ liệu được BFS sử dụng.
- Bạn đánh dấu bất kỳ nút nào trong đồ thị là nút gốc và bắt đầu duyệt dữ liệu từ đó.
- Thuật toán BFS duyệt qua tất cả các nút trong đồ thị và tiếp tục bỏ qua các nút.ping chúng đã hoàn thành.
- BFS truy cập một nút chưa được truy cập liền kề, đánh dấu nút đó là xong và chèn nó vào hàng đợi.
- Nó loại bỏ đỉnh trước đó khỏi hàng đợi nếu 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à đá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.
Ứng dụng của thuật toán BFS
Chúng ta hãy xem xét một số ứng dụng thực tế trong đó việc triển khai thuật toán BFS có thể mang lại hiệu quả cao.
- Đồ thị không có trọng số: Thuật toán BFS có thể dễ dàng tạo ra đườ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: Thuật toán BFS có thể được sử dụng để xác định vị trí 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ẽ giúp 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 dữ liệu 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, tức là trang web, sau đó truy cập tất cả các liên kết từ nguồn đó.
- Hệ thống định vị: 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 vị trí nguồn.
- Phát sóng mạng: Một gói tin được quảng bá được hướng dẫn bởi thuật toán BFS để tìm và tiếp cận tất cả các nút mà nó có địa chỉ.
