Thuật Toán Tìm Kiếm Theo Chiều Sâu DFS

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.

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Ụ:

CODE MẪU:

Kết quả: 1 3 4 5 7 6 2

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 !

Đánh Giá Bài Viết: