Mô phỏng thuật toán Duyệt Euler trên cây

Euler Tour (In/Out Times) · Nhóm: Cây

Một lượt DFS gán cho mỗi nút thời điểm vào tin và thời điểm ra tout bằng bộ đếm timer tăng đều, biến mỗi cây con thành một đoạn liên tục [tin, tout].

Ý tưởng

Giữ một bộ đếm timer bắt đầu từ 0.

Khi vào nút: timer tăng 1, đặt tin[nút] = timer.

Duyệt hết các con rồi rời nút: timer tăng 1, đặt tout[nút] = timer.

Vì sao đúng

Nhờ tin/tout, câu hỏi trên một cây con trở thành câu hỏi trên một đoạn liền mạch, dùng được Fenwick hay segment tree để trả lời nhanh.

Mã Python

timer = 0
def dfs(node):
    global timer
    timer += 1
    tin[node] = timer   # entry time
    for child in node.children:
        dfs(child)
    timer += 1
    tout[node] = timer  # exit time

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.