Cấu trúc dữ liệu đồ thị (Graph) và ứng dụng

<p style="text-align: justify;">Trong hướng dẫn n&agrave;y, ta sẽ c&ugrave;ng t&igrave;m hiểu về cấu tr&uacute;c dữ liệu đồ thị c&ugrave;ng c&aacute;c h&igrave;nh ảnh minh họa. Ta sẽ c&ugrave;ng đi qua kh&aacute;i qu&aacute;t về kiểu cấu tr&uacute;c n&agrave;y v&agrave; t&igrave;m hiểu về ứng dụng của n&oacute;.</p> <h2 id="ftoc-heading-1" class="ftwp-heading" style="text-align: justify;">1. Kh&aacute;i niệm</h2> <p style="text-align: justify;">Cấu tr&uacute;c dữ liệu đồ thị l&agrave; một tập hợp c&aacute;c n&uacute;t c&oacute; dữ liệu v&agrave; được kết nối với c&aacute;c n&uacute;t kh&aacute;c. Ta sẽ hiểu điều n&agrave;y th&ocirc;ng qua một v&iacute; dụ. Tr&ecirc;n một trang mạng x&atilde; hội A, mọi thứ đều l&agrave; một n&uacute;t. Bao gồm người d&ugrave;ng, ảnh, album, sự kiện, nh&oacute;m, trang, b&igrave;nh luận, c&acirc;u chuyện, video&hellip; bất cứ thứ g&igrave; c&oacute; dữ liệu l&agrave; một n&uacute;t. Mọi mối quan hệ l&agrave; một cạnh từ n&uacute;t n&agrave;y sang n&uacute;t kh&aacute;c. Cho d&ugrave; bạn đăng ảnh, tham gia nh&oacute;m, th&iacute;ch một trang,&hellip;, một cạnh mới sẽ được tạo ra cho mối quan hệ đ&oacute;.</p> <p><img style="width: 100%;" src="../../../public_files/00628c0e-b774-4e38-af5d-c077c6f4c88b" alt="cau-truc-du-lieu-do-thi" /></p> <p style="text-align: justify;">Tất cả của mạng x&atilde; hội n&agrave;y sau đ&oacute; l&agrave; một tập hợp c&aacute;c n&uacute;t v&agrave; c&aacute;c cạnh. Điều n&agrave;y l&agrave; do A sử dụng cấu tr&uacute;c dữ liệu đồ thị để lưu trữ dữ liệu của n&oacute;.</p> <p style="text-align: justify;">Ch&iacute;nh x&aacute;c hơn, đồ thị l&agrave; một cấu tr&uacute;c dữ liệu (V, E) bao gồm:</p> <ul> <li style="text-align: justify;">Tập hợp c&aacute;c đỉnh V.</li> <li style="text-align: justify;">Tập hợp c&aacute;c cạnh E, được biểu diễn dưới dạng c&aacute;c cặp đỉnh c&oacute; thứ tự (u, v).</li> </ul> <p><img style="width: 100%;" src="../../../public_files/2dd17e0f-e455-44ca-b209-425b3ffb82d7" alt="cau-truc-du-lieu-do-thi-2" /></p> <p style="text-align: justify;">Trong đồ thị tr&ecirc;n, ta c&oacute;:</p> <ul style="text-align: justify;"> <li>V = {0, 1, 2, 3}</li> <li>E = {(2,1), (2,0), (2,3), (1,0)}</li> <li>G = {V, E}</li> </ul> <h2 id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;">2. Thuật ngữ trong cấu tr&uacute;c dữ liệu đồ thị</h2> <ul style="text-align: justify;"> <li>Đỉnh kề: Một đỉnh được cho l&agrave; kề với một đỉnh kh&aacute;c nếu c&oacute; một cạnh nối giữa ch&uacute;ng. C&aacute;c đỉnh 0 v&agrave; 3 kh&ocirc;ng liền nhau v&igrave; kh&ocirc;ng c&oacute; cạnh giữa ch&uacute;ng.</li> <li>Đường dẫn: Một d&atilde;y c&aacute;c cạnh cho ph&eacute;p ta đi từ đỉnh A đến đỉnh B được gọi l&agrave; đường dẫn. 0-1, 1-2 v&agrave; 0-2 l&agrave; c&aacute;c đường đi từ đỉnh 0 đến đỉnh 2.</li> <li>Đồ thị c&oacute; hướng: Một đồ thị trong đ&oacute; cạnh (u, v) kh&ocirc;ng nhất thiết c&oacute; nghĩa l&agrave; cũng c&oacute; cạnh (v, u). C&aacute;c cạnh trong biểu đồ như vậy được biểu diễn bằng c&aacute;c mũi t&ecirc;n để chỉ hướng của cạnh.</li> </ul> <h2 id="ftoc-heading-3" class="ftwp-heading" style="text-align: justify;">3. Biểu diễn đồ thị</h2> <p style="text-align: justify;">Đồ thị thường được biểu diễn theo hai c&aacute;ch:</p> <h3 id="ftoc-heading-4" class="ftwp-heading" style="text-align: justify;">3.1. Ma trận liền kề hay ma trận kề</h3> <p style="text-align: justify;">Ma trận kề l&agrave; một mảng 2 chiều gồm c&aacute;c đỉnh VxV. Mỗi h&agrave;ng v&agrave; cột đại diện cho một đỉnh.</p> <p style="text-align: justify;">Nếu gi&aacute; trị của bất kỳ phần tử n&agrave;o&nbsp;<span id="urvanov-syntax-highlighter-610758676e1e9453956391" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">a</span><span class="crayon-sy">[</span><span class="crayon-v">i</span><span class="crayon-sy">]</span><span class="crayon-sy">[</span><span class="crayon-v">j</span><span class="crayon-sy">]</span></span></span>&nbsp;l&agrave; 1, n&oacute; biểu thị rằng c&oacute; một cạnh nối đỉnh i v&agrave; đỉnh j.</p> <p style="text-align: justify;">Ma trận kề cho biểu đồ ch&uacute;ng ta đ&atilde; tạo ở tr&ecirc;n như sau.</p> <p><img style="width: 100%;" src="../../../public_files/fbb4fe7a-d822-4170-ac61-8d401a80b388" alt="cau-truc-du-lieu-do-thi-3" /></p> <p>V&igrave; l&agrave; đồ thị v&ocirc; hướng n&ecirc;n đối với cạnh (0,2), ch&uacute;ng ta cũng cần đ&aacute;nh dấu cạnh (2,0), l&agrave;m cho ma trận kề đối xứng qua đường ch&eacute;o.</p> <p>Việc t&igrave;m kiếm cạnh (kiểm tra xem c&oacute; tồn tại cạnh nối giữa đỉnh A v&agrave; đỉnh B hay kh&ocirc;ng) cực kỳ nhanh ch&oacute;ng trong biểu diễn ma trận kề nhưng ch&uacute;ng ta phải d&agrave;nh kh&ocirc;ng gian cho mọi li&ecirc;n kết c&oacute; thể c&oacute; giữa tất cả c&aacute;c đỉnh (VxV), v&igrave; vậy n&oacute; đ&ograve;i hỏi nhiều kh&ocirc;ng gian hơn.</p> <h3 id="ftoc-heading-5" class="ftwp-heading">3.2. Danh s&aacute;ch kề</h3> <p>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.</p> <p>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.</p> <p>Danh s&aacute;ch kề cho biểu đồ m&agrave; ch&uacute;ng ta đ&atilde; tạo trong v&iacute; dụ đầu ti&ecirc;n như sau:</p> <p><img style="width: 100%;" src="../../../public_files/7d5843e5-6373-49d0-b011-26ac04559563" alt="cau-truc-du-lieu-do-thi-4" /></p> <p style="text-align: justify;">Danh s&aacute;ch kề c&oacute; t&iacute;nh 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 biểu đồ c&oacute; h&agrave;ng triệu đỉnh, điều n&agrave;y c&oacute; nghĩa l&agrave; rất nhiều kh&ocirc;ng gian được tiết kiệm.</p> <h2 id="ftoc-heading-6" class="ftwp-heading" style="text-align: justify;">4. C&aacute;c thao t&aacute;c l&agrave;m việc với cấu tr&uacute;c kiểu dữ liệu đồ thị</h2> <p style="text-align: justify;">C&aacute;c thao t&aacute;c thường được sử dụng với kiểu đồ thị phổ biến nhất bao gồm như sau:</p> <ul style="text-align: justify;"> <li>Kiểm tra xem phần tử c&oacute; trong đồ thị hay kh&ocirc;ng.</li> <li>Duyệt qua đồ thị.</li> <li>Th&ecirc;m c&aacute;c phần tử (đỉnh, cạnh) v&agrave;o đồ thị.</li> <li>T&igrave;m đường đi từ đỉnh n&agrave;y sang đỉnh kh&aacute;c.</li> </ul> <h2 id="ftoc-heading-7" class="ftwp-heading" style="text-align: justify;">5. Ứng dụng của đồ thị</h2> <ul style="text-align: justify;"> <li>Trong khoa học m&aacute;y t&iacute;nh, đồ thị được sử dụng để biểu diễn luồng t&iacute;nh to&aacute;n.</li> <li>Bản đồ của Google sử dụng đồ thị để x&acirc;y dựng hệ thống giao th&ocirc;ng, trong đ&oacute; giao điểm của hai (hoặc nhiều) đường được coi l&agrave; một đỉnh v&agrave; đường nối hai đỉnh được coi l&agrave; một cạnh, do đ&oacute; hệ thống điều hướng của ch&uacute;ng dựa tr&ecirc;n thuật to&aacute;n để t&iacute;nh to&aacute;n ngắn nhất đường đi giữa hai đỉnh.</li> <li>Trong mạng x&atilde; hội Facebook, người d&ugrave;ng được coi l&agrave; đỉnh v&agrave; nếu họ l&agrave; bạn b&egrave; th&igrave; sẽ c&oacute; một cạnh chạy giữa họ. Thuật to&aacute;n đề xuất bạn b&egrave; của Facebook sử dụng l&yacute; thuyết đồ thị. Facebook l&agrave; một v&iacute; dụ về đồ thị v&ocirc; hướng.</li> <li>C&aacute;c trang Web được coi l&agrave; c&aacute;c đỉnh. C&oacute; một cạnh từ trang u sang trang kh&aacute;c v nếu c&oacute; một li&ecirc;n kết của trang v tr&ecirc;n trang u. Đ&acirc;y l&agrave; một v&iacute; dụ về đồ thị c&oacute; hướng. Đ&oacute; l&agrave; &yacute; tưởng cơ bản đằng sau thuật to&aacute;n xếp hạng trang của Google.</li> <li>Trong hệ điều h&agrave;nh, ch&uacute;ng ta bắt gặp đồ thị ph&acirc;n bổ t&agrave;i nguy&ecirc;n, m&agrave; trong đ&oacute;, mỗi tiến tr&igrave;nh v&agrave; t&agrave;i nguy&ecirc;n được coi l&agrave; c&aacute;c đỉnh. C&aacute;c cạnh được r&uacute;t ra từ c&aacute;c t&agrave;i nguy&ecirc;n tới tiến tr&igrave;nh được cấp ph&aacute;t hoặc từ tiến tr&igrave;nh y&ecirc;u cầu đến t&agrave;i nguy&ecirc;n được y&ecirc;u cầu. Nếu điều n&agrave;y dẫn đến sự h&igrave;nh th&agrave;nh của một chu tr&igrave;nh th&igrave; sẽ xảy ra bế tắc.</li> </ul> <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ề cấu tr&uacute;c dữ liệu đồ thị. 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&nbsp;<a href="../../../">tek4</a>&nbsp;nh&eacute;!</p>