Bài 18.1. Các cách biểu diễn đồ thị: ma trận kề, danh sách kề

Chào mừng trở lại với hành trình chinh phục Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ mở cánh cửa bước vào thế giới của đồ thị (Graphs). Trước khi có thể áp dụng các thuật toán tìm kiếm đường đi ngắn nhất, tìm cây bao trùm hay phân tích liên kết mạng, chúng ta cần biết cách "lưu trữ" đồ thị này trong bộ nhớ máy tính sao cho hiệu quả.

Có hai cách tiếp cận kinh điển cho việc này: Ma trận kề (Adjacency Matrix) và Danh sách kề (Adjacency List). Mỗi cách đều vẽ nên một bức tranh về cấu trúc đồ thị, nhưng với nét cọ và màu sắc khác nhau, dẫn đến hiệu quả khác nhau tùy thuộc vào "bức tranh" (đồ thị) bạn đang xử lý.

1. Đồ thị là gì? (Nhắc lại nhanh)

Trước khi đi sâu vào biểu diễn, hãy ôn lại một chút về đồ thị. Một đồ thị $G$ được định nghĩa bởi một tập hợp các đỉnh (vertices) $V$ và một tập hợp các cạnh (edges) $E$. Mỗi cạnh nối hai đỉnh với nhau.

Đồ thị vô hướng (Undirected Graph): Cạnh nối hai đỉnh $u$ và $v$ là "hai chiều", có nghĩa là nếu có cạnh từ $u$ đến $v$ thì cũng có cạnh từ $v$ đến $u$.
Đồ thị có hướng (Directed Graph): Cạnh nối hai đỉnh $u$ và $v$ là "một chiều", có nghĩa là có cạnh từ $u$ đến $v$ không suy ra có cạnh từ $v$ đến $u$. Cạnh có hướng thường được ký hiệu là $(u, v)$, nghĩa là từ $u$ sang $v$.
Đồ thị có trọng số (Weighted Graph): Mỗi cạnh được gán thêm một giá trị (trọng số), thường biểu thị chi phí, khoảng cách, thời gian, v.v., để đi qua cạnh đó.

Việc lựa chọn cách biểu diễn sẽ phụ thuộc vào việc đồ thị của bạn là vô hướng hay có hướng, có trọng số hay không, và quan trọng nhất là số lượng đỉnh ($V$) và số lượng cạnh ($E$) có quan hệ với nhau như thế nào (đồ thị dày đặc hay thưa thớt).

2. Biểu diễn bằng Ma trận kề (Adjacency Matrix)

Hãy tưởng tượng bạn có $V$ đỉnh. Ma trận kề sử dụng một ma trận vuông kích thước $V \times V$ để lưu trữ thông tin về các cạnh.

Gọi ma trận là $Adj$. Các hàng và cột của ma trận này tương ứng với các đỉnh của đồ thị (thường đánh số từ 0 hoặc 1 đến $V-1$ hoặc $V$).

Đối với đồ thị vô hướng không trọng số: $Adj[i][j] = 1$ nếu có cạnh nối đỉnh $i$ và đỉnh $j$, và $Adj[i][j] = 0$ nếu không có.
Đối với đồ thị có hướng không trọng số: $Adj[i][j] = 1$ nếu có cạnh từ đỉnh $i$ đến đỉnh $j$, và $Adj[i][j] = 0$ nếu không có.
Đối với đồ thị có trọng số: $Adj[i][j]$ lưu trọng số của cạnh nối đỉnh $i$ và đỉnh $j$. Nếu không có cạnh, ta có thể dùng một giá trị đặc biệt, ví dụ như vô cùng ($\infty$), hoặc 0 (nếu trọng số luôn dương) để biểu thị.

Trong đồ thị vô hướng không trọng số, ma trận kề sẽ đối xứng qua đường chéo chính ($Adj[i][j] = Adj[j][i]$).

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

Kiểm tra sự tồn tại của cạnh: Việc kiểm tra xem có cạnh nối giữa đỉnh $i$ và đỉnh $j$ hay không là cực kỳ nhanh chóng, chỉ cần truy cập vào phần tử $Adj[i][j]$. Độ phức tạp là O(1).
Đơn giản để cài đặt: Cài đặt ma trận 2D là thao tác cơ bản trong hầu hết các ngôn ngữ lập trình.

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

Tốn bộ nhớ: Kích thước của ma trận luôn là $V \times V$, bất kể số lượng cạnh $E$. Điều này có nghĩa là bộ nhớ yêu cầu là O($V^2$). Nếu đồ thị có rất nhiều đỉnh nhưng rất ít cạnh (đồ thị thưa thớt - sparse graph), phần lớn các phần tử trong ma trận sẽ là 0 hoặc giá trị "không có cạnh", gây lãng phí bộ nhớ khủng khiếp.
Liệt kê các đỉnh kề: Để tìm tất cả các đỉnh kề với đỉnh $i$, bạn phải duyệt qua toàn bộ hàng thứ $i$ của ma trận, từ cột 0 đến $V-1$. Độ phức tạp là O($V$). Điều này có thể chậm nếu bạn chỉ cần tìm các đỉnh kề của một đỉnh có ít bậc (degree).

Ví dụ cài đặt Ma trận kề trong C++:

Giả sử chúng ta có một đồ thị vô hướng với 5 đỉnh (đánh số từ 0 đến 4) và các cạnh sau: (0,1), (0,4), (1,2), (1,3), (1,4), (2,3), (3,4).

#include <iostream>
#include <vector>

int main() {
    // Số lượng đỉnh
    int V = 5;

    // Khởi tạo ma trận kề V x V với tất cả giá trị ban đầu là 0
    // Sử dụng vector của vector để linh hoạt
    std::vector<std::vector<int>> adjMatrix(V, std::vector<int>(V, 0));

    // Thêm các cạnh vào đồ thị vô hướng
    // Cạnh (0, 1)
    adjMatrix[0][1] = 1;
    adjMatrix[1][0] = 1; // Đồ thị vô hướng nên thêm cả chiều ngược lại

    // Cạnh (0, 4)
    adjMatrix[0][4] = 1;
    adjMatrix[4][0] = 1;

    // Cạnh (1, 2)
    adjMatrix[1][2] = 1;
    adjMatrix[2][1] = 1;

    // Cạnh (1, 3)
    adjMatrix[1][3] = 1;
    adjMatrix[3][1] = 1;

    // Cạnh (1, 4)
    adjMatrix[1][4] = 1;
    adjMatrix[4][1] = 1;

    // Cạnh (2, 3)
    adjMatrix[2][3] = 1;
    adjMatrix[3][2] = 1;

    // Cạnh (3, 4)
    adjMatrix[3][4] = 1;
    adjMatrix[4][3] = 1;

    // In ra ma trận kề (không bắt buộc, chỉ để minh họa)
    std::cout << "Ma tran ke:" << std::endl;
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            std::cout << adjMatrix[i][j] << " ";
        }
        std::cout << std::endl;
    }

    // Minh họa kiểm tra sự tồn tại của cạnh (O(1))
    int u = 1, v = 4;
    if (adjMatrix[u][v] == 1) {
        std::cout << "\nCo canh giua " << u << " va " << v << std::endl;
    } else {
        std::cout << "\nKhong co canh giua " << u << " va " << v << std::endl;
    }

    u = 0, v = 2;
     if (adjMatrix[u][v] == 1) {
        std::cout << "Co canh giua " << u << " va " << v << std::endl;
    } else {
        std::cout << "Khong co canh giua " << u << " va " << v << std::endl;
    }

    // Minh họa liệt kê các đỉnh kề của một đỉnh (O(V))
    int startNode = 1;
    std::cout << "\nCac dinh ke voi dinh " << startNode << ":" << std::endl;
    for (int i = 0; i < V; ++i) {
        if (adjMatrix[startNode][i] == 1) {
            std::cout << i << " ";
        }
    }
    std::cout << std::endl;


    return 0;
}

Giải thích code Ma trận kề:

