Thuật toán tìm kiếm theo chiều rộng đầu tiên (BFS) với VÍ DỤ

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 cây hoặc duyệt qua các cấu trúc. Hình thức đầy đủ của BFS là tìm kiếm theo chiều rộng.

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

1. Ở các cấp độ khác nhau của dữ liệu, 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 di chuyển ngang. BFS sẽ truy cập nút và đánh dấu nó là đã truy cập và đặt nó vào hàng đợi.
2. Bây giờ BFS sẽ ghé thăm các nút gần nhất và chưa được ghé thăm 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.
3. 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ị được phân tích, đánh dấu và thêm vào hàng đợi. Các mục này bị xóa khỏi hàng đợi khi nhận và được in ra dưới dạng kết quả.

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 để 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 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 đó, 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 trong lần lặp đầu tiên. Một 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à 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 thì 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à đã truy cập.

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)

Truy xuất tất cả các đỉnh còn lại trên đồ thị liền 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à đã 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 biểu đồ gồm bảy số nằm trong khoảng từ 0 – 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òn lại 0 nút liền kề và chưa được thăm dò sẽ được truy cập, đá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à các quy tắc quan trọng để sử dụng thuật toán BFS:

• Một hàng đợi (FIFO-First in First Out) 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 biểu đồ là nút gốc và bắt đầu duyệt dữ liệu từ nút đó.
• BFS duyệt qua tất cả các nút trong biểu đồ và tiếp tục loại bỏ chúng khi đã 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.
• 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 biểu đồ đượ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.

Ứ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 đường đi ngắn nhất và cây bao trùm tối thiểu để truy cập 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 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ỉ.

Tổng kết

• Truyền tải biểu đồ là một quy trình duy nhất 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. Thuật toán BFS hoạt động theo nguyên tắc tương tự.
• Thuật toán này 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.
• Thuật toán duyệt đồ 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 liền kề với nút đã chọn. BFS truy cập từng nút một.
• Dữ liệu đã truy cập và đánh dấu được BFS đặt vào hàng đợi. Hàng đợi hoạt động theo nguyên tắc vào trước ra trước. Do đó, phần tử được đặt trong biểu đồ đầu tiên sẽ bị xóa trước và kết quả là được in.
• Thuật toán BFS không bao giờ có thể bị mắc vào 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 thực tế như mạng P2P, Trình thu thập thông tin web và Phát sóng mạng.