🕸️ Đồ thị (Graph)

Linked list nối các phần tử theo một đường thẳng, cây (tree) tổ chức chúng theo quan hệ cha-con phân cấp - cả hai đều là những ràng buộc khá chặt về cách các phần tử được kết nối. Đồ thị (graph) bỏ hết những ràng buộc đó: bất kỳ phần tử nào cũng có thể nối với bất kỳ phần tử nào khác, theo bất kỳ số lượng kết nối nào. Đây là mô hình tự nhiên cho những mạng lưới không có “trên dưới” rõ ràng: bạn bè trên mạng xã hội, các trạm trong hệ thống tàu điện, đường bay giữa các thành phố.

Các khái niệm cơ bản

Một đồ thị gồm hai thành phần: tập đỉnh (vertex) và tập cạnh (edge) nối giữa các đỉnh. Vài trục phân loại quan trọng:

Vô hướng vs có hướng: cạnh vô hướng biểu diễn quan hệ “hai chiều” như bạn bè trên Facebook (A là bạn B thì B cũng là bạn A); cạnh có hướng biểu diễn quan hệ “một chiều” như theo dõi trên Instagram (A theo dõi B không có nghĩa B theo dõi lại A).
Có trọng số vs không trọng số: cạnh có thể mang thêm một con số (trọng số) biểu diễn “chi phí” của kết nối đó - ví dụ khoảng cách giữa hai thành phố, hoặc độ thân thiết giữa hai người dùng.
Liên thông (connected): một đồ thị liên thông nếu từ bất kỳ đỉnh nào cũng có đường đi tới mọi đỉnh khác; nếu tồn tại đỉnh nào đó “cô lập”, đồ thị được gọi là không liên thông.

Hai cách biểu diễn đồ thị

Ma trận kề (adjacency matrix)

Dùng một bảng vuông kích thước n × n (với n là số đỉnh), ô [i][j] đánh dấu có/không có cạnh nối đỉnh i và đỉnh j (hoặc lưu trọng số nếu là đồ thị có trọng số).

# 4 đỉnh, ma trận kề dùng số 0/1
adj_matrix = [
    [0, 1, 1, 0],
    [1, 0, 1, 0],
    [1, 1, 0, 1],
    [0, 0, 1, 0],
]
# Kiểm tra đỉnh 0 và 2 có nối nhau không: O(1)
print(adj_matrix[0][2])  # 1

Ưu điểm: kiểm tra hai đỉnh có nối nhau hay không chỉ tốn O(1) - tra thẳng vào ô tương ứng. Nhược điểm: tốn O(n²) bộ nhớ bất kể đồ thị có bao nhiêu cạnh thực sự - với đồ thị thưa (ít cạnh so với số đỉnh), phần lớn ma trận toàn số 0, rất lãng phí.

Danh sách kề (adjacency list)

Với mỗi đỉnh, chỉ lưu danh sách các đỉnh kề với nó (thay vì lưu quan hệ với tất cả n đỉnh):

# key: đỉnh, value: danh sách các đỉnh kề
adj_list = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1, 3],
    3: [2],
}

Ưu điểm: chỉ tốn bộ nhớ tỷ lệ với số cạnh thực sự có (O(n + m) với m là số cạnh), phù hợp với đồ thị thưa - trường hợp phổ biến trong thực tế (một người dùng mạng xã hội chỉ kết bạn với một phần nhỏ trong hàng triệu người dùng khác). Đánh đổi: kiểm tra hai đỉnh có nối nhau hay không chậm hơn ma trận, vì phải duyệt qua danh sách kề của một đỉnh.

Các thao tác cơ bản

Với danh sách kề (biểu diễn phổ biến nhất trong thực hành):

class Graph:
    def __init__(self):
        self.adj = {}

    def add_vertex(self, v):
        self.adj.setdefault(v, [])          # O(1)

    def add_edge(self, u, v):
        self.adj[u].append(v)                # O(1)
        self.adj[v].append(u)                # vô hướng: thêm cả 2 chiều

    def remove_edge(self, u, v):
        self.adj[u].remove(v)                # O(bậc của u) - phải tìm trong danh sách
        self.adj[v].remove(u)

Chú ý thao tác xóa một đỉnh tốn nhiều công hơn hẳn (phải duyệt và dọn dẹp mọi cạnh liên quan đến đỉnh đó trong danh sách kề của các đỉnh khác) - đây là một trong những lý do khiến đồ thị trong thực tế thường được thiết kế để thêm nhiều hơn là xóa.