Adjacency matrix là gì?

Ma trận kề (adjacency matrix) là một cách biểu diễn đồ thị (graph) dưới dạng ma trận boolean (0 và 1). Một đồ thị hữu hạn (finite graph) có thể được biểu diễn dưới dạng ma trận vuông (square matrix) trên máy tính, trong đó giá trị boolean của ma trận cho biết liệu có một đường đi (path) trực tiếp giữa hai đỉnh (vertex) hay không.

Ví dụ chúng ta có một đồ thị bên dưới.

Chúng ta có thể biểu diễn đồ thị này dưới dạng ma trận như dưới đây.

Mỗi ô (cell) trong bảng / ma trận trên được biểu diễn dưới dạng Aij, trong đó i và j là các đỉnh. Giá trị của Aij là 1 hoặc 0 tùy thuộc vào việc có cạnh từ đỉnh i đến đỉnh j hay không.

Nếu có một đường đi từ i đến j, thì giá trị của Aij là 1 nếu không thì giá trị của nó là 0. Ví dụ: có một đường đi từ đỉnh 1 đến đỉnh 2, vì vậy A12 là 1 và không có đường đi nào từ đỉnh 1 đến 3, nên A13 là 0.

Trong trường hợp đồ thị vô hướng (undirected graph), ma trận là đối xứng qua đường chéo (diagonal) vì với mọi cạnh (i, j) thì cũng có một cạnh (j, i).

Ưu điểm:

• Các phép toán (operation) cơ bản như thêm một cạnh, xóa một cạnh và kiểm tra xem có cạnh nào từ đỉnh i đến đỉnh j hay không là các phép toán với thời gian không đổi (constant time), cực kỳ hiệu quả về mặt thời gian.
• Nếu đồ thị dày (dense) và số lượng cạnh lớn, ma trận kề (adjacency matrix) nên là lựa chọn đầu tiên. Ngay cả khi đồ thị và ma trận kề là thưa (sparse), chúng ta có thể biểu diễn nó bằng cách sử dụng cấu trúc dữ liệu cho ma trận thưa.
• Tuy nhiên, lợi thế lớn nhất đến từ việc sử dụng ma trận. Những tiến bộ gần đây trong phần cứng cho phép chúng ta thực hiện các phép toán ma trận thậm chí tốn kém trên GPU.
• Bằng cách thực hiện các phép toán trên ma trận kề (adjacency matrix), chúng ta có thể có được những hiểu biết quan trọng về bản chất của đồ thị và mối quan hệ giữa các đỉnh của nó.

Nhược điểm:

• Yêu cầu về không gian VxV của ma trận kề làm cho nó trở thành một memory hog. Các đồ thị ngoài tự nhiên thường không có quá nhiều kết nối và đây là lý do chính tại sao danh sách kề (adjacency list) là lựa chọn tốt hơn cho hầu hết các tác vụ (task).
• Trong khi các phép toán cơ bản là dễ dàng, các phép toán như inEdges và outEdges rất tốn kém khi sử dụng biểu diễn ma trận kề.

Bên dưới là code ma trận kề (adjacency matrix) trong C:

// Adjacency Matrix representation in C

#include 
#define V 4

// Initialize the matrix to zero
void init(int arr[][V]) {
  int i, j;
  for (i = 0; i 

Ứng dụng:

• Tạo bảng định tuyến (routing table) trong mạng (network).
• Tác vụ điều hướng.