Cấu trúc dữ liệu và Giải thuật Bài 46: Giới thiệu Đồ thị (Graph) và các phương pháp biểu diễn (Ma trận kề, Danh sách kề).

Cây Nhị Phân (Binary Tree) mà chúng ta nghiên cứu ở chương trước bản chất chỉ là một mạng lưới bị giới hạn khắt khe: quy luật phân cấp từ trên xuống dưới và tuyệt đối không có sự xuất hiện của vòng lặp. Nhưng thế giới thực không vận hành theo trục dọc tĩnh lặng đó.

Hãy nhìn vào bản đồ các trạm thu phí tự động (AFC) của tuyến Metro Line 1 mà Hiếu đang bảo trì, mạng lưới bạn bè trên mạng xã hội, hay sơ đồ giao tiếp chéo giữa hàng chục Microservices. Chúng là những mạng lưới tự do, nơi mọi điểm đều có quyền kết nối với bất kỳ điểm nào khác, tạo ra các chu trình khép kín. Để mô hình hóa thế giới hỗn mang này vào không gian RAM của máy tính, chúng ta sử dụng Đồ thị (Graph).

1. Giải phẫu Đồ thị: Đỉnh (Vertex) và Cạnh (Edge)

Một đồ thị $G = (V, E)$ được định nghĩa bởi 2 tập hợp:

• $V$ (Vertices - Đỉnh): Đại diện cho các thực thể. (Ví dụ: Các nhà ga Metro như Bến Thành, Ba Son, Suối Tiên).

• $E$ (Edges - Cạnh): Đại diện cho mối quan hệ kết nối giữa 2 đỉnh. (Ví dụ: Đoạn đường ray hoặc tuyến cáp quang tín hiệu nối giữa 2 nhà ga).

Dựa trên tính chất của Cạnh, Đồ thị được chia thành các hệ tư tưởng khác nhau:

• Vô hướng (Undirected) vs Có hướng (Directed): Mối quan hệ bạn bè trên Facebook là vô hướng (A là bạn của B, thì B chắc chắn là bạn của A). Nhưng mạng lưới Follower trên TikTok/X là có hướng (A follow B không có nghĩa là B follow A).

• Không trọng số (Unweighted) vs Có trọng số (Weighted): Nếu chỉ quan tâm ga Bến Thành có nối với ga Ba Son hay không, đó là đồ thị không trọng số. Nhưng nếu bạn cần thuật toán tìm đường đi ngắn nhất, mỗi cạnh phải cõng thêm một con số (khoảng cách thực tế hoặc thời gian chạy tàu) - đó là đồ thị có trọng số.

Để thuật toán có thể chạy được, chúng ta phải chuyển hóa hình vẽ mạng lưới đó thành cấu trúc dữ liệu code. Có 2 trường phái biểu diễn thống trị ngành Khoa học máy tính.

2. Ma trận kề (Adjacency Matrix): Lãng phí để đổi lấy tốc độ

Ma trận kề biểu diễn đồ thị bằng một Mảng 2 chiều (2D Array) có kích thước $V \times V$.

Nếu đồ thị có 5 đỉnh, bạn tạo một ma trận vuông 5x5.

• Nếu có một cạnh nối từ Đỉnh $i$ đến Đỉnh $j$, ta gán Matrix[i][j] = 1 (hoặc bằng trọng số của cạnh đó).

• Nếu không có kết nối, Matrix[i][j] = 0.

Ưu điểm tuyệt đối:

Tốc độ tra cứu là ma thuật $O(1)$. Nếu muốn biết Ga số 2 và Ga số 5 có đường ray nối trực tiếp hay không, CPU chỉ cần check lệnh if matrix[2][5] == 1 trong một tích tắc xung nhịp.

Nhược điểm chí mạng:

Ma trận kề bị mắc kẹt trong lỗ hổng không gian $O(V^2)$.

Nếu mạng lưới User của hệ thống có 1 triệu người, bạn phải cấp phát một ma trận $1,000,000 \times 1,000,000$. Nó sẽ đốt cháy ngay lập tức 1 Terabyte RAM. Đáng sợ hơn, trong thực tế, một user thường chỉ có khoảng vài trăm bạn bè. Hơn 99.99% ô nhớ trong ma trận khổng lồ đó sẽ chứa giá trị 0 (vô dụng). Đây gọi là hiện tượng Đồ thị thưa (Sparse Graph).

