Giới thiệu

Khi lập trình giải các bài toán theo mô hình đồ thị, việc đầu tiên cần làm là phải biểu diễn được đồ thị trong máy tính.

Có rất nhiều cách để biểu diễn đồ thị, mỗi cách dùng một cấu trúc dữ liệu khác nhau. Tùy vào tính chất bài toán cần giải quyết, có thể cách biểu diễn này thuận tiện nhưng cách kia thì không.

Trong chủ đề này, chúng ta sẽ cùng khảo sát qua các cách biểu diễn của đồ thị và phân tích hiệu quả của nó trong những bài toán cụ thể.

Tài liệu tham khảo:

1. Tài liệu giáo khoa chuyên Tin quyển 1, Hồ Sỹ Đàm

2. Bài giảng của tiến sỹ Nguyễn Nhật Duy

3. GeeksforGeeks - Graph implementation

Ma trận kề

Với một đơn đồ thị G = (V, E) với |V| = n, ta đánh số các đỉnh từ 1 đến n. Ma trận kề của nó là một ma trận vuông A = {aij}nxn được xây dựng theo cách sau:

Ví dụ:

Đối với đa đồ thị thì aij được biểu diễn bằng số cạnh nối i và j

Tính chất của ma trận kề

• Ma trận kề của đồ thị vô hướng là đối xứng: a[i,j] = a[j,i]. Điều này không đúng với đồ thị có hướng.

• Nếu đồ thị vô hướng:

Tổng dòng thứ i = Tổng cột thứ i = deg(i)

• Nếu đồ thị có hướng:

Tổng dòng i = deg+(i), Tổng cột i = deg -(i)

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

• Đơn giản, trực quan, dễ cài đặt trên máy tính.

• Để kiểm tra hai đỉnh u, v có kề nhau hay không, ta chỉ cần kiểm tra xem auv có khác không hay không.

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

• Bất kể đồ thị thưa hay dày, tức là số cạnh nhiều hay ít, ma trận kề luôn cần n^2 ô nhớ để lưu --> Tốn bộn nhớ.

• Các bài toán cần liệt kê tất cả các đỉnh kề với định u cho trước, ta luôn phải duyệt toàn mà trận, trong khi có trường hợp u là đỉnh treo hoặc đỉnh cô lập thì điều này là lãng phí.

Nhiệm vụ 1. Tạo file 'MATRANKE.INP' để lưu đồ thị sau đây bằng ma trận kề. Sau đó viết một chương trình đọc đồ thị này và hiển thị lên máy tính.

Danh sách cạnh

Với đồ thị G = (V, E) với |V| = n và |E| = m, ta có thể liệt kê tất cả các cạnh của nó vào một danh sách, mỗi phần tử của danh sách này là một cặp (x,y) tương ứng với một cạnh của E. Trong trường hợp đồ thị có hướng thì mỗi cặp (x, y) tương ứng một cung, x là đỉnh đầu, y là đỉnh cuối. Cách biểu diễn này gọi là danh sách cạnh.

Xây dựng danh sách cạnh

• Dùng mảng

• Dùng danh sách liên kết

• Hoặc bất cứ cấu trúc dữ liệu nào có thể lưu được danh sách các cạnh theo mô tả trên.

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

• Trong trường hợp đồ thị thưa, cách biểu diễn bằng danh sách cạnh là rất tiết kiệm bộ nhớ.

• Nhiều thuật toán trên đồ thị cần duyệt qua tất cả các cạnh của đồ thị thì việc cài đặt bằng danh sách cạnh thể hiện ưu thế rõ rệt.

Nhược điểm của danh sách cạnh

• Nhược điểm cơ bản nhất của danh sách cạnh là khi ta cần duyệt qua tất cả các đỉnh kề với đỉnh v thì buộc phải duyệt qua hết cách cạnh, lọc ra những cạnh có v.

• Việc kiểm tra hai đỉnh u, v có kề nhau hay không cũng phải duyệt qua tất cả các cạnh. Nếu đồ thị dày, việc này khá tồn thời gian.

