Giải Thuật Tìm Kiếm Theo Chiều Rộng (Breadth First Search) - VietTuts

Trang chủ » Duyệt Rộng » Giải Thuật Tìm Kiếm Theo Chiều Rộng (Breadth First Search) - VietTuts

Có thể bạn quan tâm

Cấu Trúc Dữ Liệu & Giải Thuật

Tổng quan về cấu trúc dữ liệu và giải thuật Cấu trúc dữ liệu là gì? Giải thuật là gì? Cài đặt môi trường

Giải Thuật

Giải thuật tiệm cận Giải thuật tham lam Giải thuật chia để trị Giải thuật qui hoạch động

Cấu Trúc Dữ Liệu Mảng

Cấu trúc dữ liệu mảng

Danh sách liên kết - Linked list

Cấu trúc dữ liệu Linked List Cấu trúc dữ Doubly Linked List Cấu trúc dữ Circular Linked List

Ngăn Xếp & Hàng Đợi

Cấu trúc dữ liệu ngăn xếp - Stack Cấu trúc dữ hàng dợi - Queue

Một Số Giải Thuật Tìm Kiếm

Tìm kiếm tuyến tính - Linear Search Tìm kiếm nhị phân - Binary Search Tìm kiếm nội suy - Interpolation Search Cấu trúc dữ liệu Hash Table

Một Số Giải Thuật Sắp Xếp

Giải thuật sắp xếp Sắp xếp nổi bọt - Bubble Sort Sắp xếp chèn - Insertion Sort Sắp xếp chọn - Selection Sort Sắp xếp trộn - Merge Sort Sắp xếp nhanh - Quick Sort Giải thuật Shell Sort Giải thuật quay lui - Back Tracking

Cấu Trúc Dữ Liệu Đồ Thị (Graph)

Cấu trúc dữ liệu đồ thị Tìm kiếm theo chiều sâu - Depth First Search Tìm kiếm theo chiều sâu - Breadth First Search Giải thuật tìm kiếm theo chiều sâu (Depth First Search) Học lập trình C/C++

Nội dung chính

  • 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 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.

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

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 Mô tả
1. Giải thuật tìm kiếm theo chiều rộng Khởi tạo hàng đợi (queue)
2. Giải thuật tìm kiếm theo chiều rộng 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. Giải thuật tìm kiếm theo chiều rộng 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. Giải thuật tìm kiếm theo chiều rộng 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. Giải thuật tìm kiếm theo chiều rộng 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. Giải thuật tìm kiếm theo chiều rộng 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. Giải thuật tìm kiếm theo chiều rộng 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.

Đế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.

Giải thuật tìm kiếm theo chiều sâu (Depth First Search) Học lập trình C/C++

Recent Updates

Xuất dữ liệu ra màn hình console trong JavaCài đặt môi trường JavaJava Swing - Bài tập quản lý sinh viên trong javaLinkedList trong javaArrayList trong javaBài tập java có lời giảiXác thực dữ liệu (Data Validation) trong ExcelSắp xếp dữ liệu trong ExcelLọc dữ liệu (Data Filter) trong ExcelHeader và Footer trong ExcelMàu văn bản và màu nền (background) trong ExcelCăn chỉnh văn bản trong ExcelSắp Tết 2024 Rồi! - Còn bao nhiêu ngày nữa là đến tết 2024?

VietTuts on facebook

Học Lập Trình Online Miễn Phí - VietTuts.Vn
Danh Sách Bài Học

Học Java | Hibernate | Spring Học Excel | Excel VBA Học Servlet | JSP | Struts2 Học C | C++ | C# Học Python Học SQL

Bài Tập Có Lời Giải

Bài tập Java Bài tập C Bài tập C++ Bài tập C# Bài tập Python Ví dụ Excel VBA

Câu Hỏi Phỏng Vấn

201 câu hỏi phỏng vấn java 25 câu hỏi phỏng vấn servlet 75 câu hỏi phỏng vấn jsp 52 câu hỏi phỏng vấn Hibernate 70 câu hỏi phỏng vấn Spring 57 câu hỏi phỏng vấn SQL

Từ khóa » Duyệt Rộng