3. Danh sách kề (Adjacency List): Sự lựa chọn của Backend hiện đại

Để cứu hệ thống khỏi sự lãng phí tài nguyên của ma trận, các kỹ sư hệ thống sử dụng Danh sách kề. Tư duy của phương pháp này rất thực dụng: Đỉnh nào có kết nối với ai thì mới ghi chép lại, không có thì bỏ qua.

Chúng ta sử dụng một Bảng Băm (Hash Table / Map) hoặc một Mảng 1 chiều. Mỗi Đỉnh sẽ làm Key, và Value là một Danh sách (Slice/Linked List) chứa những người hàng xóm trực tiếp của nó.

Hiệu năng:

• Không gian (RAM): Tuyệt hảo ở mức $O(V + E)$. Bạn chỉ tốn bộ nhớ cho những kết nối thực sự tồn tại. Với 1 triệu User và 5 triệu mối quan hệ, hệ thống chỉ mất vài chục Megabyte RAM thay vì 1 Terabyte.

• Thời gian truy vấn: Để biết $A$ và $B$ có kết nối không, bạn phải quét qua mảng hàng xóm của $A$. Thời gian là $O(k)$ với $k$ là số lượng kết nối của $A$. Chậm hơn $O(1)$ của Ma trận, nhưng hoàn toàn chấp nhận được trong đồ thị thưa.

4. Triển khai Danh sách kề bằng Golang

Khi thiết kế backend bằng Go, việc kết hợp map và slice tạo ra một Danh sách kề vô cùng linh hoạt và thanh lịch cho các đồ thị có hướng (Directed Graph).

Go

package main

import "fmt"

// Định nghĩa cấu trúc Đồ thị bằng Danh sách kề
type Graph struct {
    // Key là tên Đỉnh (ID), Value là Slice chứa danh sách hàng xóm
    adjList map[string][]string
}

// Khởi tạo đồ thị
func NewGraph() *Graph {
    return &Graph{
        adjList: make(map[string][]string),
    }
}

// Thêm Đỉnh mới vào đồ thị
func (g *Graph) AddVertex(v string) {
    if _, exists := g.adjList[v]; !exists {
        g.adjList[v] = []string{} // Khởi tạo Slice rỗng cho hàng xóm
    }
}

// Thêm Cạnh có hướng (Từ v1 -> v2)
func (g *Graph) AddEdge(from, to string) {
    // Trong môi trường Production cần kiểm tra xem Đỉnh đã tồn tại chưa
    g.adjList[from] = append(g.adjList[from], to)
    
    // Nếu là đồ thị VÔ HƯỚNG, bạn phải mở khóa dòng code dưới đây:
    // g.adjList[to] = append(g.adjList[to], from)
}

// In đồ thị ra để kiểm tra
func (g *Graph) Print() {
    for vertex, neighbors := range g.adjList {
        fmt.Printf("Đỉnh %s kết nối tới: %v\n", vertex, neighbors)
    }
}

5. Lựa chọn kiến trúc (Matrix vs List)

Việc chọn Ma trận hay Danh sách kề phụ thuộc hoàn toàn vào mật độ của Đồ thị (Density):

1. Dense Graph (Đồ thị dày đặc): Khi số lượng cạnh cực kỳ lớn, tiệm cận mức $V^2$ (mọi đỉnh gần như đều nối với mọi đỉnh khác). Ví dụ: Các thuật toán tính toán ma trận, định tuyến vệ tinh, thuật toán luồng mạng lõi. Ở đây, Ma trận kề là vua.

2. Sparse Graph (Đồ thị thưa): Khi số lượng cạnh tương đối nhỏ so với khả năng kết nối tối đa ($E \ll V^2$). Mọi hệ thống chúng ta xây dựng hằng ngày (Mạng xã hội, Bản đồ đường đi, Mạng lưới viễn thông, Quan hệ khóa ngoại Database) đều là đồ thị thưa. Ở đây, Danh sách kề là lựa chọn kiến trúc bắt buộc.

Khi đã biểu diễn thành công Đồ thị vào RAM dưới dạng Danh sách kề, thử thách tiếp theo là làm sao để máy tính có thể "đi dạo" qua mạng lưới mạng nhện chằng chịt này mà không bị kẹt vào các vòng lặp chết người.