Nhiệm vụ 2. Tạo một file 'DANHSACHCANH.INP' để lưu đồ thị sau đây bằng danh sách cạnh. Viết chương trình đọc vào đồ thị này rồi in lên màn hình.

Nhiệm vụ 3. Sau khi đọc vào ma trận kề ở nhiệm vụ 1, ngoài việc in ma trận lên màn hình, em hãy in thêm bật của từng đỉnh.

Nhiệm vụ 4. Sau khi đọc vào danh sách cạnh ở nhiệm vụ 2, ngoài việc in danh sách lên màn hình, em hãy in ra danh sách các đỉnh kề với từng đỉnh. 

Ví dụ: 

0: 1, 2, 4

1: 0, 2, 4

...

Danh sách kề

Để khắc phục nhược điểm của ma trận kề và danh sách cạnh được nêu ở trên, người ta đề xuất cách biểu diễn thứ ba bằng danh sách kề, tức là biểu diễn tương ứng 1 đỉnh bằng danh sách cách đỉnh kề với nó.

Với đồ thị có hướng, ta có hai thứ tự để biểu diện danh sách kề:

• Forward Star: với mỗi đỉnh u, ta lưu trữ một danh sách adj[u] gồm các đỉnh v nối từ u.

             adj[u] = {v| (u,v) ∈  E}

• Reverse Star: với mỗi đỉnh v, ta lưu trữ một danh sách adj[v] gồm các đỉnh u nối tới v.

             adj[v] = {u| (u,v) ∈  E}

Với đồ thị vô hướng, ta cần chuyển sang phiên bản có hướng của nó để biểu diễn (lưu ý ràng tập cạnh nhân đôi).

Người ta có nhiều cấu trúc dữ liệu để biểu diễn được danh sách kề. Tuy nhiên, hai cách phổ biến nhất là mảng và danh sách liên kết.

Biểu diễn danh sách kề bằng mảng

Dùng một mảng adj[1...m] chứa các đỉnh, mảng này được chia làm n đoạn, đoạn thứ u trong mảng lưu danh sách các đỉnh kề với u. Ta cần dùng thêm một mảng head[1...n+1] để lưu vị trí một đoạn nằm từ đâu đến đâu trong adj.  head[u] bằng chỉ số đứng liền trước đoạn thứ u, head[n+1] = m. Khi đó các đỉnh kề với u sẽ nằm trong đoạn:

adj[head[u]+1...head[u+1]]

Ví dụ:

Nhiệm vụ 5. Hãy dùng mảng biểu diễn danh sách kề cho đồ thị sau đây

Biểu diễn danh sách kề bằng danh sách liên kết

Trong cách biểu diễn này, với mỗi định u ta cho một List[u] làm chốt của một danh sách các đỉnh kề với u.

Ví dụ:

Để cài đặt danh sách kề bằng linked list, chúng ta thực hiện như sau:

Bước 1. Tạo một mảng lưu các danh sách, mỗi phần tử là một đỉnh của đồ thị.

Bước 2. Cứ mỗi định trong mảng, ta khởi tạo một linked list cho nó.

Bước 3. Cứ mỗi cạnh (u, v) trong đồ thị vô hướng, ta add v và linked list của u và add u vào linked list của v. Với đồ thị có hướng chỉ cần làm một chiều.

Lưu ý: Việc triển khai linked list cần nắm vững các kiến thức về con trỏ và cấp phát bộ nhớ động.

Code minh họa

# include <iostream.h> 

# include <stdlib.h>

const maxV = 99;

typedef struct Node { 

         int v;

         struct Node*next;

 }node;

int j, x, y, m, n, v ; node *p, *ke[maxV];

int main() {

        cout<<"Cho so canh va so dinh cua do thi: "; cin>>m>>n;

        for(j=0;j<n;j++) 

               ke[j]=NULL;

        for(j=1;j<=m;j++) {

               cout<<"Cho dinh dau, dinh cuoi cua canh "<<j<<":"; 

               cin>>x>>y;

               p = (node*)malloc(sizeof(node)); 

               p->v = x;

               p->next = ke[y]; 

               ke[y]=p;

               p = (node*)malloc(sizeof(node)); 

               p->v = y;

               p->next = ke[x]; 

               ke[x]=p;

        }

}

