Xem mã nguồn của Tìm kiếm theo chiều sâu

<div style="clear:right; float:right; margin-left:10px">
{{thông tin thuật toán
|Tên=Thuật toán tìm kiếm theo chiều sâu
|Hình=Depth-first-tree.svg
|Chú thích=Ví dụ về thứ tự duyệt theo chiều sâu
|Loại=Thuật toán tìm kiếm
|Cấu trúc=Đồ thị
|Thời gian=O(<nowiki>|</nowiki>V<nowiki>|</nowiki>+<nowiki>|</nowiki>E<nowiki>|</nowiki>) với đơn đồ thị, không duyệt vòng
|Không gian=O(<nowiki>|</nowiki>V<nowiki>|</nowiki>) nếu duyệt toàn bộ đồ thị, mỗi đỉnh qua đúng một lần
}}
<div style="clear:right; float:right">
{{graph search algorithm}}
</div>
</div>
'''Tìm kiếm ưu tiên chiều sâu''' hay '''tìm kiếm theo chiều sâu'''  ({{Lang-en|Depth-first search - DFS}}) là một [[thuật toán]] duyệt hoặc tìm kiếm trên một [[cây (lý thuyết đồ thị)|cây]] hoặc một [[đồ thị]]. Thuật toán khởi đầu tại gốc (hoặc chọn một đỉnh nào đó coi như gốc) và phát triển xa nhất có thể theo mỗi nhánh.

Thông thường, DFS là một dạng tìm kiếm thông tin không đầy đủ mà quá trình tìm kiếm được phát triển tới đỉnh con đầu tiên của nút đang tìm kiếm 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 (khoa học máy tính)|quay lui]] về đỉnh vừa mới tìm kiếm ở bước trước. Trong dạng không đệ quy, tất cả các đỉnh chờ được phát triển được bổ sung vào một [[ngăn xếp]] [[LIFO]].

Độ phức tạp không gian của DFS thấp hơn của BFS ([[tìm kiếm theo chiều rộng]]). Độ phức tạp thời gian của hai thuật toán là tương đương nhau và bằng O(|V| + |E|). 

== Ví dụ ==

[[Tập tin:graph.traversal.example.svg|200px]]

Tìm kiếm ưu tiên chiều sâu bắt đầu thăm đỉnh A, đi theo cạnh trái, tiếp tục tìm kiếm xong ở cây con trái mới chuyển sang tìm kiếm ở cây con phải. Thứ tự thăm viếng các đỉnh là: A, B, D, F, E, C, G.

Quá trình viếng thăm các đỉnh diễn ra như sau: Sau khi thăm đỉnh A, vì B chưa được thăm nên theo cạnh AB ta thăm B, tiếp tục theo cạnh BD tới viếng thăm D. Từ D không thể tiếp tục đi xa hơn, ta quay lại B. Từ B, theo BF đến thăm F, tiếp tục theo cạnh FE đến thăm E. Từ E cũng không thể đi xa hơn, quay lại A, duyệt tiếp đến C, G.

== Kết quả của thuật toán ==
Một cách tự nhiên, kết quả của [[giải thuật tìm kiếm]] theo chiều sâu là một [[cây]] phủ qua tất cả các đỉnh được duyệt của đồ thị.

=== Duyệt các đỉnh ===
Có thể dùng giải thuật này để tạo một danh sách tuyến tính các đỉnh của một [[đồ thị]] (hoặc [[cây]]). Có ba cách hiện thực phương pháp này:
* Duyệt tiền thứ tự (''preordering''): tạo ra một danh sách mà trong đó các đỉnh xuất hiện theo '''đúng trật tự''' nó được thăm đến khi chạy thuật toán. Đây chính là biểu diễn tự nhiên của quá trình thực hiện giải thuật tìm kiếm theo chiều sâu. Một biểu thức ở dạng tiền thứ tự được gọi là [[ký pháp tiền tố]].
* Duyệt hậu thứ tự (''postordering''): tạo ra một danh sách mà trong đó các đỉnh xuất hiện theo thứ tự của lần '''duyệt đến sau cùng''' khi thực hiện giải thuật. Một lần duyệt hậu thứ tự một [[cây biểu thức]] sẽ cho ra một [[ký pháp hậu tố]].
* Duyệt đảo hậu thứ tự (''reverse postordering''): kết quả của cách duyệt này là sự đảo ngược lại thứ tự trong kết quả duyệt hậu thứ tự. Thông thường, khi duyệt cây, cách này cho ra cùng kết quả với duyệt tiền thứ tự, nhưng xét tổng quát, khi duyệt một đồ thị, tiền thứ tự và đảo hậu thứ tự cho ra kết quả khác nhau. Với các đồ thị có hướng và không có vòng, cách duyệt đảo hậu thứ tự cho ra một [[trật tự tô-pô]] của đồ thị đó.

== Thuật toán tìm kiếm theo chiều sâu trong đồ thị vô hướng<ref>Dương Anh Đức, [http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly_thuyet_do_thi_Theorie/Graph-DFS.pdf Nhập môn Cấu Trúc Dữ Liệu và Giải Thuật], Đại Học Khoa Học Tự Nhiên TP.HCM</ref> == 
=== Ý tưởng thuật toán ===
# '''DFS''' trên [[Thuật ngữ lý thuyết đồ thị#.C4.90|đồ thị vô hướng]] cũng giống như khám phá mê cung với một cuộn chỉ và một thùng sơn đỏ để đánh dấu, tránh bị lạc. Trong đó mỗi [[Thuật ngữ lý thuyết đồ thị#.C4.90|đỉnh]] '''s''' trong đồ thị tượng trưng cho một cửa trong mê cung.
# Ta bắt đầu từ [[Thuật ngữ lý thuyết đồ thị#.C4.90|đỉnh]] '''s''', buộc đầu cuộn chỉ vào '''s''' và đánh đấu [[Thuật ngữ lý thuyết đồ thị#.C4.90|đỉnh]] này '''"đã thăm"'''. Sau đó ta đánh dấu '''s''' là [[Thuật ngữ lý thuyết đồ thị#.C4.90|đỉnh]] hiện hành '''u'''.
# Bây giờ, nếu ta đi theo [[Thuật ngữ lý thuyết đồ thị#.C|cạnh]] '''(u,v)''' bất kỳ.
# Nếu [[Thuật ngữ lý thuyết đồ thị#.C|cạnh]] '''(u,v)''' dẫn chúng ta đến [[Thuật ngữ lý thuyết đồ thị#.C4.90|đỉnh]] '''"đã thăm"''' '''v''', ta quay trở về '''u'''.
# Nếu [[Thuật ngữ lý thuyết đồ thị#.C4.90|đỉnh]] '''v''' là [[Thuật ngữ lý thuyết đồ thị#.C4.90|đỉnh]] mới, ta di chuyển đến '''v''' và lăn cuộn chỉ theo. Đánh dấu '''v''' là '''"đã thăm"'''. Đặt '''v''' thành [[Thuật ngữ lý thuyết đồ thị#.C4.90|đỉnh]] hiện hành và lặp lại các bước.
# Cuối cùng, ta có thể đi đến một [[Thuật ngữ lý thuyết đồ thị#.C4.90|đỉnh]] mà tại đó tất cả các cạnh kề với nó đều dẫn chúng ta đến các [[Thuật ngữ lý thuyết đồ thị#.C4.90|đỉnh]] '''"đã thăm"'''. Khi đó, ta sẽ quay lui bằng cách cuộn ngược cuộn chỉ và quay lại cho đến khi trở lại một [[Thuật ngữ lý thuyết đồ thị#.C4.90|đỉnh kề]] với một [[Thuật ngữ lý thuyết đồ thị#.C|cạnh]] còn chưa được khám phá. Lại tiếp tục quy trình khám phá như trên.
# Khi chúng ta trở về '''s''' và không còn [[Thuật ngữ lý thuyết đồ thị#.C|cạnh]] nào kề với nó chưa bị khám phá là lúc '''DFS''' dừng.