Chúng ta sử dụng std::vector<std::vector<int>> adjMatrix để tạo một ma trận 2D. adjMatrix(V, std::vector<int>(V, 0)) tạo ra một ma trận $V \times V$ và gán giá trị 0 cho tất cả các phần tử ban đầu.
Để thêm cạnh vô hướng giữa đỉnh u và v, chúng ta đặt adjMatrix[u][v] = 1 và adjMatrix[v][u] = 1. Nếu là đồ thị có hướng từ u đến v, chỉ cần adjMatrix[u][v] = 1.
Để kiểm tra có cạnh giữa u và v không, chỉ cần kiểm tra adjMatrix[u][v]. Nếu giá trị là 1 (hoặc khác giá trị "không có cạnh" trong đồ thị có trọng số), thì có cạnh.
Để tìm các đỉnh kề với đỉnh startNode, chúng ta duyệt qua tất cả các cột i trong hàng startNode. Nếu adjMatrix[startNode][i] là 1, thì đỉnh i kề với startNode.

Ma trận kề rất phù hợp với đồ thị dày đặc (dense graph), tức là đồ thị có số cạnh $E$ gần với $V^2$. Trong trường hợp này, sự lãng phí bộ nhớ không quá nghiêm trọng, và ưu điểm kiểm tra cạnh nhanh O(1) trở nên rất giá trị.

3. Biểu diễn bằng Danh sách kề (Adjacency List)

Danh sách kề là một cách tiếp cận khác, sử dụng một mảng (hoặc vector) mà mỗi phần tử của mảng này đại diện cho một đỉnh. Tại mỗi phần tử mảng i, chúng ta lưu trữ một danh sách (có thể là std::vector, std::list, v.v.) chứa tất cả các đỉnh kề với đỉnh $i$.

Đối với đồ thị vô hướng không trọng số: Danh sách ở vị trí i chứa tất cả các đỉnh $j$ mà có cạnh nối với $i$. Nếu có cạnh $(i, j)$, thì $j$ sẽ nằm trong danh sách của $i$, và $i$ sẽ nằm trong danh sách của $j$.
Đối với đồ thị có hướng không trọng số: Danh sách ở vị trí i chỉ chứa tất cả các đỉnh $j$ mà có cạnh từ $i$ đến $j$.
Đối với đồ thị có trọng số: Danh sách ở vị trí i sẽ chứa các cặp (pair) hoặc cấu trúc dữ liệu tương tự, lưu trữ đỉnh kề và trọng số của cạnh tương ứng. Ví dụ: một danh sách các cặp {đỉnh_kề, trọng_số}.

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

Tiết kiệm bộ nhớ: Bộ nhớ yêu cầu tỉ lệ thuận với số lượng đỉnh và số lượng cạnh. Đối với đồ thị vô hướng, mỗi cạnh $(u, v)$ được lưu trữ hai lần (trong danh sách của $u$ và trong danh sách của $v$). Đối với đồ thị có hướng, mỗi cạnh $(u, v)$ được lưu trữ một lần (trong danh sách của $u$). Tổng cộng, bộ nhớ yêu cầu là O($V + E$). Đây là một ưu điểm lớn so với Ma trận kề khi xử lý đồ thị thưa thớt (sparse graph) (khi $E$ nhỏ hơn đáng kể so với $V^2$).
Liệt kê các đỉnh kề hiệu quả: Để tìm tất cả các đỉnh kề với đỉnh $i$, bạn chỉ cần duyệt qua danh sách của đỉnh $i$. Độ phức tạp là O(degree($i$)), trong đó degree($i$) là số bậc của đỉnh $i$ (số cạnh nối với $i$). Điều này nhanh hơn nhiều so với O(V) của Ma trận kề khi đỉnh có bậc thấp.

Nhược điểm của Danh sách kề:

Kiểm tra sự tồn tại của cạnh: Để kiểm tra xem có cạnh nối giữa đỉnh $i$ và đỉnh $j$ hay không, bạn phải duyệt qua danh sách của đỉnh $i$ để xem $j$ có nằm trong đó không. Độ phức tạp là O(degree($i$)) trong trường hợp xấu nhất. Đối với các đồ thị có bậc lớn, thao tác này có thể chậm hơn đáng kể so với O(1) của Ma trận kề.
Phức tạp hơn một chút khi cài đặt: Việc quản lý các danh sách động (như std::vector hoặc std::list) đòi hỏi cấu trúc code phức tạp hơn so với một ma trận 2D đơn giản.

Ví dụ cài đặt Danh sách kề trong C++:

Sử dụng lại đồ thị vô hướng với 5 đỉnh (đánh số 0-4) và các cạnh: (0,1), (0,4), (1,2), (1,3), (1,4), (2,3), (3,4).

#include <iostream>
#include <vector>
#include <list> // Hoặc có thể dùng std::vector cho danh sách kề

int main() {
    // Số lượng đỉnh
    int V = 5;

    // Khởi tạo danh sách kề.
    // Sử dụng vector của list để mỗi đỉnh có một danh sách các đỉnh kề.
    // Có thể dùng vector của vector: std::vector<std::vector<int>> adjList(V);
    std::vector<std::list<int>> adjList(V);

    // Thêm các cạnh vào đồ thị vô hướng
    // Cạnh (0, 1)
    adjList[0].push_back(1); // Thêm 1 vào danh sách của 0
    adjList[1].push_back(0); // Thêm 0 vào danh sách của 1 (vì vô hướng)

    // Cạnh (0, 4)
    adjList[0].push_back(4);
    adjList[4].push_back(0);

    // Cạnh (1, 2)
    adjList[1].push_back(2);
    adjList[2].push_back(1);

    // Cạnh (1, 3)
    adjList[1].push_back(3);
    adjList[3].push_back(1);

    // Cạnh (1, 4)
    adjList[1].push_back(4);
    adjList[4].push_back(1);

    // Cạnh (2, 3)
    adjList[2].push_back(3);
    adjList[3].push_back(2);

    // Cạnh (3, 4)
    adjList[3].push_back(4);
    adjList[4].push_back(3);


    // In ra danh sách kề (không bắt buộc, chỉ để minh họa)
    std::cout << "Danh sach ke:" << std::endl;
    for (int i = 0; i < V; ++i) {
        std::cout << "Dinh " << i << ": ";
        for (int neighbor : adjList[i]) {
            std::cout << neighbor << " ";
        }
        std::cout << std::endl;
    }

    // Minh họa kiểm tra sự tồn tại của cạnh (O(degree(u)))
    int u = 1, v = 4;
    bool edgeExists = false;
    for (int neighbor : adjList[u]) {
        if (neighbor == v) {
            edgeExists = true;
            break;
        }
    }
    if (edgeExists) {
        std::cout << "\nCo canh giua " << u << " va " << v << std::endl;
    } else {
        std::cout << "\nKhong co canh giua " << u << " va " << v << std::endl;
    }

    u = 0, v = 2;
    edgeExists = false;
    for (int neighbor : adjList[u]) {
        if (neighbor == v) {
            edgeExists = true;
            break;
        }
    }
    if (edgeExists) {
        std::cout << "Co canh giua " << u << " va " << v << std::endl;
    } else {
        std::cout << "Khong co canh giua " << u << " va " << v << std::endl;
    }

    // Minh họa liệt kê các đỉnh kề của một đỉnh (O(degree(startNode)))
    int startNode = 1;
    std::cout << "\nCac dinh ke voi dinh " << startNode << ":" << std::endl;
    for (int neighbor : adjList[startNode]) {
        std::cout << neighbor << " ";
    }
    std::cout << std::endl;

    return 0;
}

Giải thích code Danh sách kề:

Chúng ta sử dụng std::vector<std::list<int>> adjList. adjList là một vector có kích thước V. Mỗi phần tử adjList[i] là một std::list<int> lưu trữ các đỉnh kề của đỉnh i. (Bạn hoàn toàn có thể thay std::list bằng std::vector cho đơn giản nếu không cần chèn/xóa hiệu quả ở giữa danh sách).
Để thêm cạnh vô hướng giữa đỉnh u và v, chúng ta sử dụng adjList[u].push_back(v) và adjList[v].push_back(u). Nếu là đồ thị có hướng từ u đến v, chỉ cần adjList[u].push_back(v).
Để kiểm tra có cạnh giữa u và v không, chúng ta phải duyệt qua danh sách adjList[u] để tìm xem có đỉnh v trong đó không.
Để tìm các đỉnh kề với đỉnh startNode, chúng ta chỉ cần duyệt qua danh sách adjList[startNode] bằng vòng lặp dựa trên phạm vi (for (int neighbor : adjList[startNode])).

