Cấu trúc dữ liệu và Giải thuật Bài 110: Đồ thị nâng cao (Thành phần liên thông mạnh - SCC) - Phân rã đồ thị có hướng phức tạp.

Trong thế giới của đồ thị có hướng (Directed Graphs), các mối quan hệ thường mang tính một chiều: Dịch vụ A gọi dịch vụ B, giao dịch từ tài khoản X sang tài khoản Y, hoặc câu lệnh phụ thuộc trong biểu đồ biên dịch mã nguồn (Build System). Tuy nhiên, điều gì xảy ra nếu các mối quan hệ một chiều này vô tình tạo thành một vòng lặp khép kín (Circular Dependency)?

Ví dụ kinh điển trong kiến trúc phần mềm: Service A gọi sang Service B, B gọi sang C, và C lại gọi ngược về A. Nếu có lỗi xảy ra, toàn bộ cụm dịch vụ này sẽ vướng vào một vòng xoáy bế tắc (Deadlock hoặc Infinite Loop). Để phân tích và phân rã cấu trúc phức tạp của đồ thị có hướng thành các tiểu vùng mà mọi đỉnh bên trong đều có thể đi đến nhau, chúng ta sử dụng khái niệm Thành phần liên thông mạnh (Strongly Connected Components - SCC).

1. Định nghĩa Thành phần liên thông mạnh (SCC)

Một Thành phần liên thông mạnh (SCC) trong một đồ thị có hướng $G$ là một tập hợp các đỉnh sao cho với mọi cặp đỉnh $u$ và $v$ bất kỳ trong tập hợp đó, luôn tồn tại đường đi có hướng từ $u$ đến $v$ và ngược lại, tồn tại đường đi có hướng từ $v$ đến $u$.

Nói cách khác, bên trong một SCC, mọi đỉnh đều có thể "nhìn thấy" và di chuyển đến nhau. Mục tiêu của thuật toán tìm SCC là cô lập đồ thị thành các "cụm khép kín" độc lập nhau.

2. Thuật toán Tarjan tìm SCC (Tarjan's SCC Algorithm)

Tiếp nối tư duy sử dụng hai mảng disc (thời điểm thăm) và low (giá trị vươn tới thấp nhất) mà chúng ta đã làm quen ở Bài 109, Robert Tarjan đã phát minh ra một thuật toán cực kỳ tinh tế chỉ với một lần duyệt DFS duy nhất kết hợp với một Cấu trúc dữ liệu Ngăn xếp (Stack):

1. Duyệt DFS: Khi đi qua mỗi đỉnh $u$, ta đẩy $u$ vào một Stack tạm thời.

2. Cập nhật low: Giống như trước, disc[u] = low[u] = timer++. Khi duyệt qua các đỉnh kề $v$, nếu $v$ chưa thăm thì đệ quy, sau đó cập nhật low[u] = min(low[u], low[v]). Nếu $v$ đã thăm và còn nằm trong Stack, ta cập nhật low[u] = min(low[u], disc[v]).

3. Cô lập SCC: Khi quay lui từ một đỉnh $u$ mà thỏa mãn điều kiện disc[u] == low[u], điều này có nghĩa là $u$ chính là gốc của một thành phần liên thông mạnh. Ta tiến hành pop các phần tử khỏi Stack ra cho đến khi gặp lại chính đỉnh $u$. Tập hợp các đỉnh vừa pop ra chính là một SCC hoàn chỉnh!

Độ phức tạp thời gian của thuật toán là $O(V + E)$, tối ưu tuyệt đối cho mọi quy mô hệ thống.

3. Hiện thực hóa Thuật toán Tarjan SCC bằng Golang

Đoạn code Golang dưới đây cài đặt thuật toán Tarjan để phân rã một đồ thị có hướng thành các Thành phần liên thông mạnh (SCC):

Go

package main

import (
	"fmt"
)

var (
	timer        int
	disc, low    []int
	onStack      []bool
	stack        []int
	adj          [][]int
	sccList      [][]int
)

func dfs(u int) {
	disc[u] = timer
	low[u] = timer
	timer++
	stack = append(stack, u)
	onStack[u] = true

	for _, v := range adj[u] {
		if disc[v] == -1 {
			// Nút con chưa được thăm
			dfs(v)
			if low[v] < low[u] {
				low[u] = low[v]
			}
		} else if onStack[v] {
			// Nút v đã thăm và đang nằm trong Stack hiện tại (Cạnh ngược / Cross edge)
			if disc[v] < low[u] {
				low[u] = disc[v]
			}
		}
	}

	// Nếu u là gốc của một SCC
	if low[u] == disc[u] {
		var currentSCC []int
		for {
			v := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			onStack[v] = false
			currentSCC = append(currentSCC, v)
			if v == u {
				break
			}
		}
		sccList = append(sccList, currentSCC)
	}
}

func main() {
	// Số lượng đỉnh của đồ thị có hướng (từ 0 đến 6)
	n := 7
	adj = make([][]int, n)

	addEdge := func(u, v int) {
		adj[u] = append(adj[u], v)
	}

	// Xây dựng đồ thị mẫu có chứa các vòng lặp (Cycles)
	addEdge(0, 1)
	addEdge(1, 2)
	addEdge(2, 0)
	addEdge(1, 3)
	addEdge(3, 4)
	addEdge(4, 5)
	addEdge(5, 3)
	addEdge(6, 4)

	disc = make([]int, n)
	low = make([]int, n)
	onStack = make([]bool, n)
	for i := range disc {
		disc[i] = -1
	}

	timer = 0
	for i := 0; i < n; i++ {
		if disc[i] == -1 {
			dfs(i)
		}
	}

	// In kết quả các Thành phần liên thông mạnh (SCC)
	fmt.Println("Các Thành phần liên thông mạnh (SCC) trong đồ thị:")
	for idx, scc := range sccList {
		fmt.Printf("SCC #%d: %v\n", idx+1, scc)
	}
}

4. Ứng dụng thực tế

• Phát hiện Phụ thuộc vòng (Circular Dependencies) trong Build Systems: Các công cụ như Webpack, Maven, hoặc Go Modules dùng SCC để kiểm tra xem các package có bị gọi vòng tròn lẫn nhau không, từ đó báo lỗi biên dịch.

• Phân tích Cấu trúc Mạng xã hội & Web: Phân tích các cụm cộng đồng có độ tương tác hai chiều cao trong biểu đồ mạng lưới người dùng hoặc phân rã biểu đồ liên kết các trang web (Web Graph Crawler).

• Tối ưu hóa cơ sở dữ liệu & Giao dịch phân tán: Phát hiện các chu kỳ chờ khóa (Deadlock detection) trong hệ thống quản trị cơ sở dữ liệu quan hệ.

SCC khép lại hành trình khám phá đồ thị nâng cao, giúp chúng ta nhìn thấu tâm can của mọi cấu trúc liên kết phức tạp nhất.