Code thuật toán tìm kiếm theo chiều rộng năm 2024

Thuật toán BFS là thuật toán tìm kiếm theo chiều rộng trên đồ thị vô hướng hoặc có hướng, không trọng số.

Minh họa:

Visualization

Cho đồ thị như hình vẽ

Cho đồ thị như hình vẽ, tìm đường đi ngắn nhất từ đỉnh 0 đến đỉnh 5

Như vậy ta có file input.txt với dạng ma trận kề như sau

Ta có file input.txt chứa ma trận kề như saufile input.txt danh sách kề

Mô tả thuật toán:

Xuất phát từ 1 đỉnh bất kỳ, đi tới tất cả các đỉnh kề của nó, lưu các đỉnh này lại. Tiếp tục đem 1 đỉnh khác (từ tập đỉnh đã được lưu) ra xét và đi cho đến khi không còn đỉnh nào có thể đi.

Trong quá trình đi từ đỉnh này sang đỉnh kia, t iến hành lưu lại đỉnh cha của đỉnh kề, để khi đi ngược lại từ đỉnh kết thúc đến đỉnh xuất phát, ta có được đường đi ngắn nhất.

Bước 0: Chuẩn bị dữ liệu

Bước 0: Chuẩn bị dữ liệu

Bước 1: Chạy thuật toán lần 1

Bước 2: Chạy thuật toán lần 2

Bước 3: Chạy thuật toán lần 3

Bước 4: Chạy thuật toán lần 4

Bước 5: Chạy thuật toán lần 5

Bước 6: Chạy thuật toán lần 6

Dừng thuật toán

Kết quả: 0 -> 1 -> 5

Thứ tự duyệt BFS là 0, 1, 3, 2, 5, 4

Chạy thuật toán chính

Ta xem đoạn code sau

Ý nghĩa:

Xuất phát từ 1 đỉnh đi tới tất cả các đỉnh kề của nó, lưu các đỉnh này lại. Tiếp tục đem 1 đỉnh khác (từ tập đỉnh đã được lưu) ra xét và đi cho đến khi không còn đỉnh nào có thể đi.

Trong quá trình đi từ đỉnh này sang đỉnh kia, t iến hành lưu lại đỉnh cha của đỉnh kề, để khi đi ngược lại từ đỉnh kết thúc đến đỉnh xuất phát, ta có được đường đi ngắn nhất.

Mã nguồn toàn bộ

Độ phức tạp thuật toán

Độ phức tạp của BFS: O(V + E) (với V là số đỉnh)

Ưu điểm và ứng dụng của BFS

Kỹ thuật tìm kiếm rộng là kỹ thuật vét cạn không gian trạng thái bài toán vì vậy sẽ tìm được lời giải nếu có và đường đi tìm được đi qua ít đỉnh nhất.

Trong trí tuệ nhân tạo hay lý thuyết đồ thị, thuật toán tìm kiếm theo chiều rộng (BFS) là một thuật toán phát triển các nút chưa xét theo chiều rộng và các nút được xét theo thứ tự độ sâu tăng dần .BFS phù hợp với các bài toán tìm đường từ gốc đến 1 điểm đích cho trước và thuật toán sẽ tốt nhất khi ở trong đồ thị không có trọng số. khi đó, thuật toán sẽ luôn tìm được đường tới đích ngắn nhất có thể.

Cách cài đặt giải thuật :

• fringe : là một cấu trúc kiểu hàng đợi (FIFO) lưu giữ các nút sẽ được duyệt
• closed : cấu trúc hàng đợi queue lưu giữ các nút đã được duyệt .
• G(N, A) : cây biểu diễn không gian trạng thái bài toán.
• no : trạng thái đầu của bài toán
• DICH : tập hợp các trạng thái đích của bài toán.
• NB(n) : tập hợp các trạng thái con của cua nút đang xét n

sau đây là giải thuật :

Mô tả :

1. Chèn đỉnh gốc no vào hàng đợi
2. Lấy ra đỉnh đầu tiên trong hàng đợi và thăm nó
   • Nếu đỉnh này chính là đỉnh đích, dừng quá trình tìm kiếm và trả về kết quả.
   • Nếu không phải thì chèn tất cả các đỉnh kề với đỉnh vừa thăm nhưng chưa được thăm trước đó vào hàng đợi.
