Giải Thuật Tìm Kiếm Theo Chiều Sâu

Có thể bạn quan tâm

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

Một số khái niệm về Giải thuật
Giải thuật là gì ?
Giải thuật tiệm cận - Asymptotic Algorithms
Giải thuật tham lam - Greedy Algorithms
Giải thuật chia để trị - Divide and Conquer
Giải thuật qui hoạch động - Dynamic Programming
Giải thuật định lý thợ - Master Theorem

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

Danh sách liên kết - Linked Lists
Danh sách liên kết - Linked List
Danh sách liên kết đôi - Doubly Linked List
Danh sách liên kết vòng - 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ữ liệu hàng đợ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
Giải thuật Shell Sort
Sắp xếp nhanh - Quick Sort
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 Traversal
Tìm kiếm theo chiều rộng - Breadth First Traversal

Cấu trúc dữ liệu cây
Cấu trúc dữ liệu cây
Duyệt cây - Tree Traversal
Cây tìm kiếm nhị phân - Binary Search Tree
Cây AVL - AVL Tree
Cây Slay - splay Tree
Giải thuật Cây khung - Spanning Tree
Cấu trúc dữ liệu Heap

Đệ qui (Recursion)
Khái niệm cơ bản về Đệ qui
Bài toán Tháp Hà Nội - Tower of Hanoi
Dãy Fibonacci

Tài liệu tham khảo
Học lập trình C
Học lập trình C++
Học lập trình Java

Giải thuật tìm kiếm theo chiều sâu Trang trước Trang sau

Giải thuật tìm kiếm theo chiều sâu là gì ?

Giải thuật tìm kiếm theo chiều sâu (Depth First Search – viết tắt là DFS), còn được gọi là giải thuật tìm kiếm ưu tiên chiều sâu, là giải thuật duyệt hoặc tìm kiếm trên một cây hoặc một đồ thị và sử dụng stack (ngăn xếp) để 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 tiếp tục cho tới khi gặp được đỉnh cần tìm hoặc tới một nút không có con. Khi đó giải thuật quay lui về đỉnh vừa mới tìm kiếm ở bước trước.

Trong hình minh họa trên, giải thuật tìm kiếm theo chiều sâu đầu tiên duyệt từ các đỉnh A tới B tới C tới D sau đó tới E, sau đó tới F và cuối cùng tới G. Giải thuật này tuân theo qui tắc sau:

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 ngăn xếp (stack).
Qui tắc 2: Nếu không tìm thấy đỉnh liền kề, thì lấy một đỉnh từ trong ngăn xếp (thao tác pop up). (Giải thuật sẽ lấy tất cả các đỉnh từ trong ngăn xếp mà không có các đỉnh liền kề nào)
Qui tắc 3: Lặp lại các qui tắc 1 và qui tắc 2 cho tới khi ngăn xếp là trống.

Bảng dưới đây minh họa các qui tắc với hình ví dụ trên:

Bước	Duyệt	Miêu tả
1.		Khởi tạo ngăn xếp (stack)
2.		Đánh dấu đỉnh S là đã duyệt và đặt đỉnh này vào trong ngăn xếp. Tìm kiếm bất kỳ đỉnh liền kề nào mà chưa được duyệt từ đỉnh S. Chúng ta có 3 đỉnh và chúng ta có thể lấy bất kỳ đỉnh nào trong số chúng. Ví dụ, chúng ta lấy đỉnh A theo thứ tự chữ cái.
3.		Đánh dấu đỉnh A là đã duyệt và đặt vào trong ngăn xếp. Tìm kiếm bất kỳ đỉnh liền kề nào với đỉnh A. Cả S và D đều là hai đỉnh liền kề A nhưng chúng ta chỉ quan tâm về đỉnh chưa được duyệt.
4.		Duyệt đỉnh D, đánh dấu đỉnh này là đã duyệt và đặt vào trong ngăn xếp. Ở đây, chúng ta có B và C là hai đỉnh kề với D và cả hai đều là chưa được duyệt. Chúng ta sẽ chọn theo thứ tự chữ cái một lần nữa.
5.		Chọn B, đánh dấu là đã duyệt và đặt vào trong ngăn xếp. Ở đây B không có bất kỳ đỉnh liền kề nào mà chưa được duyệt. Vì thế chúng ta lấy B ra khỏi ngăn xếp.
6.		Kiểm tra phần tử trên cùng của ngăn xếp để trở về nút đã duyệt trước đó và kiểm tra xem đỉnh này có đỉnh nào liền kề mà chưa được duyệt hay không. Ở đây, chúng ta tìm thấy đỉnh D nằm ở trên cùng của ngăn xếp.
7.		Chỉ có một đỉnh liền kề với D mà chưa được duyệt, đó là đỉnh C. Chúng ta duyệt C, đánh dấu là đã duyệt và đặt vào trong ngăn xếp.

Quảng cáo

Vì C không có bất kỳ đỉnh nào liền kề mà chưa được duyệt, chúng ta tiếp tục lấy các đỉnh từ trong ngăn xếp để tìm xem có còn bất kỳ đỉnh nào liền kề mà chưa được duyệt hay không. Trong ví dụ này là không có, và chúng ta vẫn tiếp tục cho tới khi ngăn xếp là trống.

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 sâu. Để tìm hiểu code đầy đủ của giải thuật tìm kiếm theo chiều sâu trong ngôn ngữ C, mời bạn click chuột vào chương: Tìm kiếm theo chiều sâu trong C.

👉 Giải bài nhanh với AI Hay:

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

Bài học Cấu trúc dữ liệu và giải thuật phổ biến tại vietjack.com: