Khóa học Python từ Cơ bản đến Nâng cao

Bài 14.1 - DFS trên cây trong Python

DFS (Depth-First Search) là một trong những thuật toán tìm kiếm và duyệt cây/đồ thị quan trọng nhất trong lập trình. Trong bài này, bạn sẽ học cách triển khai DFS trên cấu trúc cây bằng ngôn ngữ Python. Đây là kiến thức nền tảng cực kỳ quan trọng khi bạn làm việc với các bài toán đệ quy, cây nhị phân, cây tổng quát, hoặc các hệ thống phân cấp dữ liệu.

DFS là gì?

DFS (tìm kiếm theo chiều sâu) là một thuật toán bắt đầu từ gốc của cây, sau đó đi sâu theo nhánh con đầu tiên cho đến khi không thể tiếp tục, rồi quay lại và đi theo nhánh tiếp theo.

DFS có thể triển khai theo hai cách chính:

• Đệ quy (sử dụng call stack)
• Dùng stack tường minh

Trong bài này, ta sẽ tập trung vào cách đệ quy, đơn giản và trực quan hơn đối với người mới học.

Cấu trúc cây trong Python

Trước hết, bạn cần xây dựng cấu trúc của một cây. Một cách đơn giản nhất là sử dụng class Node như sau:

class Node:
    def __init__(self, value):
        self.value = value
        self.children = []

    def add_child(self, child_node):
        self.children.append(child_node)

Giải thích:

• Node đại diện cho mỗi nút trong cây.
• value là giá trị của nút.
• children là danh sách chứa các nút con.

Triển khai DFS bằng đệ quy

def dfs_recursive(node):
    if node is None:
        return
    print(node.value)  # Xử lý node hiện tại
    for child in node.children:
        dfs_recursive(child)

Giải thích:

• Hàm dfs_recursive nhận một node làm tham số.
• Nó in ra giá trị của node hiện tại.
• Sau đó, gọi đệ quy chính nó trên từng nút con.

Ví dụ 1: Cây đơn giản

# Xây dựng cây mẫu
root = Node("A")
b = Node("B")
c = Node("C")
d = Node("D")
e = Node("E")

root.add_child(b)
root.add_child(c)
b.add_child(d)
b.add_child(e)

# Gọi DFS
print("Kết quả DFS:")
dfs_recursive(root)

✅ Kết quả in ra sẽ là:

A
B
D
E
C

Giải thích luồng duyệt:

1. Bắt đầu tại A
2. Sang B → D → E
3. Quay lại → duyệt C

Ví dụ 2: Cây lớn hơn nhiều cấp

# Cây phức tạp hơn
root = Node("1")
a = Node("2")
b = Node("3")
c = Node("4")
d = Node("5")
e = Node("6")
f = Node("7")

a.add_child(d)
a.add_child(e)
b.add_child(f)
root.add_child(a)
root.add_child(b)
root.add_child(c)

print("DFS trên cây nhiều cấp:")
dfs_recursive(root)

✅ Kết quả:

1
2
5
6
3
7
4

Luồng duyệt:

• Đi sâu vào 2, rồi đến 5 → 6
• Sau đó đến 3 → 7, cuối cùng 4

Kết luận

DFS là một kỹ thuật cơ bản nhưng cực kỳ quan trọng trong lập trình cây và đồ thị. Hiểu rõ cách hoạt động của DFS giúp bạn giải quyết được rất nhiều bài toán đệ quy, quản lý cấu trúc dữ liệu phân cấp, và là bước đệm cho các thuật toán nâng cao hơn.

💡 Hãy thử viết thêm các hàm để đếm số nút, tìm giá trị lớn nhất, hoặc tính chiều sâu của cây sử dụng DFS nhé!

#HappyCoding cùng FullhouseDev! 🚀