Cấu trúc dữ liệu và Giải thuật Bài 89: Thành phần liên thông mạnh (Strongly Connected Components) - Thuật toán Tarjan và Kosaraju.

Trong kỹ thuật phân tích đồ thị, đặc biệt là khi bạn thiết kế kiến trúc vi dịch vụ (Microservices) hoặc phân tích mạng xã hội, một khái niệm cực kỳ quan trọng thường xuyên xuất hiện: Tính liên thông.

Đối với một đồ thị vô hướng, nếu bạn có thể đi từ đỉnh $A$ đến đỉnh $B$, hiển nhiên bạn cũng có thể đi ngược lại từ $B$ về $A$. Nhưng trong một đồ thị có hướng (Directed Graph), chiều đi bị giới hạn. Có thể bạn đi được từ máy chủ $A$ sang máy chủ $B$, nhưng không thể có đường vòng ngược lại.

Một cụm các đỉnh được gọi là Thành phần liên thông mạnh (Strongly Connected Component - SCC) nếu từ bất kỳ đỉnh nào trong cụm đó, bạn đều có đường đi đến tất cả các đỉnh còn lại trong cùng cụm.

Làm sao để khoanh vùng và chia nhỏ một mạng lưới khổng lồ thành các SCC rời rạc? Hai thuật toán vĩ đại nhất để giải quyết bài toán này trong thời gian tuyến tính $O(V + E)$ là Thuật toán Kosaraju và Thuật toán Tarjan.

1. Thuật toán Kosaraju: Sự thanh lịch của Đồ thị Đảo ngược

Thuật toán Kosaraju được thiết kế dựa trên một quan sát toán học cực kỳ sắc bén: Nếu một cụm đỉnh là một SCC, thì khi bạn đảo ngược chiều của tất cả các cạnh trên đồ thị, cụm đỉnh đó vẫn là một SCC. Tuy nhiên, các đường đi "một chiều" thoát ra khỏi SCC đó sẽ bị chặn đứng lại.

Kosaraju thực hiện phân tách qua 3 bước rất dễ hiểu:

1. DFS lượt 1 (Lấy thứ tự topologically-like): Duyệt DFS trên đồ thị gốc. Khi một đỉnh đã duyệt xong hoàn toàn (không còn đỉnh con nào để đi tiếp), ta đẩy nó vào một Ngăn xếp (Stack). Những đỉnh nằm ở "cuối nguồn" sẽ vào Stack trước, những đỉnh "đầu nguồn" sẽ vào Stack sau cùng.

2. Đảo ngược đồ thị (Transpose Graph): Xây dựng một đồ thị mới, trong đó mọi cạnh $u \rightarrow v$ bị lật ngược thành $v \rightarrow u$.

3. DFS lượt 2 (Khám phá SCC): Rút từng đỉnh ra khỏi Ngăn xếp (Stack) từ trên xuống. Nếu đỉnh đó chưa bị thăm, thực hiện DFS trên Đồ thị đảo ngược bắt đầu từ đỉnh đó. Toàn bộ những đỉnh mà lượt DFS này chạm tới sẽ tạo thành đúng một Thành phần liên thông mạnh.

Ưu điểm: Cực kỳ dễ hiểu và dễ code, tư duy rõ ràng.

Nhược điểm: Phải chạy DFS 2 lần và tốn thêm bộ nhớ để xây dựng một bản đồ thị lật ngược.

2. Thuật toán Tarjan: Một lượt DFS duy nhất với mảng Low-Link

Nếu Kosaraju cần đến 2 lượt quét và 2 đồ thị, thì Robert Tarjan (người sáng tạo ra DSU ở Bài 85) lại đưa ra một thuật toán chỉ cần duyệt DFS đúng một lần duy nhất.

Tarjan duy trì một Ngăn xếp (Stack) để lưu các đỉnh đang được xét và sử dụng 2 giá trị tại mỗi đỉnh $u$:

• discovery_time[u]: Thời điểm (số thứ tự) mà đỉnh $u$ được thăm lần đầu.

• low_link[u]: Nút có discovery_time nhỏ nhất mà đỉnh $u$ (hoặc các con cháu của nó) có thể "đi ngược" về được thông qua các cạnh ngược (back-edges). Cạnh ngược này phải trỏ về một đỉnh vẫn đang nằm trong Stack.

Cơ chế cốt lõi:

Khi thuật toán DFS lùi lại (backtrack) khỏi một đỉnh $u$, nó sẽ kiểm tra:

Nếu low_link[u] == discovery_time[u], nghĩa là từ $u$ không có cách nào đi ngược lên một đỉnh tổ tiên cao hơn nó. $u$ chính là "đỉnh chốt" (Root) của một Thành phần liên thông mạnh! Lúc này, thuật toán chỉ việc pop liên tục các đỉnh ra khỏi Stack cho đến khi gặp lại $u$ — toàn bộ các đỉnh vừa pop ra tạo thành một SCC.

3. Trực quan hóa Thuật toán Tarjan

Dưới đây là mô phỏng cách Tarjan đi sâu vào đồ thị, cập nhật giá trị low_link khi chạm trán cạnh ngược, và chốt hạ một SCC khi lùi lại.

4. Triển khai Thuật toán Tarjan bằng Golang

Đoạn code Golang dưới đây thể hiện sự gọn gàng và sức mạnh của thuật toán Tarjan trên đồ thị có hướng:

