Thuật toán Tarjan trong tìm thành phần liên thông mạnh

<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ề thuật to&aacute;n Tarjan để t&igrave;m ra c&aacute;c th&agrave;nh phần li&ecirc;n th&ocirc;ng mạnh c&ugrave;ng với c&aacute;c h&igrave;nh ảnh minh họa.</p> <h2 id="ftoc-heading-1" class="ftwp-heading" style="text-align: justify;">Kh&aacute;i niệm</h2> <p style="text-align: justify;">Một đồ thị c&oacute; hướng được li&ecirc;n th&ocirc;ng mạnh nếu c&oacute; một đường đi giữa tất cả c&aacute;c cặp đỉnh. Th&agrave;nh phần li&ecirc;n th&ocirc;ng mạnh (SCC &ndash; Strongly Connected Component) của đồ thị c&oacute; hướng l&agrave; đồ thị con được li&ecirc;n th&ocirc;ng mạnh cực đại. V&iacute; dụ, c&oacute; 3 SCC trong đồ thị sau.</p> <p><img style="width: 100%;" src="../../../public_files/8452a6ed-83e0-4cd7-9864-446797b0e642" alt="thuat-toan-tarjan" /></p> <p style="text-align: justify;">Thuật to&aacute;n của Tarjan chỉ y&ecirc;u cầu một lần duyệt dựa theo thuật to&aacute;n DFS, l&agrave; một thuật to&aacute;n t&igrave;m kiếm theo chiều s&acirc;u tr&ecirc;n đồ thị.</p> <p style="text-align: justify;">Thuật to&aacute;n của Tarjan được thực thi trong thời gian tuyến t&iacute;nh l&agrave; một thuật to&aacute;n trong l&yacute; thuyết đồ thị để t&igrave;m c&aacute;c th&agrave;nh phần được kết nối chặt chẽ hay li&ecirc;n th&ocirc;ng mạnh của một đồ thị c&oacute; hướng.</p> <h3 id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;">Cầu nối (Bridge)</h3> <p style="text-align: justify;">Cầu nối (hoặc cạnh) hay Bridge trong l&yacute; thuyết đồ thị l&agrave; bất kỳ cạnh n&agrave;o trong biểu đồ m&agrave; việc loại bỏ n&oacute; sẽ l&agrave;m tăng số lượng c&aacute;c th&agrave;nh phần được kết nối.</p> <p><img style="width: 100%;" src="../../../public_files/ee9b2289-c7b8-4a70-bf96-8c6f51a78077" alt="thuat-toan-tarjan-2" /></p> <p style="text-align: justify;">C&aacute;c đường c&oacute; m&agrave;u đỏ được gọi l&agrave; cầu nối v&igrave; nếu ta loại bỏ bất kỳ đường n&agrave;o trong số ch&uacute;ng, biểu đồ được chia th&agrave;nh hai th&agrave;nh phần.</p> <h3 id="ftoc-heading-3" class="ftwp-heading" style="text-align: justify;">Điểm li&ecirc;n kết (Articulation Point)</h3> <p style="text-align: justify;">Điểm li&ecirc;n kết l&agrave; bất kỳ n&uacute;t n&agrave;o trong biểu đồ m&agrave; việc loại bỏ n&oacute; sẽ l&agrave;m tăng số lượng c&aacute;c th&agrave;nh phần được kết nối.</p> <p><img style="width: 100%;" src="../../../public_files/34391a52-b373-4494-afde-8d3414d501f6" alt="thuat-toan-tarjan-3" /></p> <p style="text-align: justify;">C&aacute;c n&uacute;t được đ&aacute;nh dấu m&agrave;u cam l&agrave; c&aacute;c điểm li&ecirc;n kết v&igrave; nếu ta loại bỏ bất kỳ n&uacute;t n&agrave;o trong số ch&uacute;ng, biểu đồ sẽ được chia th&agrave;nh hai th&agrave;nh phần.</p> <p style="text-align: justify;">Thuật to&aacute;n Tarjan dựa tr&ecirc;n c&aacute;c dữ kiện sau:</p> <ol style="text-align: justify;"> <li>T&igrave;m kiếm DFS tạo ra một c&acirc;y hoặc rừng DFS.</li> <li>C&aacute;c th&agrave;nh phần được li&ecirc;n th&ocirc;ng mạnh tạo th&agrave;nh c&aacute;c c&acirc;y con của c&acirc;y DFS.</li> <li>Nếu ch&uacute;ng ta c&oacute; thể t&igrave;m thấy đầu của c&aacute;c c&acirc;y con như vậy, ch&uacute;ng ta c&oacute; thể in ra hoặc lưu trữ tất cả c&aacute;c n&uacute;t trong c&acirc;y con đ&oacute; (bao gồm cả đầu) v&agrave; đ&oacute; sẽ l&agrave; một SCC.</li> <li>Kh&ocirc;ng c&oacute; cạnh n&agrave;o quay trở lại từ SCC n&agrave;y sang SCC kh&aacute;c (C&oacute; thể c&oacute; c&aacute;c cạnh ch&eacute;o, nhưng c&aacute;c cạnh ch&eacute;o sẽ kh&ocirc;ng được sử dụng trong khi xử l&yacute; đồ thị).</li> </ol> <p style="text-align: justify;">Thuật to&aacute;n Tarjan cung cấp một c&aacute;ch hiệu quả để t&igrave;m c&aacute;c cầu nối v&agrave; c&aacute;c điểm li&ecirc;n kết n&agrave;y trong thời gian tuyến t&iacute;nh. Ch&uacute;ng ta c&oacute; thể giải th&iacute;ch thuật to&aacute;n n&agrave;y theo 3 bước như sau:</p> <ul> <li style="text-align: justify;">Bước 1: Bắt đầu ở bất kỳ n&uacute;t n&agrave;o v&agrave; thực hiện duyệt t&igrave;m kiếm theo chiều s&acirc;u (DFS), gắn nh&atilde;n c&aacute;c n&uacute;t với gi&aacute; trị id tăng dần khi ta thực hiện.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/26d980f1-2327-458e-b6c8-c0240970a7b8" alt="thuat-toan-tarjan-4" /></p> <ul> <li style="text-align: justify;">Bước 2: Theo d&otilde;i id của từng n&uacute;t v&agrave; gi&aacute; trị li&ecirc;n kết thấp nhỏ nhất.</li> </ul> <p style="text-align: justify;">Li&ecirc;n kết thấp l&agrave; g&igrave;? Gi&aacute; trị li&ecirc;n kết thấp của một n&uacute;t được định nghĩa l&agrave; id nhỏ nhất c&oacute; thể truy cập được từ n&uacute;t đ&oacute; khi thực hiện t&igrave;m kiếm đầu ti&ecirc;n theo chiều s&acirc;u (DFS), bao gồm cả ch&iacute;nh n&oacute;. Ban đầu, tất cả c&aacute;c gi&aacute; trị li&ecirc;n kết thấp c&oacute; thể được khởi tạo cho id của mỗi n&uacute;t.</p> <p><img style="width: 100%;" src="../../../public_files/05650bd6-8eac-486b-a709-a182749915aa" alt="thuat-toan-tarjan-5" /></p> <p style="text-align: justify;">Nếu ch&uacute;ng ta kiểm tra n&uacute;t 1 v&agrave; n&uacute;t 2, ch&uacute;ng ta sẽ nhận thấy rằng tồn tại một con đường đi từ n&uacute;t 1 v&agrave; n&uacute;t 2 đến n&uacute;t 0. V&igrave; vậy, ch&uacute;ng ta n&ecirc;n cập nhật cả gi&aacute; trị li&ecirc;n kết thấp của n&uacute;t 1 v&agrave; n&uacute;t 2 th&agrave;nh gi&aacute; trị 0.</p> <p><img style="width: 100%;" src="../../../public_files/b15a2d6a-94ad-4f00-9fce-faeb3a75087d" alt="thuat-toan-tarjan-6" /></p> <p>Tuy nhi&ecirc;n, n&uacute;t 3, n&uacute;t 4 v&agrave; n&uacute;t 5 đ&atilde; c&oacute; gi&aacute; trị li&ecirc;n kết thấp tối ưu v&igrave; kh&ocirc;ng c&oacute; n&uacute;t n&agrave;o kh&aacute;c m&agrave; ch&uacute;ng c&oacute; thể tiếp cận với gi&aacute; trị id nhỏ hơn.</p> <p><img style="width: 100%;" src="../../../public_files/0db5a261-fe5d-4114-8b0d-60f796cfa108" alt="thuat-toan-tarjan-7" /></p> <p style="text-align: justify;">Đối với n&uacute;t 6, n&uacute;t 7 v&agrave; n&uacute;t 8, c&oacute; một đường đi từ n&uacute;t 6, n&uacute;t 7 v&agrave; n&uacute;t 8 đến n&uacute;t 5. V&igrave; vậy, ta sẽ cập nhật c&aacute;c gi&aacute; trị li&ecirc;n kết thấp của n&uacute;t 6, n&uacute;t 7 v&agrave; n&uacute;t 8 th&agrave;nh gi&aacute; trị 5.</p> <p><img style="width: 100%;" src="../../../public_files/5d285004-6881-4316-ae4e-7da8ec7a7ff4" alt="thuat-toan-tarjan-8" /></p> <ul> <li style="text-align: justify;">Bước 3: Trong T&igrave;m kiếm đầu ti&ecirc;n theo chiều s&acirc;u (DFS), c&aacute;c cầu nối sẽ được t&igrave;m thấy m&agrave; trong đ&oacute; id của n&uacute;t m&agrave; cạnh của ta bắt đầu từ n&oacute; nhỏ hơn gi&aacute; trị li&ecirc;n kết thấp của n&uacute;t m&agrave; cạnh của ta sẽ đến.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/af89ea6e-a759-4d43-b31c-15748354c0ec" alt="thuat-toan-tarjan-9" /></p> <p style="text-align: justify;">V&iacute; dụ: Để t&igrave;m đầu của một SCC, ch&uacute;ng ta t&iacute;nh to&aacute;n mảng Low v&agrave; Disc (như được thực hiện đối với điểm khớp nối, cầu nối, th&agrave;nh phần li&ecirc;n th&ocirc;ng hai chiều). low[u] chỉ ra đỉnh được truy cập sớm nhất (đỉnh c&oacute; thời gian t&igrave;m ra tối thiểu) c&oacute; thể đạt được từ c&acirc;y con bắt nguồn từ u. Một n&uacute;t u sẽ nằm ở đầu nếu disc[u] = low[u].</p> <ul> <li style="text-align: justify;">Giả sử ban đầu ta c&oacute; như sau:</li> </ul> <p><img style="width: 100%;" src="../../../public_files/9a1c96f4-b427-400e-b894-c58b90486e26" alt="thuat-toan-tarjan-10" /></p> <ul> <li>Duyệt DFS:</li> </ul> <p><img style="width: 100%;" src="../../../public_files/19a0084f-e699-468a-8cfc-1da530460842" alt="thuat-toan-tarjan-11" /></p> <p style="text-align: justify;">Th&agrave;nh phần li&ecirc;n th&ocirc;ng mạnh chỉ li&ecirc;n quan đến đồ thị c&oacute; hướng, nhưng c&aacute;c gi&aacute; trị Disc v&agrave; gi&aacute; trị Low li&ecirc;n quan đến cả đồ thị c&oacute; hướng v&agrave; v&ocirc; hướng, trong h&igrave;nh tr&ecirc;n, ch&uacute;ng ta đ&atilde; sử dụng đồ thị c&oacute; hướng.</p> <p style="text-align: justify;">Trong h&igrave;nh tr&ecirc;n, ch&uacute;ng ta đ&atilde; chỉ ra một đồ thị v&agrave; một trong những c&acirc;y DFS của n&oacute; (C&oacute; thể c&oacute; nhiều c&acirc;y DFS kh&aacute;c nhau tr&ecirc;n c&ugrave;ng một đồ thị t&ugrave;y thuộc v&agrave;o thứ tự m&agrave; c&aacute;c cạnh được duyệt qua). Trong c&acirc;y DFS, c&aacute;c mũi t&ecirc;n li&ecirc;n tục l&agrave; c&aacute;c cạnh của c&acirc;y v&agrave; c&aacute;c mũi t&ecirc;n đứt n&eacute;t l&agrave; c&aacute;c cạnh sau (DFS Tree Edges). C&aacute;c gi&aacute; trị Disc v&agrave; Low được hiển thị trong h&igrave;nh cho mỗi n&uacute;t l&agrave; (Disc v&agrave; Low).</p> <p style="text-align: justify;">Disc: Đ&acirc;y l&agrave; thời điểm khi một n&uacute;t được truy cập lần đầu ti&ecirc;n trong khi duyệt DFS. Đối với c&aacute;c n&uacute;t A, B, C, .., J trong c&acirc;y DFS, gi&aacute; trị Disc l&agrave; 1, 2, 3, .., 10.</p> <p style="text-align: justify;">Low: Trong c&acirc;y DFS, c&aacute;c cạnh của c&acirc;y đưa ch&uacute;ng ta về ph&iacute;a trước, từ n&uacute;t gốc đến một trong những n&uacute;t con của n&oacute;. V&iacute; dụ, từ n&uacute;t C, c&aacute;c cạnh của c&acirc;y c&oacute; thể đưa ch&uacute;ng ta đến n&uacute;t G, n&uacute;t I. C&aacute;c cạnh quay lại đưa ch&uacute;ng ta l&ugrave;i lại, từ một n&uacute;t con đến một trong những n&uacute;t gốc của n&oacute;. V&iacute; dụ: từ n&uacute;t G, c&aacute;c cạnh quay lại đưa ch&uacute;ng ta đến E hoặc C. Nếu ch&uacute;ng ta xem x&eacute;t cả cạnh của c&acirc;y v&agrave; cạnh quay lại c&ugrave;ng nhau, th&igrave; ch&uacute;ng ta c&oacute; thể thấy rằng nếu ch&uacute;ng ta bắt đầu duyệt từ một n&uacute;t, ch&uacute;ng ta c&oacute; thể đi xuống c&acirc;y th&ocirc;ng qua c&aacute;c cạnh của c&acirc;y v&agrave; sau đ&oacute; đi l&ecirc;n qua c&aacute;c cạnh quay lại. V&iacute; dụ: từ n&uacute;t E, ch&uacute;ng ta c&oacute; thể đi xuống G v&agrave; sau đ&oacute; đi l&ecirc;n C. Tương tự từ E, ch&uacute;ng ta c&oacute; thể đi xuống I hoặc J v&agrave; sau đ&oacute; đi l&ecirc;n F. Gi&aacute; trị Low của một n&uacute;t cho biết n&uacute;t c&oacute; thể truy cập n&uacute;t gốc cao nhất (với gi&aacute; trị Disc thấp nhất c&oacute; thể) th&ocirc;ng qua c&acirc;y con của n&uacute;t đ&oacute;. V&igrave; vậy, đối với bất kỳ n&uacute;t n&agrave;o, gi&aacute; trị Low bằng gi&aacute; trị Disc của n&oacute; (Một n&uacute;t l&agrave; n&uacute;t gốc của ch&iacute;nh n&oacute;). Sau đ&oacute;, ch&uacute;ng ta sẽ xem x&eacute;t c&acirc;y con của n&oacute; v&agrave; xem liệu c&oacute; n&uacute;t n&agrave;o c&oacute; thể đưa ch&uacute;ng ta đến bất kỳ n&uacute;t gốc n&agrave;o của n&oacute; hay kh&ocirc;ng. Nếu c&oacute; nhiều cạnh quay lại trong c&acirc;y con đưa ch&uacute;ng ta đến c&aacute;c n&uacute;t gốc kh&aacute;c nhau, th&igrave; ch&uacute;ng ta lấy một cạnh c&oacute; gi&aacute; trị Disc tối thiểu (tức l&agrave; cạnh tr&ecirc;n c&ugrave;ng). Nếu ch&uacute;ng ta nh&igrave;n v&agrave;o n&uacute;t F, n&oacute; c&oacute; hai c&acirc;y con. C&acirc;y con với n&uacute;t G, đưa ch&uacute;ng ta đến E v&agrave; C. C&acirc;y con c&ograve;n lại chỉ đưa ch&uacute;ng ta trở lại F. Ở đ&acirc;y n&uacute;t gốc tr&ecirc;n c&ugrave;ng l&agrave; C nơi F c&oacute; thể đạt tới v&agrave; do đ&oacute; gi&aacute; trị Low của F l&agrave; 3 (Gi&aacute; trị Disc của C).</p> <p style="text-align: justify;">C&aacute;c gi&aacute; trị Low của B, C v&agrave; D l&agrave; 1 (V&igrave; A l&agrave; n&uacute;t tr&ecirc;n c&ugrave;ng m&agrave; B, C v&agrave; D c&oacute; thể tiếp cận). Theo c&aacute;ch tương tự, gi&aacute; trị Low của E, F, G l&agrave; 3 v&agrave; gi&aacute; trị Low của H, I, J l&agrave; 6. Đối với bất kỳ n&uacute;t u n&agrave;o, khi DFS bắt đầu, Low sẽ được đặt th&agrave;nh gi&aacute; trị Disc đầu ti&ecirc;n của n&oacute;. Sau đ&oacute;, DFS sẽ được thực hiện tr&ecirc;n từng con của n&oacute; v, gi&aacute; trị Low của u c&oacute; thể thay đổi n&oacute; theo hai trường hợp:</p> <p style="text-align: justify;">Trường hợp 1 (Cạnh của c&acirc;y): Nếu n&uacute;t v chưa được truy cập, th&igrave; sau khi ho&agrave;n tất DFS của v, th&igrave; gi&aacute; trị thấp nhất của low[u] v&agrave; low[v] sẽ được cập nhật th&agrave;nh low [u].</p> <p class="ql-center-displayed-equation" style="text-align: center;">$\text{low}[u] = \text{min}(\text{low}[u], \text{low}[v])$</p> <p class="ql-center-displayed-equation" style="text-align: justify;">Trường hợp 2 (Cạnh quay lại): Khi n&uacute;t con v đ&atilde; được truy cập, th&igrave; gi&aacute; trị thấp nhất của low[u] v&agrave; disc[v] sẽ được cập nhật th&agrave;nh low[u].</p> <p class="ql-center-displayed-equation" style="text-align: center;">$\text{low}[u] = \text{min}(\text{low}[u], \text{disc}[v])$</p> <p class="ql-center-displayed-equation" style="text-align: left;"><img style="width: 100%;" src="../../../public_files/56fe4883-421b-476b-a22a-b9e9f439517e" alt="thuat-toan-tarjan-12" /></p> <p style="text-align: justify;">C&aacute;c gi&aacute; trị Low v&agrave; Disc giống nhau gi&uacute;p giải quyết c&aacute;c vấn đề kh&aacute;c của đồ thị như điểm li&ecirc;n kết của một đồ thị nếu loại bỏ n&oacute; th&igrave; sẽ l&agrave;m mất kết nối trong đồ thị, cầu nối v&agrave; th&agrave;nh phần li&ecirc;n kết hai chiều.</p> <p style="text-align: justify;">Để theo d&otilde;i c&acirc;y con bắt nguồn từ đầu, ch&uacute;ng ta c&oacute; thể sử dụng một ngăn xếp (tiếp tục đẩy n&uacute;t trong khi truy cập). Khi một n&uacute;t đầu được t&igrave;m thấy, ta sẽ lấy tất cả c&aacute;c n&uacute;t từ ngăn xếp cho đến khi tho&aacute;t ra khỏi ngăn xếp. Để đảm bảo, ch&uacute;ng ta sẽ kh&ocirc;ng xem x&eacute;t c&aacute;c cạnh ch&eacute;o, khi ch&uacute;ng ta đến một n&uacute;t đ&atilde; được truy cập, ch&uacute;ng ta chỉ n&ecirc;n xử l&yacute; n&uacute;t đ&atilde; truy cập nếu n&oacute; c&oacute; mặt trong ngăn xếp, nếu kh&ocirc;ng bỏ qua n&uacute;t đ&oacute;.</p> <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ề thuật to&aacute;n Tarjan trong việc t&igrave;m c&aacute;c th&agrave;nh phần li&ecirc;n th&ocirc;ng mạnh hay kết nối chặt chẽ. 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>