Nguồn: TS. Lê Nhật Duy

Nhiệm vụ 6. Hãy tự code lại đề lưu trữ đồ thị trên bằng danh sách kề sử dụng Linked List.

Nhiệm vụ 7. Nếu muốn kiểm tra (u,v) có phải là cạnh hay không, thì ma trận kề hay danh sách kề tốt hơn? tại sao?

Danh sách liên thuộc

Danh sách liên thuộc là dạng mở rộng của danh sách kề. Thay vì biểu diễn một danh sách các đỉnh kề với đỉnh u, danh sách liên thuộc sẽ biểu diễn bằng một danh sách các cạnh liên thuộc với u. Chúng ta có thể cải tiến các thuật toán cài đặt biểu diễn danh sách kề để biểu diễn danh sách liên thuộc.

Biểu diễn danh sách lien thuộc bằng mảng (ma trận liên thuộc)

Ma trận liên thuộc là ma trận B hai chiều n x m, với n = |V|, m = |E|. Trong đó:

Ví dụ:

Cài đặt

Giả định ta đang xây dựng cho đồ thị có hướng và cũng đã có sẵn danh sách cạnh (cung) tương ứng. Nếu ta xây dựng cho mỗi định một danh sách cung đi ra khỏi nó thì sẽ có n danh sách. Dựa trên danh sách cạnh có sẵn, ta cần bổ sung thêm hai mảng head[1...n] và link[1...m] để:

head[u] là chỉ số cung đầu tiên trong danh sách liên thuộc của đỉnh u. Nếu danh sách sách liên thuộc của u là rỗng, head[u] được gán bằng 0.

link[i] là chỉ số cung kế tiếp của cung e[i] trong danh sách liên thuộc chứa cung e[i]. Trường hợp e[i] là cung cuối cùng của một danh sách liên thuộc, link[i] được gán bằng 0.

Code minh họa:

//Khởi tạo danh sách liên thuộc của các đỉnh bằng rỗng:

for(int i =0; i<n; i++){

      head[u] = 0;

}

//Duyệt qua danh sách cạnh, mỗi khi duyệt qua cung (x, y), ta móc nối cung này vào danh sách liên thuộc các cung đi ra khỏi x.

for(int i = 0; i<m; i++){

      if(e[i].x = x){

            link[i] = head[x];

            head[x] = i; 

     }

}

Nhiệm vụ 8. Biểu diễn ma trận liên thuộc của hai đồ thị sau đây

Biểu diễn danh sách cạnh bằng Linked list

Để biểu diễn danh sách liên thuộc bằng linked list, ta có nhiều cách khai báo cấu trúc cạnh và đỉnh, sau đây là một đề xuất:

Đầu tiền xây dựng cấu trúc cho cạnh:

Sau đó khai báo cấu trúc đỉnh:

struct Vertex{

         int x;

         int y;

         Edge* EdgeOut; //để móc vào cạnh đầu tiên

}

Tuy nhiên, trong lập trình hiện đại, người ta thường dùng cấu trúc Vector và Pair trong STL của C++ để cài đặt đồ thị nhằm tận dụng những thư viện, hàm sẵn có của chúng.

Các em có thể tham khảo một cách cài đặt đồ thị sau dùng vector<pair> khá thuận tiện.

Graph implementation using STL for competitive programming

Nhiệm vụ 9: Cho đồ thị có hướng sau cùng hình ảnh về danh sách kề của nó, em hãy lập trình để lưu đồ thị này ở đúng dạng được mô tả rồi xuất lên màn hình theo input gợi ý:

Nhiệm vụ 10. Cho đồ thị sau đây, em hãy cài đặt danh sách liên thuộc cho nó và xuất ra output theo định dạng gợi ý: