THUẬT TOÁN DUYỆT CHIỀU SÂU DFS
Thuật toán DFS (Depth First Search) là thuật toán tìm kiếm theo chiều sâu bắt
đầu từ một đỉnh bất kì trong một đồ thì vô hướng, có hướng hoặc trong một cây.
cellpadding="0"
cellspacing="0"
class="tr-caption-container"
style="margin-left: auto; margin-right: auto;"
>
imageanchor="1"
style="margin-left: auto; margin-right: auto;"
>
data-original-height="1000"
data-original-width="1635"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg5nHACPvLu7l1ZLYawrgH8rLJqHXmIGrEqchWi-MQrSsOcN_CrjV7dt1GSJSISX0ZZ7jaEteX5Nzwgs3cv34rzBB67BvL711WS-OCZc6GuOumkuxBmys3uO1xSwLKwVe_ykKRmim9tDPo/s16000/DFS.png"
/>
Thuật Toán Tìm Kiếm Theo Chiều Sâu DFS
THUẬT TOÁN
MÔ TẢ THUẬT TOÁN:
- DFS: duyệt theo chiều sâu bắt đầu từ đỉnh u.
Nếu tồn tại đỉnh v trong danh sách kề adj[u] của đỉnh u chưa được
thăm thì tiến hành thăm v sau đó duyệt chiều sâu với đỉnh v
Nếu tất cả các đỉnh kề với u đã được thăm thì DFS quay trở lại đỉnh
x mà từ đó thăm u để tiến hành thăm các đỉnh khác kề với x mà chưa được
thăm. Lúc này đỉnh u được gọi là đã duyệt xong
- Thuật toán được code trên ngôn ngữ C++
VÍ DỤ:
style="margin-left: 1em; margin-right: 1em;"
>
data-original-height="688"
data-original-width="963"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg2TB5sfry8Da9qnVHv1SmP1r15kN1dJflyP82OJ3fum1QbH_JoCkvgBYFONtsQYoubQv-tqXQA5JuZZb_y6lZ81CSoUH4Uob9lcxIk-aY4ZGPq93rGhfLmRaDqPSR1BcAz7kfH3Mu1-SU/s16000/Untitled-4.png"
/>
CODE MẪU:
Kết quả: 1 3 4 5 7 6 2
style="margin-left: 1em; margin-right: 1em;"
>
data-original-height="698"
data-original-width="1006"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj4OZgxZPTzHl2MpKpJb4sRZRo3CTcCdmUB5RV8JU4haC2rezSycAx1rIEV4-GjeGNrrgQHJyEElR483ayL0c1Nv7vA2jwwRA7MKPsQ8_BYj6WZO69miP-9f9gOR9aN9_ZuywqH9Fg4mdw/s16000/Untitled-3.png"
/>
LỜI KẾT
Trên đây mình đã chia sẻ những hiểu biết của mình về DFS. Nếu có gì sai sót
các bạn có thể để lại comment ở bên dưới để mình chỉnh sửa. Cảm ơn các bạn đã
đọc bài viết !