Cấu trúc dữ liệu và Giải thuật Bài 109: Đồ thị nâng cao (Thuật toán Tarjan tìm cầu và khớp) - Phát hiện điểm yếu và liên kết trọng yếu trong hệ thống mạng.

Trong quản trị hệ thống mạng phân tán, hạ tầng viễn thông, hay sơ đồ định tuyến gói tin (Routing topology), một trong những bài toán sinh tử là Độ bền vững của mạng lưới (Network Resiliency).

Giả sử bạn có một hệ thống gồm hàng trăm máy chủ kết nối với nhau qua các đường truyền cáp quang.

• Điều gì xảy ra nếu một máy chủ chết đi và khiến toàn bộ cụm hạ tầng phía sau bị cô lập hoàn toàn? Máy chủ đó được gọi là Điểm khớp (Articulation Point / Cut Vertex).

• Điều gì xảy ra nếu một đường cáp quang đứt và chia đôi hệ thống thành hai phần không thể liên lạc với nhau? Đường cáp đó được gọi là Cầu (Bridge / Cut Edge).

Trong lý thuyết đồ thị, việc phát hiện ra các "điểm chết" và "liên kết trọng yếu" này bằng tay là bất khả thi khi quy mô mạng lưới lớn. Thuật toán Tarjan chính là cỗ máy quét tối ưu giúp tìm ra toàn bộ Cầu và Khớp chỉ trong một lần duyệt đồ thị duy nhất với độ phức tạp tuyến tính $O(V + E)$.

1. Hai khái niệm cốt lõi: disc và low

Thuật toán Tarjan sử dụng phép duyệt DFS (Depth-First Search) và thiết lập hai mảng số nguyên cực kỳ quan trọng cho mỗi đỉnh $u$:

1. disc[u] (Discovery Time - Thời gian thăm): Thời điểm (hoặc thứ tự) mà thuật toán lần đầu tiên đặt chân đến đỉnh $u$ trong quá trình DFS.

2. low[u] (Lowest Reachable - Giá trị thấp nhất vươn tới được): Giá trị disc nhỏ nhất mà đỉnh $u$ hoặc bất kỳ hậu duệ nào của nó trong cây DFS có thể đi tới được thông qua các cạnh xuôi (tree edges) và tối đa một cạnh ngược (back edge) quay về tổ tiên.

Công thức cập nhật khi duyệt từ $u$ sang nút con $v$:

• Nếu $v$ chưa được thăm (nút con trong cây DFS):

  dfs(v)

  low[u] = min(low[u], low[v])

  • Kiểm tra Cầu (Bridge): Nếu low[v] > disc[u], thì cạnh $(u, v)$ chính là một Cầu. (Lý do: Từ nhánh con $v$ không có bất kỳ đường vòng/cạnh ngược nào quay ngược về tổ tiên của $u$. Nếu đứt cạnh này, hệ thống đứt làm đôi).

• Nếu $v$ đã được thăm và không phải là cha trực tiếp của $u$ (tồn tại cạnh ngược - back edge):

  low[u] = min(low[u], disc[v])

  • Kiểm tra Khớp (Articulation Point): Nếu $u$ là đỉnh gốc của cây DFS và có từ 2 con trở lên, $u$ là khớp. Nếu $u$ không phải gốc và có một nút con $v$ thỏa mãn low[v] >= disc[u], thì $u$ là một Điểm khớp.

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

Đoạn code Golang dưới đây cài đặt thuật toán Tarjan để quét và phát hiện toàn bộ các Cầu (Bridges) và Đỉnh khớp (Articulation Points) trên một đồ thị vô hướng:

Go

package main

import (
	"fmt"
)

var (
	timer        int
	disc, low    []int
	isAP         []bool // Đánh dấu các đỉnh là điểm khớp
	bridges      [][2]int // Lưu trữ các cặp cạnh là cầu
	adj          [][]int
)

func dfs(u, p int) {
	disc[u] = timer
	low[u] = timer
	timer++
	children := 0

	for _, v := range adj[u] {
		if v == p {
			continue
		}
		if disc[v] != -1 {
			// Tồn tại cạnh ngược (Back edge) -> cập nhật low của u
			if disc[v] < low[u] {
				low[u] = disc[v]
			}
		} else {
			// Nút con chưa được thăm
			children++
			dfs(v, u)

			// Cập nhật low sau khi đệ quy về
			if low[v] < low[u] {
				low[u] = low[v]
			}

			// Điều kiện 1: Phát hiện Cầu (Bridge)
			if low[v] > disc[u] {
				bridges = append(bridges, [2]int{u, v})
			}

			// Điều kiện 2: Phát hiện Điểm khớp (Articulation Point)
			// Nếu u không phải gốc DFS và low của con v >= disc của u
			if p != -1 && low[v] >= disc[u] {
				isAP[u] = true
			}
		}
	}

	// Nếu u là gốc DFS và có từ 2 con trở lên trong cây DFS -> u là điểm khớp
	if p == -1 && children > 1 {
		isAP[u] = true
	}
}

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

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

	// Xây dựng đồ thị mẫu
	addEdge(0, 1)
	addEdge(1, 2)
	addEdge(2, 0)
	addEdge(1, 3)
	addEdge(3, 4)

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

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

	// In kết quả các Cầu (Bridges)
	fmt.Println("Các liên kết trọng yếu (Cầu - Bridges):")
	for _, b := range bridges {
		fmt.Printf("Cạnh: %d - %d\n", b[0], b[1])
	}

	// In kết quả các Điểm khớp (Articulation Points)
	fmt.Println("\nCác điểm yếu hệ thống (Điểm khớp - Articulation Points):")
	for i := 0; i < n; i++ {
		if isAP[i] {
			fmt.Printf("Đỉnh: %d\n", i)
		}
	}
}

3. Ứng dụng thực tế trong Hệ thống phân tán

• Phát hiện Single Point of Failure (SPOF): Trong kiến trúc Microservices, nếu sơ đồ gọi API giữa các dịch vụ tạo thành một đồ thị có điểm khớp, hệ thống sẽ sập toàn bộ nếu dịch vụ tại điểm khớp đó gặp sự cố.

• An ninh mạng & Viễn thông: Giúp các kỹ sư nhà mạng xác định chính xác các trạm chuyển mạch hoặc tuyến cáp trọng yếu cần phải thiết lập đường truyền dự phòng (Redundancy) ngay lập tức để tránh tê liệt toàn bộ hệ thống.

Thuật toán Tarjan là một kiệt tác của tư duy đồ thị, biến một bài toán tìm kiếm cấu trúc phức tạp thành vài dòng tính toán số nguyên tinh tế.