Posts

2019

Disjoint Set Union

7 minute read

Published:

Bài viết này được thực hiện khi tôi đang học học phần Cấu trúc dữ liệu và giải thuậtLí thuyết đồ thị của kì 2, năm 2 (2018-2019). Trong quá trình học môn học, tôi thấy Disjoint Set Union là một cấu trúc dữ liệu rất hữu ích cho các bài toán xử lí trên đồ thị. Khi muốn duyệt hay quản lí các đỉnh trong đồ thị mà có nhiều thành phần rời rạc nhau thì DSU là một lựa chọn tối ưu và nhanh vì ta không phải duyệt lại toàn bộ đồ thị với DFS / BFS.