=== Mệnh đề ===
Gọi '''G''' là một đồ thị vô hướng, trên đó ta sẽ thực hiện thao tác '''DFS''' với đỉnh bắt đầu là '''s''' thì:
# Phép duyệt sẽ thăm tất cả các đỉnh cùng thành phần liên thông với '''s'''.
# Các cạnh có nhãn '''"đã thăm"''' sẽ tạo ra một cây tối đại của thành phần liên thông chứa '''s'''.

=== Chứng minh ===
# '''Khẳng định 1''', là hiển nhiên vì '''DFS''' duyệt qua tất cả các đỉnh kề với đỉnh hiện hành (có thể chứng minh hoàn chỉnh hơn bằng phản chứng).
# '''Khẳng định 2''', đúng do ta chỉ đánh dấu các cạnh đi đến một đỉnh mới nên không thể tạo ra chu trình. Như vậy '''DFS''' tạo ra một [[Cây (lý thuyết đồ thị)|cây]]. Hơn nữa, '''DFS''' thăm tất cả các đỉnh thuộc thành phần liên thông nên cây này là [[cây tối đại]].

=== Độ phức tạp của thuật toán ===
# '''DFS''' được gọi đúng '''1''' lần ứng với mỗi đỉnh.
# Mỗi cạnh được xem xét đúng '''2''' lần, mỗi lần từ một đỉnh kề với nó.
# Với '''n<sub>s</sub>''' đỉnh và '''m<sub>s</sub>''' cạnh thuộc thành phần liên thông chứa '''s''', một phép '''DFS''' bắt đầu tại '''s''' sẽ chạy với thời gian '''O(n<sub>s</sub> + m<sub>s</sub>)''' nếu:
::* Đồ thị được biểu diễn bằng [[cấu trúc dữ liệu]] dạng danh sách kề.
::* Đặt nhãn cho một đỉnh là '''"đã thăm"''' và kiểm tra xem một đỉnh '''"đã thăm"''' chưa tốn chi phí '''O(degree)'''.
::* Bằng cách đặt nhãn cho các đỉnh là '''"đã thăm"''', ta có thể xem xét một cách hệ thống các cạnh kề với đỉnh hiện hành nên ta sẽ không xem xét một cạnh quá 1 lần.

=== Xác định đỉnh kề trong DFS ===
* Kết quả của '''DFS''' phụ thuộc vào cách ta chọn đỉnh kế tiếp.
[[Tập tin:DFS1.jpg|khung|giữa|Xác định đỉnh kề trong Depth-first search]]
* Nếu ta bắt đầu tại '''A''' và thử cạnh nối đến '''F''', sau đó đến '''B''', rồi đến '''E''', '''C''', cuối cùng là '''G''' ta được:
[[Tập tin:DFS2.jpg|khung|giữa|Bắt đầu từ '''A''' và kết thúc tại '''G''']]
* Nếu cũng bắt đầu từ '''A''' nhưng đi theo trình tự, tập các cạnh đã thăm, '''backedge''' và các điểm đệ quy sẽ khác trước.
[[Tập tin:DFS3.jpg|khung|giữa|Bắt đầu từ '''A''' nhưng đi theo trình tự tập các cạnh đã thăm.]]