3. Nếu hàng đợi là rỗng, thì tất cả các đỉnh có thể đến được đều đã được thăm – dừng việc tìm kiếm và trả về “không thấy”.
4. Nếu hàng đợi không rỗng thì quay về bước 2.

ví dụ minh họa :

Giả sử ta có đồ thị :

Để được giải thích chi tiết và code của thuật toán trong C xin xem video sau :

Giải thuật tìm kiếm theo chiều rộng là gì ?

Giải thuật tìm kiếm theo chiều rộng (Breadth First Search – viết tắt là BFS) duyệt qua một đồ thị theo chiều rộng và sử dụng hàng đợi (queue) để ghi nhớ đỉnh liền kề để bắt đầu việc tìm kiếm khi không gặp được đỉnh liền kề trong bất kỳ vòng lặp nào.

Như trong hình ví dụ trên, giải thuật tìm kiếm theo chiều rộng duyệt từ A tới B tới E tới F sau đó tới C, tới G và cuối cùng tới D. Giải thuật này tuân theo qui tắc:

• Qui tắc 1: Duyệt tiếp tới đỉnh liền kề mà chưa được duyệt. Đánh dấu đỉnh mà đã được duyệt. Hiển thị đỉnh đó và đẩy vào trong một hàng đợi (queue)..
• Qui tắc 2: Nếu không tìm thấy đỉnh liền kề, thì xóa đỉnh đầu tiên trong hàng đợi.
• Qui tắc 3: Lặp lại Qui tắc 1 và 2 cho tới khi hàng đợi là trống.

Bảng dưới đây minh họa cách giải thuật tìm kiếm theo chiều rộng làm việc với một ví dụ đơn giản sau:

Bước Duyệt Miêu tả 1.

Khởi tạo hàng đợi (queue) 2.Chúng ta bắt đầu duyệt đỉnh S (đỉnh bắt đầu) và đánh dấu đỉnh này là đã duyệt. 3.Sau đó chúng ta tìm đỉnh liền kề với Smà chưa được duyệt. Trong ví dụ này chúng ta có 3 đỉnh, và theo thứ tự chữ cái chúng ta chọn đỉnh A đánh dấu là đã duyệt và xếp A vào hàng đợi. 4.Tiếp tục duyệt đỉnh liền kề với S là B. Đánh dấu là đã duyệt và xếp đỉnh này vào hàng đợi. 5.Tiếp tục duyệt đỉnh liền kề với S là C. Đánh dấu là đã duyệt và xếp đỉnh này vào hàng đợi. 6.Bây giờ đỉnh S không còn đỉnh nào liền kề mà chưa được duyệt. Bây giờ chúng ta rút A từ hàng đợi. 7.Từ đỉnh A chúng ta có đỉnh liền kề là D và là đỉnh chưa được duyệt. Đánh dấu đỉnh D là đã duyệt và xếp vào hàng đợi.

Quảng cáo

Đến đây, chúng ta thấy rằng không còn đỉnh nào là chưa được đánh dấu (chưa được duyệt với ví dụ trong bảng này). Nhưng giải thuật vẫn tiếp tục, chúng ta vẫn tiếp tục rút các đỉnh từ hàng đợi theo thứ tự để tìm tất cả các đỉnh mà chưa được duyệt. Khi hàng đợi là trống thì đó là lúc kết thúc giải thuật.

Trên đây là phần giới thiệu và minh họa cho giải thuật tìm kiếm theo chiều rộng với một đồ thị gồm 5 đỉnh. Để tìm hiểu code đầy đủ của giải thuật tìm kiếm theo chiều rộng trong ngôn ngữ C, mời bạn click chuột vào chương: Tìm kiếm theo chiều rộng trong C.

Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.

Theo dõi chúng tôi miễn phí trên mạng xã hội facebook và youtube:

Follow fanpage của team https://www.facebook.com/vietjackteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.vietjack để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... mới nhất của chúng tôi.