Go

package main

import (
	"fmt"
)

type TarjanSCC struct {
	graph       [][]int
	time        int
	disc        []int
	low         []int
	inStack     []bool
	stack       []int
	components  [][]int
}

func NewTarjanSCC(n int, edges [][]int) *TarjanSCC {
	g := make([][]int, n)
	for _, edge := range edges {
		u, v := edge[0], edge[1]
		g[u] = append(g[u], v)
	}

	disc := make([]int, n)
	low := make([]int, n)
	inStack := make([]bool, n)
	
	// Gán -1 để nhận biết đỉnh chưa được thăm
	for i := 0; i < n; i++ {
		disc[i] = -1
		low[i] = -1
	}

	return &TarjanSCC{
		graph:   g,
		disc:    disc,
		low:     low,
		inStack: inStack,
		stack:   []int{},
	}
}

func (t *TarjanSCC) dfs(u int) {
	// Khởi tạo thời gian khám phá và low-link
	t.disc[u] = t.time
	t.low[u] = t.time
	t.time++

	// Đẩy đỉnh u vào Stack
	t.stack = append(t.stack, u)
	t.inStack[u] = true

	// Duyệt qua các đỉnh kề
	for _, v := range t.graph[u] {
		if t.disc[v] == -1 {
			// Đỉnh v chưa được thăm, đi sâu vào v
			t.dfs(v)
			// Khi lùi lại, cập nhật low-link của u nếu v có đường chéo lên cao hơn
			if t.low[v] < t.low[u] {
				t.low[u] = t.low[v]
			}
		} else if t.inStack[v] {
			// Nếu v đã thăm và ĐANG nằm trong Stack, đây là cạnh ngược (back-edge)
			if t.disc[v] < t.low[u] {
				t.low[u] = t.disc[v]
			}
		}
	}

	// Nếu u là đỉnh chốt của một SCC (không thể lùi cao hơn được nữa)
	if t.low[u] == t.disc[u] {
		var scc []int
		for {
			// Pop đỉnh ra khỏi Stack
			v := t.stack[len(t.stack)-1]
			t.stack = t.stack[:len(t.stack)-1]
			t.inStack[v] = false
			
			scc = append(scc, v)
			
			// Dừng pop khi đã lấy chính đỉnh chốt u ra
			if u == v {
				break
			}
		}
		t.components = append(t.components, scc)
	}
}

func (t *TarjanSCC) FindSCCs() [][]int {
	for i := 0; i < len(t.graph); i++ {
		if t.disc[i] == -1 {
			t.dfs(i)
		}
	}
	return t.components
}

func main() {
	// Đồ thị 5 đỉnh (0 đến 4)
	n := 5
	edges := [][]int{
		{1, 0}, {0, 2}, {2, 1}, // Tạo SCC 1: {0, 1, 2}
		{0, 3},                 // Đường nối sang SCC 2
		{3, 4},                 // Mảnh rẽ lẻ tẻ (SCC riêng rẽ)
	}

	t := NewTarjanSCC(n, edges)
	sccs := t.FindSCCs()

	fmt.Printf("Tìm thấy %d Thành phần liên thông mạnh:\n", len(sccs))
	for i, scc := range sccs {
		fmt.Printf("SCC %d: %v\n", i+1, scc)
	}
}

5. Phân tích Hiệu năng (Big-O) và Ứng dụng Thực tế

• Thời gian thực thi: $O(V + E)$ (Cả Kosaraju và Tarjan). Thuật toán chỉ đi qua mỗi đỉnh và mỗi cạnh một số lần hằng số rất nhỏ, đạt mức tối ưu tuyệt đối cho mọi kích thước đồ thị.

• Không gian (RAM): $O(V)$. Tarjan tối ưu hơn Kosaraju vì không cần phải phân bổ bộ nhớ để tạo thêm một bản sao đồ thị đảo ngược.

Ứng dụng cốt lõi ở tầng Enterprise:

1. Phát hiện chu trình vòng lặp (Deadlock Detection): Trong kiến trúc Microservices hoặc thiết kế Database, nếu một cụm các Transaction hoặc Services khóa lẫn nhau tạo thành một SCC lớn hơn 1 đỉnh, hệ thống đang bị Deadlock (Chờ nhau vô tận).

2. Khuyên nghị bạn bè (Social Networks): Nhóm các tài khoản follow chéo lẫn nhau (A follow B, B follow C, C follow A) thành một "Cộng đồng khép kín" để phân tích hành vi và gợi ý kết bạn nội bộ.

3. Tối ưu hóa Trình biên dịch (Compiler Optimization): Gom nhóm các hàm (functions) gọi chéo lẫn nhau (recursive dependencies) thành các khối (blocks) độc lập để tối ưu hóa việc phân bổ Register trên CPU.

Các thuật toán đồ thị nâng cao đã xử lý rất tốt các dữ liệu trừu tượng. Nhưng nếu đỉnh đồ thị không phải là các máy chủ mà là một lưới tọa độ thực tế (ví dụ: Bản đồ số), và số lượng đỉnh lớn đến mức thuật toán truyền thống bị cạn kiệt RAM, chúng ta phải chuyển sang kỹ thuật Đồ thị Đẳng cấu với một cách biểu diễn hoàn toàn mới.