Đối với đồ thị thưa thớt (sparse graph), Danh sách kề là lựa chọn tối ưu về mặt bộ nhớ và thường hiệu quả hơn cho các thuật toán duyệt đồ thị như DFS (Depth First Search) và BFS (Breadth First Search) vì chúng chủ yếu cần liệt kê các đỉnh kề.

Nếu là đồ thị có trọng số, bạn sẽ lưu trữ các cặp {đỉnh_kề, trọng_số} trong danh sách. Ví dụ std::vector<std::list<std::pair<int, int>>> adjListWeighted(V);. Khi thêm cạnh có trọng số từ u đến v với trọng số w: adjListWeighted[u].push_back({v, w});.

4. So sánh Ma trận kề và Danh sách kề

Đây là bảng tóm tắt giúp bạn dễ dàng so sánh hai phương pháp:

Đặc điểm	Ma trận kề (Adjacency Matrix)	Danh sách kề (Adjacency List)
Bộ nhớ	O($V^2$)	O($V + E$)
Kiểm tra cạnh (u, v)?	O(1)	O(degree(u)) (xấu nhất O(V))
Liệt kê đỉnh kề của u?	O($V$)	O(degree(u))
Phù hợp với	Đồ thị dày đặc (Dense Graphs)	Đồ thị thưa thớt (Sparse Graphs)
Cài đặt	Đơn giản hơn	Phức tạp hơn một chút

Bài tập ví dụ:

[Graph]. Danh sách cạnh sang ma trận kề.

Cho đồ thị vô hướng G=<'V,E'> được biểu diễn dưới dạng danh sách cạnh. Hãy viết chương trình thực hiện chuyển đổi biểu diễn đồ thị dưới dạng ma trận kề.

Input Format

Dòng đầu tiên chứa 2 số n, m là số đỉnh và số cạnh của đồ thị. ( 1≤ n ≤1000, 1 ≤ m ≤ n*(n-1)/2 ) M dòng tiếp theo mỗi dòng là 2 số u, v biểu diễn cạnh u, v của đồ thị ( 1 ≤ u, v ≤ n). Các cạnh được liệt kê theo thứ tự tăng dần của các đỉnh đầu

Constraints

Output Format

In ra ma trận kề tương ứng của đồ thị.

Ví dụ:

Dữ liệu vào

Dữ liệu ra

Đây là hướng dẫn giải bài tập chuyển đổi danh sách cạnh sang ma trận kề bằng C++:

Đọc Input: Đọc hai số nguyên n (số đỉnh) và m (số cạnh).
Khởi tạo Ma trận Kề:
- Sử dụng một mảng 2 chiều hoặc std::vector<std::vector<int>> có kích thước n x n để biểu diễn ma trận kề.
- Khởi tạo tất cả các phần tử của ma trận này bằng 0.
Xử lý Danh sách Cạnh:
- Lặp lại m lần (tương ứng với mỗi cạnh).
- Trong mỗi lần lặp, đọc hai số nguyên u và v biểu diễn một cạnh.
- Lưu ý rằng đỉnh trong input là 1-based (từ 1 đến n). Trong lập trình C++, mảng thường là 0-based. Do đó, cần chuyển đổi chỉ số: u-1 và v-1.
- Vì đồ thị là vô hướng, cạnh (u, v) tồn tại nghĩa là có kết nối từ u đến v VÀ từ v đến u.
- Đặt các phần tử tương ứng trong ma trận kề bằng 1: ma_tran_ke[u-1][v-1] = 1; và ma_tran_ke[v-1][u-1] = 1;.
In Ma trận Kề:
- Duyệt qua ma trận kề theo từng hàng (từ 0 đến n-1).
- Trong mỗi hàng, duyệt qua từng cột (từ 0 đến n-1).
- In giá trị của phần tử ma_tran_ke[i][j].
- In một khoảng trắng sau mỗi phần tử (trừ phần tử cuối cùng trong hàng).
- Sau khi in xong một hàng, in một ký tự xuống dòng (\n).

Tóm tắt các bước chính:

Đọc n, m.
Tạo ma trận n x n toàn số 0.
Với mỗi cạnh (u, v): đặt matrix[u-1][v-1] = 1 và matrix[v-1][u-1] = 1.
In ma trận theo định dạng yêu cầu.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.