=== Chạy từng bước thuật toán ===
Giờ ta sẽ chạy từng bước thuật toán theo ví dụ trên.
==== Nguyên lý<ref>Trương Mỹ Dung, [http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly_thuyet_do_thi_Theorie/Ch1_LTDT_TMD.pdf Chương 1. Các khái niệm cơ bản về đồ thị, trang 9], Đại Học Khoa Học Tự Nhiên TP.HCM</ref> ====
Khởi đầu từ một đỉnh, đi theo các cung(cạnh) xa nhất có thể. Trở lại đỉnh của cạnh xa nhất, tiếp tục duyệt như trước, cho đến đỉnh cuối cùng.
[[Tập tin:DFS1.jpg|khung|giữa|Thuật toán Depth-first search]]
{{Hộp thông báo
| loại = nội dung
| hình = [[Hình:Nuvola apps kedit.png|50px]]
| chữ  = '''Đoạn này đang chờ cập nhật hướng dẫn chi tiết các bước chạy.'''<br /><small> Bạn có thể [{{SERVER}}{{localurl:{{NAMESPACE}}:{{PAGENAME}}|action=edit}} viết thêm cho đoạn này được hoàn thiện hơn]. Xem phần [[Help:Sửa đổi|trợ giúp]] để biết thêm về cách sửa đổi bài. Nếu trang này <span class="plainlinks">[{{SERVER}}{{localurl:{{NAMESPACE}}:{{PAGENAME}}|action=history}}</span> đã hoàn thiện], mời bạn gỡ bản mẫu này.<br>
{{last edited by}}
}}<includeonly>{{{category|{{#switch:{{NAMESPACE}}
 |{{ns:2}}
 |{{ns:3}}=<!-- no category for user/talk pages-->
 |#default=[[Thể loại:Bài đang được viết]]
}}}}}</includeonly><noinclude>
</noinclude>
* Bước 1:
[[Tập tin:DFS-Step1.jpg|khung|giữa|Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 1]]
* Bước 2:
[[Tập tin:DFS-Step2.jpg|khung|giữa|Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 2]]
* Bước 3:
[[Tập tin:DFS-Step3.jpg|khung|giữa|Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 3]]
* Bước 4:
[[Tập tin:DFS-Step4.jpg|khung|giữa|Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 4]]
* Bước 5:
[[Tập tin:DFS-Step5.jpg|khung|giữa|Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 5]]
* Bước 6:
[[Tập tin:DFS-Step6.jpg|khung|giữa|Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 6]]
* Bước 7:
[[Tập tin:DFS-Step7.jpg|khung|giữa|Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 7]]
* Bước 8:
[[Tập tin:DFS-Step8.jpg|khung|giữa|Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 8]]
* Bước 9:
[[Tập tin:DFS-Step9.jpg|khung|giữa|Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 9]]
* Bước 10:
[[Tập tin:DFS-Step10.jpg|khung|giữa|Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 10]]
* Bước 11:
[[Tập tin:DFS-Step11.jpg|khung|giữa|Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 11]]
* Bước 12:
[[Tập tin:DFS-Step12.jpg|khung|giữa|Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 12]]
* Bước 13:
[[Tập tin:DFS-Step13.jpg|khung|giữa|Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 13]]
* Bước 14:
[[Tập tin:DFS-Step14.jpg|khung|giữa|Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 14]]
* Bước 15:
[[Tập tin:DFS-Step15.jpg|khung|giữa|Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 15]]
* Bước 16:
[[Tập tin:DFS-Step16.jpg|khung|giữa|Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 16]]
* Bước 17:
[[Tập tin:DFS-Step17.jpg|khung|giữa|Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 17]]
* Bước 18:
[[Tập tin:DFS-Step18.jpg|khung|giữa|Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 18]]
* Bước 19:
[[Tập tin:DFS-Step19.jpg|khung|giữa|Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 19]]

== Ứng dụng ==
Nhiều giải thuật sử dụng tìm kiếm theo chiều sâu:
* Xác định các [[thành phần liên thông]] của [[đồ thị]]
* Sắp xếp [[tô pô|tô-pô]] cho đồ thị
* Xác định các [[thành phần liên thông mạnh]] của đồ thị có hướng
* Kiểm tra một đồ thị có phải là [[đồ thị phẳng]] hay không

== Xem thêm ==
[[Tìm kiếm theo chiều rộng]]

==Tham khảo==
{{tham khảo|30em}}

== Liên kết ngoài ==
[http://www.youtube.com/watch?v=5AN55O8cF8E Video demo thuật toán DFS]
{{thể loại Commons|Depth-first search}}
[[Thể loại:Giải thuật lý thuyết đồ thị]]
[[Thể loại:Giải thuật tìm kiếm]]