Triển Khai Đồ Thị Vô Hướng Bằng Danh Sách Kề

Hôm nay, khi mở rộng hệ thống ống dẫn trong game của chúng tôi, lại gặp phải bài toán triển khai đồ thị vô hướng. Trước đây, hệ thống ống dẫn chỉ cho phép mỗi đoạn ống kết nối với số lượng ống kề giới hạn, nên tôi đã sử dụng cấu trúc tương tự cây, lưu trữ trực tiếp một mảng kích thước cố định tại mỗi nút để chứa các nút kế tiếp. Cấu trúc này hoạt động rất hiệu quả với hệ thống ống dẫn chất lỏng.

Tuy nhiên lần này, hệ thống mới yêu cầu một mô hình ống dẫn đặc biệt hơn - không có hướng, mỗi nút có thể kết nối với nhiều nút lân cận. Ví dụ như mạng lưới dây điện hoặc hệ thống ống dẫn nhiệt. Đây chính là cấu trúc đồ thị vô hướng điển hình.

Tôi quyết định thiết kế lại cấu trúc dữ liệu bằng danh sách kề. Đặc biệt, tôi tách biệt dữ liệu nút và mối quan hệ kết nối giữa các nút thành hai cấu trúc riêng biệt, giúp module kết nối ống dẫn có thể tái sử dụng độc lập.

Đầu tiên, mỗi nút trong đồ thị được đánh dấu bằng một ID số nguyên 16-bit. Với quy mô đồ thị không quá lớn, không gian 16-bit hoàn toàn đủ dùng. Mỗi cạnh nối hai nút sẽ được biểu diễn bằng 32-bit (kết hợp hai ID). Vì là đồ thị vô hướng, tôi quy ước luôn đặt ID nhỏ hơn ở vị trí thấp hơn để đảm bảo mỗi cạnh chỉ có duy nhất một cách biểu diễn.

Nếu cần mở rộng cho đồ thị có hướng, chỉ cần thêm 1 bit để đánh dấu hướng của cạnh. Về mặt lưu trữ tối thiểu, chúng ta chỉ cần một mảng chứa các giá trị 32-bit này (khi lưu trữ lâu dài, tôi chỉ cần lưu các cạnh, các cấu trúc khác có thể xây dựng lại nhanh chóng).

Tuy nhiên, trong quá trình chạy chương trình, chúng ta cần truy xuất nhanh tất cả các cạnh liên quan đến một nút cụ thể - ví dụ để tính toán sự lan truyền năng lượng trong mạng. Tôi thiết kế cấu trúc edge như sau:

1
2
3
4
5

struct edge {
 uint16_t endpoint[2];  // Hai đầu nối
 uint16_t left;         // Con trỏ trái
 uint16_t right;        // Con trỏ phải
} ;

Cấu trúc này cho phép mỗi cạnh tham gia vào hai danh sách liên kết tại hai đầu nối. Ngoài ra, một mảng uint16_t được dùng để trỏ đến cạnh đầu tiên của mỗi nút. Nếu nút không có cạnh nào, giá trị trỏ đến có thể là bất kỳ (thường là 0), vì cạnh có thể kiểm tra ngược lại xem có kết nối với nút không.

Nếu không cần thao tác động (thêm/xóa cạnh nhanh), có thể tối ưu cấu trúc này xuống còn 48-bit. Bằng cách sắp xếp các cạnh thuộc một đỉnh liên quan vào cùng một danh sách, chỉ cần một con trỏ 16-bit thay vì hai. Một mẹo nhỏ để đánh dấu kết thúc danh sách là lưu ngược thứ tự hai ID của cạnh.

Ví dụ với đồ thị 3x3 như sau:

1
2
3
4
5

1 - 2 - 3
|   |   |
4 - 5 - 6
|   |   |
7 - 8 - 9

Đồ thị này có 12 cạnh được lưu trữ theo thứ tự:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

[0] (1,2) → 2
[1] (4,1) → 5
[2] (2,3) → 4
[3] (5,2) → 5
[4] (6,3) → 7
[5] (4,5) → 7
[6] (7,4) → a
[7] (5,6) → 9
[8] (8,5) → a
[9] (9,6) → b
[a] (8,7) → b
[b] (9,8) → b

Khi duyệt các cạnh của nút 5:

• Cạnh đầu tiên tại index 3: (5,2) → 5 (vì 5 > 2 nên tiếp tục đến index 5)
• Cạnh tại index 5: (4,5) → 7 (5 > 4 nên đến index 7)
• Cạnh tại index 7: (5,6) → 9 (5 < 6 nên đến cạnh tiếp theo)
• Cạnh tại index 8: (8,5) → a (do thứ tự đảo ngược, đây là cạnh cuối cùng)

Như vậy đã tìm được 4 cạnh kết nối với nút 5. Tôi mất nửa ngày để hoàn thiện giải pháp này. Dù đồ thị vô hướng không thường xuyên xuất hiện trong công việc hàng ngày, nhưng việc thiết kế một cấu trúc dữ liệu tối ưu vẫn mang lại cảm giác thỏa mãn. Sau khi hoàn thành, tôi kiểm tra lại trên Wikipedia và thấy có ý tưởng tương tự đã được đề xuất từ trước. Tuy nhiên, phương án nén tối ưu của tôi có lẽ vẫn là một cải tiến độc đáo.