Danh sách kề (Adjacency list)
This entry is part 10 of 16 in the series Cấu trúc dữ liệu
Ví dụ một đồ thị vô hướng 
Biểu diễn đồ thị phía trên dưới dạng mảng của các danh sách liên kết
Trong bài viết này, bạn sẽ cùng Lập Trình Không Khó tìm hiểu về danh sách kề (tiếng anh: adjacency list). Bài viết sẽ trình bày từng bước chi tiết để bạn đọc có thể hiểu được cấu trúc dữ liệu danh sách kề, phân tích ưu nhược điểm và ứng dụng của nó. Cũng trong bài viết này, chúng ta sẽ cùng nhau đi cài đặt cấu trúc danh sách kề sử dụng ngôn ngữ C/C++.
Để nắm được kiến thức của bài viết này, bạn nên có kiến thức về:
Chúng ta cùng đi tìm hiểu về danh sách kề nào!
NỘI DUNG BÀI VIẾT
Danh sách kề là gì?
Danh sách kề (Adjacency list) biểu diễn một đồ thị (graph) dưới dạng một mảng các danh sách liên kết. Trong đó, chỉ số mảng đại diện cho đỉnh của đồ thị và các phần tử trong danh sách liên kết của đỉnh đó là cách đỉnh có kết nối với đỉnh đó.
Lấy ví dụ với một đồ thị dưới đây:
Với đồ thị phía trên, chúng ta có thể biểu diễn nó vào bộ nhớ máy tính dưới dạng một mảng các danh sách liên kết như hình vẽ dưới đây:
Đồ thị của chúng ta có 4 đỉnh (0, 1, 2 và 3). Do đó, chúng ta cũng sẽ có 4 danh sách liên kết cho 4 đỉnh đó. Trong mỗi danh sách liên kết là các Node đại diện cho các đỉnh có liên kết với Node head.
Ví dụ:
- Danh sách liên kết cho đỉnh 0 (head) có 3 Node phía sau lần lượt là (1, 2 và 3) thể hiện rằng các cặp đỉnh (0, 1), (0,2) và (0, 3) có kết nối.
- Tương tự, danh sách liên kết của đỉnh 2 (head) có 2 Node phía sau lần lượt là (0 và 2) thể hiện rằng các cặp đỉnh (2, 0) và (2,1) có kết nối.
Ưu điểm của danh sách kề
- So với ma trận kề (adjacency matrix), biểu diễn đồ thị dưới dạng danh sách kề giúp tiết kiệm bộ nhớ hơn. Ta sẽ thấy rõ điều này khi biểu diễn đồ thị có số lượng lớn đỉnh nhưng có ít số cạnh (kết nối).
- Việc duyệt các đỉnh kề với một đỉnh nào đó cũng cực kỳ nhanh chóng do mỗi đỉnh chỉ kết nối tới các đỉnh kề với nó.
Nhược điểm của danh sách kề
- Do sử dụng danh sách liên kết, việc kiểm tra 2 đỉnh bất kỳ có kết nối hay không cần phải duyệt tuần tự từ node head, sẽ chậm hơn so với việc kiểm tra nếu cài đặt bằng ma trận kề.
Cài đặt danh sách kề
Để đơn giản, mục hướng dẫn cài đặt này chúng ta sẽ làm việc với:
- Đồ thị vô hướng và không có trọng số
- Danh sách liên kết đơn
# Cấu trúc của danh sách kề
Do danh sách kề là mảng của các danh sách liên kết, nên chúng ta cần định nghĩa cấu trúc Node cho các phần tử của danh sách liên kết:
|
1 2 3 4 5 |
struct Node { int vertex; struct Node *next; }; |
Ngoài ra, chúng ta cũng cần định nghĩa cấu trúc đồ thị: mảng của các danh sách liên kết với số lượng đỉnh cho trước:
|
1 2 3 4 5 |
struct Graph { int numVertices; // số đỉnh struct Node **lists; }; |
Chúng ta sử dụng con trỏ cấp 2 struct Node** lists là bởi vì nó là một mảng của các danh sách liên kết. Mà mỗi danh sách liên kết lại là một con trỏ kiểu Node.
Sau này, khi biết số lượng đỉnh thì chúng ta sẽ cấp phát bộ nhớ động cho nó đủ mức nó sử dụng.
# Các hàm khởi tạo
Chúng ta sẽ cần hàm khởi tạo Node cho danh sách liên kết để mỗi khi cần thêm Node vào danh sách liên kết thì ta có thể gọi tới và sử dụng:
- Cấp phát bộ nhớ cho Node
- Gán giá trị đỉnh cho Node đó
- Cho next của nó trỏ tới NULL, tránh nó trỏ lung tung (giá trị rác)
|
1 2 3 4 5 6 7 8 9 10 11 |
// Tạo mới 1 Node struct Node *createNode(int val) { // cấp phát bộ nhớ struct Node *newNode = malloc(sizeof(struct Node)); // gán mã đỉnh newNode->vertex = val; // cho next cho tới NULL newNode->next = NULL; return newNode; } |
Và đương nhiên không thể thiếu, chúng ta cần 1 hàm để khởi tạo cho đồ thị. Hàm này sẽ thực thi các việc sau:
- Cấp phát bộ nhớ cho đồ thị
- Cấp phát bộ nhớ cho mảng các danh sách liên kết của đồ thị
- Khởi tạo đỉnh ban đầu cho mỗi DSLK
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Tạo một đồ thị struct Graph *createAGraph(int vertices) { // Cấp phát bộ nhớ cho đồ thị struct Graph *graph = malloc(sizeof(struct Graph)); // Gán thông tin số đỉnh cho đồ thị graph->numVertices = vertices; // Cấp phát bộ nhớ cho mảng các danh sách liên kết dựa trên số lượng đỉnh graph->lists = malloc(vertices * sizeof(struct Node *)); // Hiện tại mảng các danh sách liên kết chưa có giá trị // Chúng ta sẽ gán cho các danh sách này tương ứng là node đỉnh của nó // Sau này, ta sẽ thêm các đỉnh có kết nối với nó vào sau Node đỉnh này int i; struct Node *temp; for (i = 0; i < vertices; i++) { temp = createNode(i); // i chính là đỉnh của DSLK graph->lists[i] = temp; } return graph; } |
# Tạo kết nối giữa 2 đỉnh
Nếu 2 đỉnh d và s có kết nối với nhau, ta sẽ thêm Node d vào danh sách liên kết có đỉnh là s và ngược lại.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Tạo kết nối giữa 2 đỉnh void addEdge(struct Graph *graph, int s, int d) { // Thêm kết nối từ s đến d // tạo node mới struct Node *newNode = createNode(d); // Node mới ta sẽ chèn vào đầu danh sách liên kết cho nhanh. // Vì chèn vào cuối phải duyệt tới cuối // Cho node mới làm head của DSLK, nên cần cho next của nó trỏ tới next mà head hiện tại đang trỏ newNode->next = graph->lists[s]->next; // Cập nhật head mới cho DSLK graph->lists[s]->next = newNode; // Kết thúc thêm kết nối từ s đến d // Thêm kết nối từ d đến s // Quá trình tương tự như trên newNode = createNode(s); newNode->next = graph->lists[d]->next; graph->lists[d]->next = newNode; } |
# Duyệt danh sách kề
Việc duyệt danh sách kề thực chất là việc lặp lại của thao tác duyệt danh sách liên kết đơn.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Duyệt danh sách kề void printGraph(struct Graph *graph) { int i; // Duyệt qua từng danh sách liên kết for (i = 0; i < graph->numVertices; i++) { // Tại mỗi danh sách liên kết, tạo con trỏ làm biến tạm để duyệt // Nếu dùng luôn head để duyệt sẽ mất dấu head của DSLK printf("Dinh %d co ket noi voi: ", graph->lists[i]->vertex); struct Node *temp = graph->lists[i]->next; // duyệt dslk cho tới khi null while (temp) { printf("%d ", temp->vertex); temp = temp->next; } printf("\n"); } } |
# Source code danh sách kề đầy đủ
Sau cùng, chúng ta sẽ bổ sung hàm main và thử thực thi chương trình. Dưới đây là toàn bộ source code cài đặt danh sách kề:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
#include <stdio.h> #include <stdlib.h> struct Node { int vertex; struct Node *next; }; struct Graph { int numVertices; // số đỉnh struct Node **lists; }; // Tạo mới 1 Node struct Node *createNode(int val) { // cấp phát bộ nhớ struct Node *newNode = malloc(sizeof(struct Node)); // gán mã đỉnh newNode->vertex = val; // cho next cho tới NULL newNode->next = NULL; return newNode; } // Tạo một đồ thị struct Graph *createAGraph(int vertices) { // Cấp phát bộ nhớ cho đồ thị struct Graph *graph = malloc(sizeof(struct Graph)); // Gán thông tin số đỉnh cho đồ thị graph->numVertices = vertices; // Cấp phát bộ nhớ cho mảng các danh sách liên kết dựa trên số lượng đỉnh graph->lists = malloc(vertices * sizeof(struct Node *)); // Hiện tại mảng các danh sách liên kết chưa có giá trị // Chúng ta sẽ gán cho các danh sách này tương ứng là node đỉnh của nó // Sau này, ta sẽ thêm các đỉnh có kết nối với nó vào sau Node đỉnh này int i; struct Node *temp; for (i = 0; i < vertices; i++) { temp = createNode(i); // i chính là đỉnh của DSLK graph->lists[i] = temp; } return graph; } // Tạo kết nối giữa 2 đỉnh void addEdge(struct Graph *graph, int s, int d) { // Thêm kết nối từ s đến d // tạo node mới struct Node *newNode = createNode(d); // Node mới ta sẽ chèn vào đầu danh sách liên kết cho nhanh. // Vì chèn vào cuối phải duyệt tới cuối // Cho node mới làm head của DSLK, nên cần cho next của nó trỏ tới next mà head hiện tại đang trỏ newNode->next = graph->lists[s]->next; // Cập nhật head mới cho DSLK graph->lists[s]->next = newNode; // Kết thúc thêm kết nối từ s đến d // Thêm kết nối từ d đến s // Quá trình tương tự như trên newNode = createNode(s); newNode->next = graph->lists[d]->next; graph->lists[d]->next = newNode; } // Duyệt danh sách kề void printGraph(struct Graph *graph) { int i; // Duyệt qua từng danh sách liên kết for (i = 0; i < graph->numVertices; i++) { // Tại mỗi danh sách liên kết, tạo con trỏ làm biến tạm để duyệt // Nếu dùng luôn head để duyệt sẽ mất dấu head của DSLK printf("Dinh %d co ket noi voi: ", graph->lists[i]->vertex); struct Node *temp = graph->lists[i]->next; // duyệt dslk cho tới khi null while (temp) { printf("%d ", temp->vertex); temp = temp->next; } printf("\n"); } } int main() { struct Graph *graph = createAGraph(4); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 0, 3); addEdge(graph, 1, 2); printGraph(graph); return 0; } |
Trong hàm main, mình sẽ biểu diễn 1 đồ thị 4 đỉnh và có các kết nối như hình vẽ ở ví dụ phía trên. Và đây là kết quả khi chạy trương chình (tên file code mình để là adj.c):
|
1 2 3 4 5 6 |
hieunv@ltkk:~/Documents/linkedlist$ gcc adj.c hieunv@ltkk:~/Documents/linkedlist$ ./a.out Dinh 0 co ket noi voi: 3 2 1 Dinh 1 co ket noi voi: 2 0 Dinh 2 co ket noi voi: 1 0 Dinh 3 co ket noi voi: 0 |
Biểu diễn danh sách sinh viên
Về bản chất, danh sách kề là cấu trúc dữ liệu để biểu diễn đồ thị vào bộ nhớ máy tính. Nên chính xác thì ta nên nói ứng dụng của đồ thị.
Ở mục này, mình chia sẻ thêm 1 source code sử dụng danh sách kề để biểu diễn mối quan hệ giữa các sinh viên theo lớp học: Các sinh viên cùng lớp sẽ có kết nối với nhau.
Các bạn có thể tham khảo học tập, mình xin phép không giải thích thêm.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 |
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct SinhVien { char MaSV[20]; char Ho[50]; char Ten[20]; char GioiTinh[5]; int NamSinh; char Nganh[100]; char Lop[20]; }SV; void NhapChuoi(char *s, int n){ char *p; fgets(s, n, stdin); if ((p = strchr(s, '\n')) != NULL) { *p = '\0'; } } SV Nhap1SV(){ SV sv; printf("Nhap Ma SV: "); NhapChuoi(sv.MaSV, 20); printf("Nhap ho SV: "); NhapChuoi(sv.Ho, 50); printf("Nhap ten SV: "); NhapChuoi(sv.Ten, 20); printf("Nhap gioi tinh: "); NhapChuoi(sv.GioiTinh, 5); printf("Nhap nam sinh: "); scanf("%d", &sv.NamSinh); getchar(); printf("Nhap nganh: "); NhapChuoi(sv.Nganh, 100); printf("Nhap lop: "); NhapChuoi(sv.Lop, 20); return sv; } void Xuat1SV(SV sv){ printf("Ma: %s\t", sv.MaSV); printf("Ho: %s\t", sv.Ho); printf("Ten: %s\t", sv.Ten); printf("GT: %s\t", sv.GioiTinh); printf("NS: %d\t", sv.NamSinh); printf("Nganh: %s\t", sv.Nganh); printf("Lop: %s\n", sv.Lop); } typedef struct Node { struct SinhVien data; struct Node *next; } Node; typedef struct DoThi { int soDinh; struct Node** dsPhanTu; } DoThi; // Tạo mới Node struct Node* TaoNode(SV sv) { struct Node* newNode = (struct Node*)malloc(sizeof(Node)); newNode->data = sv; newNode->next = NULL; return newNode; } // Create a graph DoThi* Tao1DoThi(int soDinh) { DoThi* doThi = (struct DoThi*) malloc(sizeof(DoThi)); doThi->soDinh = soDinh; doThi->dsPhanTu = (struct Node**)malloc(soDinh * sizeof(Node*)); int i; for (i = 0; i < soDinh; i++) doThi->dsPhanTu[i] = NULL; return doThi; } void ThemSinhVienVaoDoThi(DoThi *doThi){ int i; for (i = 0; i < doThi->soDinh; i++){ SV sv = Nhap1SV(); Node *node = TaoNode(sv); doThi->dsPhanTu[i] = node; printf("==================\n"); } } // Tạo kết nối cho 2 sinh viên ở chỉ số s và d void ThemCanh(DoThi *doThi, int s, int d){ // Thêm kết nối từ s tới d struct Node *newNode = TaoNode(doThi->dsPhanTu[d]->data); newNode->next = doThi->dsPhanTu[s]->next; doThi->dsPhanTu[s]->next = newNode; // Thêm kết nối từ d tới s newNode = TaoNode(doThi->dsPhanTu[s]->data); newNode->next = doThi->dsPhanTu[d]->next; doThi->dsPhanTu[d]->next = newNode; } int CungLop(SV a, SV b){ if (strcmp(a.Lop, b.Lop) == 0){ return 1; } return 0; } void TaoKetNoiTheoLop(DoThi *doThi){ // Duyệt từng sinh viên int i, j; for (i = 0; i < doThi->soDinh - 1; i++){ // Với mỗi sinh viên, duyệt các sinh viên phía sau nó, nếu học cùng lớp thì 2 sv đó có kết nối // Ta không duyệt sinh viên phía trước nó. Bởi vì: // Ví dụ ta duyệt được cặp (0, 1) thì ta cũng tạo luôn kết nối (1, 0) rồi. for (j = i+1; j < doThi->soDinh; j++){ if (CungLop(doThi->dsPhanTu[i]->data, doThi->dsPhanTu[j]->data)){ ThemCanh(doThi, i, j); } } } } void InDanhSachSV(DoThi *doThi){ int i; printf("%10s%20s%10s%10s%10s%50s%20s\n", "Ma SV", "Ho", "Ten", "Gioi tinh", "Nam sinh", "Nganh", "Lop"); for (i = 0; i < doThi->soDinh; i++){ SV sv = doThi->dsPhanTu[i]->data; printf("%10s%20s%10s%10s%10d%50s%20s\n", sv.MaSV, sv.Ho, sv.Ten, sv.GioiTinh, sv.NamSinh, sv.Nganh, sv.Lop); } } void DuyetDoThi(DoThi *doThi){ int i; for (i = 0; i < doThi->soDinh; i++){ Xuat1SV(doThi->dsPhanTu[i]->data); printf("=> DS cung lop (MaSV): "); struct Node *temp = doThi->dsPhanTu[i]; // bỏ qua sinh viên hiện thời temp = temp->next; while(temp){ printf("%s", temp->data.MaSV); temp = temp->next; if (temp) { printf(", "); } } printf("\n=======================\n"); } } int main(){ int soLuong; printf("Nhap so luong sinh vien: "); scanf("%d", &soLuong); DoThi *doThi = Tao1DoThi(soLuong); getchar(); ThemSinhVienVaoDoThi(doThi); TaoKetNoiTheoLop(doThi); printf("Danh sach SV hien co: \n"); InDanhSachSV(doThi); printf("Ket qua duyet danh sach ke: \n"); DuyetDoThi(doThi); } |
Kết quả thực thi:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
Nhap so luong sinh vien: 4 Nhap Ma SV: 1 Nhap ho SV: 1 Nhap ten SV: 1 Nhap gioi tinh: 1 Nhap nam sinh: 1 Nhap nganh: 1 Nhap lop: 1 ================== Nhap Ma SV: 2 Nhap ho SV: 2 Nhap ten SV: 2 Nhap gioi tinh: 2 Nhap nam sinh: 2 Nhap nganh: 2 Nhap lop: 2 ================== Nhap Ma SV: 3 Nhap ho SV: 3 Nhap ten SV: 3 Nhap gioi tinh: 3 Nhap nam sinh: 3 Nhap nganh: 3 Nhap lop: 2 ================== Nhap Ma SV: 4 Nhap ho SV: 4 Nhap ten SV: 4 Nhap gioi tinh: 4 Nhap nam sinh: 4 Nhap nganh: 4 Nhap lop: 1 ================== Danh sach SV hien co: Ma SV Ho Ten Gioi tinh Nam sinh Nganh Lop 1 1 1 1 1 1 1 2 2 2 2 2 2 2 3 3 3 3 3 3 2 4 4 4 4 4 4 1 Ket qua duyet danh sach ke: Ma: 1 Ho: 1 Ten: 1 GT: 1 NS: 1 Nganh: 1 Lop: 1 => DS cung lop (MaSV): 4 ======================= Ma: 2 Ho: 2 Ten: 2 GT: 2 NS: 2 Nganh: 2 Lop: 2 => DS cung lop (MaSV): 3 ======================= Ma: 3 Ho: 3 Ten: 3 GT: 3 NS: 3 Nganh: 3 Lop: 2 => DS cung lop (MaSV): 2 ======================= Ma: 4 Ho: 4 Ten: 4 GT: 4 NS: 4 Nganh: 4 Lop: 1 => DS cung lop (MaSV): 1 ======================= |
Bài viết tới đây là kết thúc, xin chào và hẹn gặp lại các bạn ở các bài hướng dẫn tiếp theo!
Theo dõi Lập Trình Không Khó để không bỏ lỡ các bài học bổ ích:
- Facebook: https://facebook.com/groups/LapTrinhKhongKho
- Youtube: https://youtube.com/LapTrinhKhongKho
