Nhóm 2 - Đậu Văn Nam - Lâm Minh Tuấn
| Tên | |
|---|---|
| Lâm Minh Tuấn | [email protected] |
| Đậu Văn Nam | [email protected] |
Using Treaps for Optimization of Graph Storage
Ma trận kề thường được sử dụng để biểu diễn đồ thị. Mục đích sử dụng treap là để tối ưu hóa khả năng lưu trữ đồ thị mà không cần sử dụng ma trận kề.
Các vấn đề khi sử dụng ma trận kề để biểu diễn đồ thị:
- Vấn đề chính liên quan đến việc sử dụng ma trận kề là nó có phân bổ mảng tĩnh và các mục cố định cho tăng kích thước của mạng tạo ra vấn đề trong quá trình chèn.
- Thứ hai, cấp phát mảng động đòi hỏi nhiều thời gian hơn để tạo một mảng mới có kích thước tăng dần và sau đó di chuyển các mục từ mảng trước đó sang mảng mới và sau đó giải phóng mảng trước.
- Cuối cùng, mặc dù ma trận kề biểu diễn đồ thị thì thưa nhưng mọi mục nhập null đều tốn bộ nhớ.
Ví dụ về một đồ thị ngẫu nhiên có các cạnh và các đỉnh như hình vẽ, ma trận kề biểu diễn đồ thị trên như sau:
Đây là ma trận kề tương ứng với đồ thị 10 node. Mỗi hàng của ma trận mô tả thông tin kề của mỗi node của đồ thị tương ứng. Vì Treap yêu cầu khóa và mức độ ưu tiên nên khóa sẽ được lấy từ tên duy nhất của một node và độ ưu tiên sẽ là số các liên kết tương ứng với mỗi node của nó.
Kết quả cuối cùng sau khi thêm các node vào treap:
Có thể thấy, mỗi cây con và cây con của nó thỏa mãn các tính chất của Treap. Do đó ma trận kề biểu diễn đồ thị bây giờ có thể thay thế bằng Treap.