I. Ma trận kề (Adjacency Matrix)

Giả sử 𝐺=(𝑉,𝐸)G=(V,E) là một đa đồ thị có số đỉnh là 𝑁N. Coi rằng các đỉnh được đánh số từ 11 tới 𝑁N. Khi đó, ta có thể biểu diễn đồ thị bằng một ma trận vuông 𝑎𝑑𝑗adj kích thước 𝑁×𝑁N×N, trong đó:

• 𝑎𝑑𝑗𝑢,𝑣=0,adju,v​=0, nếu (𝑢,𝑣)∉𝐸,𝑢≠𝑣(u,v)∈/E,u=v.
• 𝑎𝑑𝑗𝑢,𝑣=𝑥,adju,v​=x, nếu (𝑢,𝑣)∈𝐸,𝑢≠𝑣(u,v)∈E,u=v và 𝑥x là số lượng cạnh nối giữa 𝑢u và 𝑣v.
• Đối với 𝑎𝑑𝑗𝑢,𝑢adju,u​ với ∀𝑢:1≤𝑢≤𝑁∀u:1≤u≤N, có thể đặt giá trị tùy theo mục đích, thông thường nên đặt bằng 00.

Cài đặt: Việc cài đặt cạnh sẽ thay đổi tùy vào đồ thị là có hướng hay vô hướng. Dưới đây sẽ trình bày cài đặt cho đồ thị vô hướng:

void enter_adjacency_matrix()
{
    cin >> N >> M; // Nhập số đỉnh và số cạnh của đồ thị.

    for (int i = 1; i <= M; ++i)
    {
        int u, v;
        cin >> u >> v;

        adj[u][v]++; // Tăng số cạnh giữa u và v.
        adj[v][u]++; // Nếu là đồ thị có hướng thì không có dòng này.
    }
}

Ví dụ: Đồ thị 𝐺(𝑉,𝐸)G(V,E) dưới đây có 55 đỉnh, 66 cạnh:

Ma trận kề của nó sẽ có dạng như sau:

Ưu điểm của ma trận kề:

• Đơn giản, dễ cài đặt.
• Để kiểm tra hai đỉnh 𝑢u và 𝑣v có kề nhau hay không, chỉ việc kiểm tra trong 𝑂(1)O(1) bằng phép so sánh 𝑎𝑢,𝑣≠0au,v​=0.

Nhược điểm của ma trận kề:

• Luôn luôn tiêu tốn 𝑁2N2 ô nhớ để lưu trữ ma trận kề, dù là trong trường hợp đồ thị ít cạnh hay nhiều cạnh.
• Để xét một đỉnh 𝑢u kề với những đỉnh nào, buộc phải duyệt toàn bộ các đỉnh 𝑣v và kiểm tra điều kiện 𝑎𝑢,𝑣≠0au,v​=0. Như vậy kể cả đỉnh 𝑢u không kề với đỉnh nào, chúng ta vẫn phải duyệt mất 𝑂(𝑁)O(N) để biết được điều đó.

Phù hợp khi nào: Trong các bài toán đồ thị có số lượng đỉnh ít (thường là không vượt quá 300300).

II. Danh sách cạnh (Edge List)

Trong trường hợp biết trước đồ thị có 𝑁N đỉnh, 𝑀M cạnh, ta có thể biểu diễn đồ thị dưới dạng một danh sách lưu các cạnh (𝑢,𝑣)(u,v) của đồ thị đó (nếu là đồ thị có hướng thì mỗi cặp (𝑢,𝑣)(u,v) ứng với một cung 𝑢→𝑣u→v). Vector hoặc mảng là một kiểu dữ liệu rất phù hợp để lưu trữ danh sách cạnh.

Cài đặt:

vector < pair < int, int > > edge_list; // Danh sách cạnh.

void enter_edge_list()
{
    cin >> N >> M;

    for (int i = 1; i <= M; ++i)
    {
        int u, v;
        cin >> u >> v;

        edge_list.push_back({u, v});
    }
}

Ví dụ: Đồ thị 𝐺(𝑉,𝐸)G(V,E) dưới đây 55 đỉnh, 66 cạnh theo thứ tự là: (1,3),(1,4),(3,4),(3,2),(5,3),(2,5)(1,3),(1,4),(3,4),(3,2),(5,3),(2,5):

Danh sách cạnh của nó được biểu diễn bằng một vector \text{edge_list} như sau:

Ưu điểm của danh sách cạnh:

• Trong trường hợp đồ thị ít cạnh, cách biểu diễn này sẽ giúp tiết kiệm không gian lưu trữ.
• Ở một số trường hợp đặc biệt, ta phải xét tất cả các cạnh trên đồ thị thì phương pháp cài đặt này giúp việc duyệt cạnh dễ dàng hơn trong 𝑂(𝑀)O(M) (ví dụ giải thuật tìm cây khung nhỏ nhất Kruskal).

Nhược điểm của danh sách cạnh: Trong trường hợp cần duyệt các đỉnh kề với một đỉnh 𝑢u, bắt buộc phải duyệt qua mọi cạnh, lọc ra các cạnh có chứa đỉnh 𝑢u và xét đỉnh còn lại. Điều này sẽ tốn thời gian nếu đồ thị có nhiều cạnh.

Phù hợp khi nào: Trong các bài toán cần duyệt toàn bộ cạnh, tiêu biểu như trong giải thuật Kruskal.

III. Danh sách kề (Adjacency List)

Để khắc phục nhược điểm của ma trận kề và danh sách cạnh, người ta sử dụng danh sách kề (cũng là cách thường xuyên sử dụng nhất trong các bài toán đồ thị). Trong cách biểu diễn này, với mỗi đỉnh u của đồ thị, ta sẽ tạo ra một dánh sách 𝑎𝑑𝑗𝑢adju​ là các đỉnh kề với nó. Việc cài đặt 𝑎𝑑𝑗𝑢adju​ có thể thực hiện dễ dàng với vector.

Cài đặt:

vector < int > adj[maxn + 1]; // Danh sách kề, maxn là số đỉnh tối đa của đồ thị.

void enter_adjacency_list()
{
    cin >> N >> M; // Số đỉnh và số cạnh của đồ thị.

    for (int i = 1; i <= M; ++i)
    {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v); // Đưa v vào danh sách kề với u.
        adj[v].push_back(u); // Nếu là đồ thị có hướng thì không có dòng này.
    }
}

Ví dụ: Đồ thị 𝐺(𝑉,𝐸)G(V,E) dưới đây gồm 55 đỉnh, 44 cạnh:

Danh sách kề của nó có thể biểu diễn bằng một mảng adj[6]adj[6] gồm các vector (kích thước mảng là 66 do không có đỉnh số 00), mỗi vector adj[𝑢]adj[u] lưu danh sách kề của đỉnh 𝑢u:

Ưu điểm của danh sách kề:

• Duyệt đỉnh kề và các cạnh của đồ thị rất nhanh.
• Tiết kiệm không gian lưu trữ, do vector là kiểu dữ liệu với bộ nhớ động, sẽ chỉ tạo ra các ô nhớ tương ứng với số lượng đỉnh kề.

Nhược điểm của danh sách kề: Khi cần kiểm tra (𝑢,𝑣)(u,v) có phải là một cạnh của đồ thị hay không thì bắt buộc phải duyệt toàn bộ danh sách kề của 𝑢u hoặc của 𝑣v.

Phù hợp khi nào: Hầu hết trong mọi bài toán đồ thị đều nên sử dụng, chỉ trừ các bài toán cần duyệt toàn bộ cạnh của đồ thị.