Biểu diễn đồ thị bằng ma trận kề và danh sách kề

<p style="text-align: justify;">Trong b&agrave;i viết n&agrave;y ta sẽ c&ugrave;ng t&igrave;m hiểu về c&aacute;ch biểu diễn đồ thị bằng ma trận kề v&agrave; danh s&aacute;ch kề c&ugrave;ng với c&aacute;c h&igrave;nh ảnh minh họa. Ngo&agrave;i ra, ta sẽ triển khai bằng ng&ocirc;n ngữ lập tr&igrave;nh C.</p> <h2 style="text-align: justify;">1. Kh&aacute;i niệm</h2> <p style="text-align: justify;">Ma trận kề l&agrave; c&aacute;ch biểu diễn đồ thị G = {V, E} dưới dạng ma trận c&aacute;c gi&aacute; trị boolean.</p> <p style="text-align: justify;">Biểu diễn ma trận kề: K&iacute;ch thước của ma trận l&agrave; VxV trong đ&oacute; V l&agrave; số đỉnh trong đồ thị v&agrave; gi&aacute; trị của một đầu v&agrave;o Aij l&agrave; 1 hoặc 0 t&ugrave;y thuộc v&agrave;o việc c&oacute; một cạnh từ đỉnh i đến đỉnh j hay kh&ocirc;ng.</p> <h3 style="text-align: justify;">V&iacute; dụ về ma trận kề</h3> <p style="text-align: justify;">H&igrave;nh ảnh dưới đ&acirc;y sẽ biểu diễn một đồ thị v&agrave; ma trận kề tương đương của n&oacute;.</p> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/91fa85e1-2967-4912-a439-6b99278b7f5a" alt="bieu-dien-do-thi-bang-ma-tran-ke-danh-sach-ke" /></p> <p style="text-align: justify;">Trong trường hợp đồ thị v&ocirc; hướng, ma trận sẽ đối xứng qua đường ch&eacute;o v&igrave; với mỗi cạnh (i, j) th&igrave; cũng sẽ c&oacute; một cạnh (j, i) tương ứng.</p> <p style="text-align: justify;"><strong>Ưu điểm của ma trận kề:</strong></p> <ul style="text-align: justify;"> <li>C&aacute;c ph&eacute;p to&aacute;n cơ bản như th&ecirc;m một cạnh, x&oacute;a một cạnh v&agrave; kiểm tra xem c&oacute; cạnh n&agrave;o từ đỉnh i đến đỉnh j hay kh&ocirc;ng l&agrave; c&aacute;c thao t&aacute;c hiệu quả về mặt thời gian v&agrave; thời gian l&agrave; kh&ocirc;ng đổi.</li> <li>Nếu đồ thị d&agrave;y đặc v&agrave; số lượng cạnh lớn, ma trận kề sẽ l&agrave; lựa chọn đầu ti&ecirc;n. Ngay cả khi đồ thị v&agrave; ma trận kề l&agrave; thưa, ch&uacute;ng ta c&oacute; thể biểu diễn n&oacute; bằng c&aacute;ch sử dụng cấu tr&uacute;c dữ liệu cho ma trận thưa.</li> <li>Tuy nhi&ecirc;n, lợi thế lớn nhất đến từ việc sử dụng ma trận. Những tiến bộ gần đ&acirc;y trong phần cứng cho ph&eacute;p ch&uacute;ng ta thực hiện c&aacute;c ph&eacute;p to&aacute;n với ma trận lớn tr&ecirc;n GPU.</li> <li>Bằng c&aacute;ch thực hiện c&aacute;c thao t&aacute;c tr&ecirc;n ma trận kề, ch&uacute;ng ta c&oacute; thể c&oacute; được những hiểu biết quan trọng về bản chất của đồ thị v&agrave; mối quan hệ giữa c&aacute;c đỉnh của n&oacute;.</li> </ul> <p style="text-align: justify;"><strong>Nhược điểm của ma trận kề:</strong></p> <p style="text-align: justify;">Y&ecirc;u cầu về kh&ocirc;ng gian VxV của ma trận kề l&agrave;m cho n&oacute; trở th&agrave;nh một đối tượng ti&ecirc;u thụ lượng bộ nhớ lớn. C&aacute;c đồ thị thường sẽ kh&ocirc;ng c&oacute; qu&aacute; nhiều li&ecirc;n kết v&agrave; đ&acirc;y l&agrave; l&yacute; do ch&iacute;nh tại sao danh s&aacute;ch kề l&agrave; lựa chọn tốt hơn cho hầu hết c&aacute;c nhiệm vụ.</p> <p style="text-align: justify;">Trong khi c&aacute;c thao t&aacute;c cơ bản được thực hiện dễ d&agrave;ng, nhưng c&aacute;c thao t&aacute;c như <span class="lang:default decode:true crayon-inline ">inEdges</span> v&agrave; <span class="lang:default decode:true crayon-inline ">outEdges</span>&nbsp;sẽ rất tốn k&eacute;m khi sử dụng biểu diễn ma trận kề.</p> <p style="text-align: justify;">V&iacute; dụ:</p> <pre class="language-cpp"><code>#include &lt;stdio.h&gt; #define V 6 void init(int arr[][V]) { for (int i = 0; i &lt; V; i++) for (int j = 0; j &lt; V; j++) arr[i][j] = 0; } void add_edge(int arr[][V], int i, int j) { arr[i][j] = 1; arr[j][i] = 1; } void print(int arr[][V]) { for (int i = 0; i &lt; V; i++) { printf("%d: ", i); for (int j = 0; j &lt; V; j++) { printf("%d ", arr[i][j]); } printf("\n"); } } int main() { int matrix[V][V]; init(matrix); add_edge(matrix, 2, 3); add_edge(matrix, 2, 4); add_edge(matrix, 3, 4); add_edge(matrix, 4, 2); add_edge(matrix, 4, 5); print(matrix); return 0; }</code></pre> <p style="text-align: justify;">Kết quả:</p> <pre class="language-markup"><code>0: 0 0 0 0 0 0 1: 0 0 0 0 0 0 2: 0 0 0 1 1 0 3: 0 0 1 0 1 0 4: 0 0 1 1 0 1 5: 0 0 0 0 1 0</code></pre> <p style="text-align: justify;"><strong>Ứng dụng của ma trận gần kề:</strong></p> <ul style="text-align: justify;"> <li>Tạo bảng định tuyến trong mạng.</li> <li>C&aacute;c b&agrave;i to&aacute;n về t&igrave;m hướng đi hoặc định vị.</li> </ul> <h2 style="text-align: justify;">2. Danh s&aacute;ch kề</h2> <p style="text-align: justify;">Danh s&aacute;ch kề biểu thị một biểu đồ dưới dạng một mảng c&aacute;c danh s&aacute;ch được li&ecirc;n kết. Chỉ số của mảng đại diện cho một đỉnh v&agrave; mỗi phần tử trong danh s&aacute;ch li&ecirc;n kết của n&oacute; đại diện cho c&aacute;c đỉnh kh&aacute;c tạo th&agrave;nh một cạnh với đỉnh đ&oacute;.</p> <p style="text-align: justify;">Biểu đồ v&agrave; biểu diễn danh s&aacute;ch kề tương đương của n&oacute; được biểu diễn trong h&igrave;nh b&ecirc;n dưới.</p> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/3887c694-15dc-4378-a15c-d875ff6d82ec" alt="bieu-dien-do-thi-bang-ma-tran-ke-danh-sach-ke-2" /></p> <p style="text-align: justify;">Danh s&aacute;ch kề c&oacute; hiệu quả về mặt lưu trữ v&igrave; ch&uacute;ng ta chỉ cần lưu trữ c&aacute;c gi&aacute; trị cho c&aacute;c cạnh. Đối với một đồ thị thưa c&oacute; h&agrave;ng triệu đỉnh v&agrave; cạnh, điều n&agrave;y c&oacute; nghĩa l&agrave; rất nhiều kh&ocirc;ng gian sẽ được tiết kiệm.</p> <p style="text-align: justify;"><strong>Cấu tr&uacute;c của danh s&aacute;ch kề:</strong></p> <p style="text-align: justify;">Danh s&aacute;ch kề đơn giản nhất cần c&oacute; cấu tr&uacute;c dữ liệu n&uacute;t để lưu một đỉnh v&agrave; cấu tr&uacute;c dữ liệu đồ thị để tổ chức c&aacute;c n&uacute;t.</p> <p style="text-align: justify;">Ch&uacute;ng ta sẽ c&ugrave;ng tiếp cận với định nghĩa cơ bản của đồ thị - tập hợp c&aacute;c đỉnh v&agrave; cạnh {V, E}. Để đơn giản, ch&uacute;ng ta sẽ sử dụng một đồ thị kh&ocirc;ng c&oacute; nh&atilde;n thay v&igrave; một đồ thị c&oacute; nh&atilde;n, tức l&agrave; c&aacute;c đỉnh được x&aacute;c định bởi c&aacute;c chỉ số 0,1,2,3 của ch&uacute;ng.</p> <p style="text-align: justify;">Ta sẽ c&ugrave;ng t&igrave;m hiểu c&aacute;c cấu tr&uacute;c tại đ&acirc;y.</p> <pre class="language-cpp"><code>struct node { int vertex; struct node* next; }; struct Graph { int numVertices; struct node** adjLists; };</code></pre> <p style="text-align: justify;">Điều ch&uacute;ng ta muốn l&agrave; lưu trữ một con trỏ tới struct node*. Điều n&agrave;y l&agrave; do ch&uacute;ng ta kh&ocirc;ng biết đồ thị sẽ c&oacute; bao nhi&ecirc;u đỉnh v&agrave; v&igrave; vậy ch&uacute;ng ta kh&ocirc;ng thể tạo một mảng danh s&aacute;ch li&ecirc;n kết tại thời điểm bi&ecirc;n dịch.</p> <h3 style="text-align: justify;">Danh s&aacute;ch kề bằng ng&ocirc;n ngữ C++</h3> <p style="text-align: justify;">N&oacute; l&agrave; c&ugrave;ng một cấu tr&uacute;c nhưng bằng c&aacute;ch sử dụng cấu tr&uacute;c dữ liệu STL danh s&aacute;ch c&oacute; sẵn của C ++, ch&uacute;ng ta l&agrave;m cho cấu tr&uacute;c tr&ocirc;ng trở n&ecirc;n gọn hơn. Ch&uacute;ng ta cũng c&oacute; thể t&oacute;m tắt c&aacute;c chi tiết của việc thực hiện.</p> <pre class="language-cpp"><code>class Graph { int numVertices; list&lt;int&gt; *adjLists; public: Graph(int V); void addEdge(int src, int dest); };</code></pre> <p style="text-align: justify;">V&iacute; dụ: Triển khai danh s&aacute;ch kề bằng ng&ocirc;n ngữ lập tr&igrave;nh C.</p> <pre class="language-c"><code>#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; struct node { int vertex; struct node* next; }; struct node* create_node(int); struct Graph { int numVertices; struct node** adjLists; }; struct node* create_node(int v) { struct node* new_node = malloc(sizeof(struct node)); new_node-&gt;vertex = v; new_node-&gt;next = NULL; return new_node; } struct Graph* create_graph(int vertices) { struct Graph* graph = malloc(sizeof(struct Graph)); graph-&gt;numVertices = vertices; graph-&gt;adjLists = malloc(vertices * sizeof(struct node*)); for(int i = 0; i &lt; vertices; i++) graph-&gt;adjLists[i] = NULL; return graph; } void add_edge(struct Graph* graph, int s, int d) { struct node* new_node = create_node(d); new_node-&gt;next = graph-&gt;adjLists[s]; graph-&gt;adjLists[s] = new_node; new_node = create_node(s); new_node-&gt;next = graph-&gt;adjLists[d]; graph-&gt;adjLists[d] = new_node; } void print(struct Graph* graph) { for (int v = 2; v &lt; graph-&gt;numVertices; v++) { struct node* temp = graph-&gt;adjLists[v]; printf("\nĐỉnh %d\n: ", v); while (temp) { printf("%d -&gt; ", temp-&gt;vertex); temp = temp-&gt;next; } printf("\n"); } } int main() { struct Graph* graph = create_graph(6); add_edge(graph, 2, 3); add_edge(graph, 2, 4); add_edge(graph, 2, 5); add_edge(graph, 3, 4); print(graph); return 0; }</code></pre> <p style="text-align: justify;">Kết quả:</p> <pre class="language-markup"><code>Đỉnh 2 : 5 -&gt; 4 -&gt; 3 -&gt; Đỉnh 3 : 4 -&gt; 2 -&gt; Đỉnh 4 : 3 -&gt; 2 -&gt; Đỉnh 5 : 2 -&gt;</code></pre> <p style="text-align: justify;">Tr&ecirc;n đ&acirc;y l&agrave; kh&aacute;i niệm v&agrave; v&iacute; dụ cơ bản về ma trận kề v&agrave; danh s&aacute;ch kề. Hy vọng mọi người c&oacute; thể &aacute;p dụng v&agrave;o trong chương tr&igrave;nh của m&igrave;nh. Nếu mọi người c&oacute; đ&oacute;ng g&oacute;p g&igrave; th&ecirc;m th&igrave; c&oacute; thể để c&aacute;c b&igrave;nh luận b&ecirc;n dưới b&agrave;i viết n&agrave;y. Mọi người h&atilde;y tiếp tục theo d&otilde;i c&aacute;c b&agrave;i tiếp theo v&agrave; cập nhật c&aacute;c b&agrave;i mới nhất tr&ecirc;n <a href="http://tek4.vn">tek4</a> nh&eacute;!</p>