Đồ thị¶
Một đồ thị là một cấu trúc dữ liệu phi tuyến tính gồm các đỉnh và cạnh. Ta có thể biểu diễn đồ thị \(G\) một cách trừu tượng dưới dạng một tập hợp các đỉnh \(V\) và một tập hợp các cạnh \(E\). Ví dụ dưới đây biểu diễn một đồ thị gồm 5 đỉnh và 7 cạnh.
Nếu coi các đỉnh là các nút và các cạnh là các tham chiếu (con trỏ) nối giữa chúng, ta có thể xem đồ thị là một dạng mở rộng của cấu trúc dữ liệu danh sách liên kết. Như được minh họa trong hình dưới đây, so với mối quan hệ tuyến tính (danh sách liên kết) và mối quan hệ chia để trị (cây), mối quan hệ mạng lưới (đồ thị) có độ tự do cao hơn và do đó phức tạp hơn.
Các loại đồ thị và thuật ngữ thường gặp¶
Tùy theo việc các cạnh có hướng hay không, đồ thị có thể được chia thành đồ thị vô hướng và đồ thị có hướng, như minh họa trong hình dưới đây.
- Trong đồ thị vô hướng, cạnh biểu thị liên kết "hai chiều" giữa hai đỉnh, ví dụ như mối quan hệ bạn bè trên WeChat hoặc QQ.
- Trong đồ thị có hướng, cạnh có tính hướng, nghĩa là các cạnh \(A \rightarrow B\) và \(A \leftarrow B\) độc lập với nhau, ví dụ như mối quan hệ theo dõi (following) và người theo dõi (follower) trên Weibo hoặc TikTok.
Tùy theo việc tất cả các đỉnh có liên thông với nhau hay không, đồ thị có thể được chia thành đồ thị liên thông và đồ thị không liên thông, như minh họa trong hình dưới đây.
- Đối với đồ thị liên thông, bắt đầu từ bất kỳ đỉnh nào, ta đều có thể đi tới tất cả các đỉnh còn lại.
- Đối với đồ thị không liên thông, bắt đầu từ một đỉnh nào đó, có ít nhất một đỉnh không thể đi tới được.
Ta cũng có thể thêm biến "trọng số" (weight) vào các cạnh, tạo thành đồ thị có trọng số như minh họa trong hình dưới đây. Ví dụ, trong các trò chơi di động như "Vương Giả Vinh Diệu" (Honor of Kings), hệ thống sẽ tính toán độ "thân mật" giữa các người chơi dựa trên thời gian họ chơi cùng nhau, và mạng lưới thân mật này có thể được biểu diễn bằng đồ thị có trọng số.
Cấu trúc dữ liệu đồ thị bao gồm các thuật ngữ thường gặp dưới đây.
- Kề (Adjacency): Khi hai đỉnh được nối với nhau bằng một cạnh, hai đỉnh đó được gọi là "kề" nhau. Trong hình trên, các đỉnh kề của đỉnh 1 là các đỉnh 2, 3 và 5.
- Đường đi (Path): Chuỗi các cạnh từ đỉnh A đến đỉnh B được gọi là "đường đi" từ A đến B. Trong hình trên, chuỗi cạnh 1-5-2-4 là một đường đi từ đỉnh 1 đến đỉnh 4.
- Bậc (Degree): Số lượng cạnh nối với một đỉnh. Đối với đồ thị có hướng, bán bậc vào (in-degree) chỉ số lượng cạnh hướng vào đỉnh đó, và bán bậc ra (out-degree) chỉ số lượng cạnh hướng ra từ đỉnh đó.
Biểu diễn đồ thị¶
Các phương pháp biểu diễn đồ thị phổ biến bao gồm "ma trận kề" và "danh sách kề". Các ví dụ dưới đây sử dụng đồ thị vô hướng.
Ma trận kề¶
Cho một đồ thị gồm \(n\) đỉnh, một ma trận kề sử dụng một ma trận kích thước \(n \times n\) để biểu diễn đồ thị, trong đó mỗi hàng (cột) đại diện cho một đỉnh, và các phần tử trong ma trận đại diện cho các cạnh, sử dụng giá trị \(1\) hoặc \(0\) để cho biết có tồn tại cạnh nối giữa hai đỉnh hay không.
Như được minh họa trong hình dưới đây, giả sử ma trận kề là \(M\) và danh sách đỉnh là \(V\). Khi đó, phần tử ma trận \(M[i, j] = 1\) biểu thị có một cạnh nối giữa đỉnh \(V[i]\) và đỉnh \(V[j]\), trong khi \(M[i, j] = 0\) biểu thị không có cạnh nối giữa hai đỉnh này.
Ma trận kề có các tính chất dưới đây.
- Trong đơn đồ thị (simple graph), một đỉnh không thể tự kết nối với chính nó, vì vậy các phần tử trên đường chéo chính của ma trận kề đều vô nghĩa.
- Đối với đồ thị vô hướng, cạnh ở cả hai hướng là tương đương nhau, do đó ma trận kề đối xứng qua đường chéo chính.
- Thay thế các giá trị \(1\) và \(0\) trong ma trận kề bằng các trọng số cho phép nó biểu diễn đồ thị có trọng số.
Khi sử dụng ma trận kề để biểu diễn đồ thị, ta có thể truy cập trực tiếp các phần tử ma trận để tìm kiếm cạnh, giúp cho các thao tác thêm, xóa, tra cứu và sửa đổi đạt hiệu suất rất cao, đều có độ phức tạp thời gian là \(O(1)\). Tuy nhiên, độ phức tạp không gian của ma trận là \(O(n^2)\), tiêu tốn nhiều bộ nhớ.
Danh sách kề¶
Một danh sách kề sử dụng \(n\) danh sách liên kết để biểu diễn đồ thị, với các nút của danh sách liên kết đại diện cho các đỉnh. Danh sách liên kết thứ \(i\) tương ứng với đỉnh \(i\) và lưu trữ tất cả các đỉnh kề với đỉnh đó (các đỉnh được kết nối với đỉnh đó). Hình dưới đây minh họa một ví dụ về đồ thị được lưu trữ bằng danh sách kề.
Danh sách kề chỉ lưu trữ các cạnh thực sự tồn tại, và tổng số cạnh thường nhỏ hơn nhiều so với \(n^2\), giúp tiết kiệm không gian lưu trữ hơn. Tuy nhiên, việc tìm kiếm cạnh trong danh sách kề yêu cầu phải duyệt danh sách liên kết, nên hiệu suất thời gian sẽ kém hơn so với ma trận kề.
Như minh họa trong hình trên, cấu trúc của danh sách kề rất giống với phương pháp chuỗi kề (separate chaining) trong bảng băm, vì vậy ta có thể sử dụng các phương pháp tương tự để cải thiện hiệu suất. Ví dụ, khi một danh sách liên kết trở nên quá dài, nó có thể được chuyển đổi thành cây AVL hoặc cây đỏ-đen, cải thiện độ phức tạp thời gian từ \(O(n)\) sang \(O(\log n)\); nó cũng có thể được chuyển đổi thành bảng băm, giảm độ phức tạp thời gian xuống còn \(O(1)\).
Các ứng dụng phổ biến của đồ thị¶
Như được trình bày trong bảng dưới đây, nhiều hệ thống thực tế có thể được mô hình hóa bằng đồ thị, và các bài toán tương ứng có thể quy về các bài toán tính toán đồ thị.
Bảng
| Đỉnh | Cạnh | Bài toán tính toán đồ thị | |
|---|---|---|---|
| Mạng xã hội | Người dùng | Quan hệ bạn bè | Gợi ý bạn bè tiềm năng |
| Tuyến tàu điện ngầm | Nhà ga | Sự kết nối giữa các nhà ga | Tìm tuyến đường ngắn nhất |
| Hệ Mặt Trời | Thiên thể | Lực hấp dẫn giữa các thiên thể | Tính toán quỹ đạo hành tinh |