Cấu trúc dữ liệu và Giải thuật Bài 128: Cây khung nhỏ nhất có hướng (Directed MST / Arborescence - Thuật toán Chu-Liu/Edmonds) - Tối ưu hóa mạng lưới phân phối có hướng.

Đối với đồ thị vô hướng, bài toán Cây khung nhỏ nhất (Minimum Spanning Tree - MST) đã được giải quyết triệt để bằng các thuật toán tham lam kinh điển như Kruskal hay Prim trong thời gian $O(E \log V)$ . Tuy nhiên, khi các cạnh mang tính một chiều (đồ thị có hướng) — ví dụ: phân phối tín hiệu từ một trạm phát sóng nguồn đến tất cả các trạm thu, truyền gói tin multicast trong mạng máy tính, hoặc thiết lập luồng phân phối hàng hóa từ kho tổng — bài toán trở thành Tìm cây phân nhánh nhỏ nhất (Minimum Spanning Arborescence).

Trên đồ thị có hướng, thuật toán Kruskal và Prim hoàn toàn thất bại: việc chọn cạnh có trọng số nhỏ nhất mà không xét hướng có thể dẫn đến việc một đỉnh không thể đi tới từ nguồn hoặc đỉnh có nhiều hơn một cạnh đi vào. Để giải quyết bài toán này, Yoeng-Jin Chu và Tseng-Hong Liu (1965), cùng Jack Edmonds (1967) độc lập phát minh ra Thuật toán Chu-Liu/Edmonds, cho phép tìm cây khung có hướng nhỏ nhất xuất phát từ một gốc cố định trong thời gian $O(V \cdot E)$ .

1. Định nghĩa bài toán Minimum Spanning Arborescence

Cho một đồ thị có hướng có trọng số $G = (V, E)$ và một đỉnh gốc được chỉ định trước $r \in V$ .

Một Arborescence (cây phân nhánh có hướng) có gốc tại $r$ là một đồ thị con $T = (V, E_T)$ thỏa mãn:

$T$ không chứa chu trình có hướng.
Với mọi đỉnh $v \in V \setminus \{r\}$ , bán bậc vào (in-degree) của $v$ đúng bằng 1. Bán bậc vào của gốc $r$ bằng 0.
Tồn tại đường đi có hướng từ $r$ đến mọi đỉnh khác trong $V$ .

Mục tiêu của bài toán Minimum Spanning Arborescence (Directed MST) là tìm một cây phân nhánh $T$ sao cho tổng trọng số các cạnh là nhỏ nhất:

$\sum_{e \in E_T} w(e) \to \min$

2. Trực giác thuật toán Chu-Liu/Edmonds: Tham lam, Phát hiện chu trình và Co cụm

Thuật toán Chu-Liu/Edmonds tiếp cận bài toán qua 3 bước cốt lõi:

Bước 1: Tham lam chọn cạnh vào nhỏ nhất

Vì trong cây phân nhánh cuối cùng, mỗi đỉnh $v \neq r$ phải có đúng một cạnh đi vào, cách tiếp cận trực quan nhất là với mỗi đỉnh $v \neq r$ , chọn cạnh có trọng số nhỏ nhất đi vào $v$ :

$e_v = \arg\min_{(u, v) \in E} w(u, v)$

Nếu tồn tại một đỉnh $v \neq r$ không có cạnh nào đi vào, đồ thị không thể phủ kín từ $r$ (kết luận vô nghiệm).
Nếu tập các cạnh $\{e_v\}$ được chọn không tạo thành chu trình nào, thì tập cạnh này tạo thành một cây phân nhánh hợp lệ và tổng trọng số của chúng chính là kết quả tối ưu toàn cục.

Bước 2: Xử lý chu trình có hướng (Cycle Contraction)

Nếu tập cạnh $\{e_v\}$ xuất hiện một hoặc nhiều chu trình có hướng rời nhau:

Cây phân nhánh hợp lệ không được phép chứa chu trình.
Để phá vỡ một chu trình $C$ , ta bắt buộc phải bỏ đi đúng một cạnh bên trong chu trình đó và thay thế bằng một cạnh từ bên ngoài đi vào một đỉnh $v \in C$ .
Thuật toán co cụm (contract) toàn bộ các đỉnh thuộc chu trình $C$ thành một "siêu đỉnh" (super-vertex) duy nhất $v_C$ .

Bước 3: Công thức gán lại trọng số cạnh (Re-weighting Formula)

Khi co chu trình $C$ thành siêu đỉnh $v_C$ , bất kỳ cạnh nào $(u, v)$ từ bên ngoài đi vào một đỉnh $v \in C$ sẽ được cập nhật lại trọng số:

$w'(u, v) = w(u, v) - w(e_v)$

Trong đó $w(e_v)$ là trọng số của cạnh nội bộ trong chu trình đang đi vào $v$ .

Ý nghĩa: Trọng số $w'(u, v)$ thể hiện chi phí phụ trội thực tế nếu ta quyết định chọn cạnh $(u, v)$ từ ngoài vào, đồng thời loại bỏ cạnh nội bộ $e_v$ để phá vỡ chu trình.
Các cạnh nội bộ bên trong chu trình $C$ bị loại bỏ.
Các cạnh xuất phát từ chu trình $C$ đi ra ngoài giữ nguyên trọng số, chỉ đổi đỉnh nguồn thành siêu đỉnh $v_C$ .

Sau khi co các chu trình và điều chỉnh trọng số, ta thu được một đồ thị mới có ít đỉnh hơn. Thuật toán lặp lại quy trình trên đồ thị mới cho đến khi không còn chu trình nào xuất hiện.

3. Hiện thực hóa Thuật toán Chu-Liu/Edmonds bằng Golang

Đoạn mã Golang dưới đây cài đặt thuật toán Chu-Liu/Edmonds dạng lặp với cơ chế phát hiện chu trình và nén đồ thị trong $O(V \cdot E)$ :

package main

import (
	"fmt"
	"math"
)

const INF = math.MaxInt64 / 4

type Edge struct {
	u, v int
	cost int64
}

// ChuLiuEdmonds tìm trọng số Minimum Spanning Arborescence có gốc tại root
// Trả về -1 nếu không thể phủ toàn bộ các đỉnh từ root
func ChuLiuEdmonds(n, root int, edges []Edge) int64 {
	var totalCost int64 = 0

	for {
		// 1. Tìm cạnh có trọng số nhỏ nhất đi vào mỗi đỉnh v != root
		in := make([]int64, n)
		pre := make([]int, n)
		for i := 0; i < n; i++ {
			in[i] = INF
			pre[i] = -1
		}

		for _, e := range edges {
			if e.u != e.v && e.v != root && e.cost < in[e.v] {
				in[e.v] = e.cost
				pre[e.v] = e.u
			}
		}

		// Kiểm tra tính liên thông: mọi đỉnh != root phải có ít nhất 1 cạnh vào
		for i := 0; i < n; i++ {
			if i != root && in[i] == INF {
				return -1 // Không thể đến được đỉnh i từ root
			}
		}

		// 2. Phát hiện chu trình
		cycleCount := 0
		id := make([]int, n)
		vis := make([]int, n)
		for i := 0; i < n; i++ {
			id[i] = -1
			vis[i] = -1
		}

		in[root] = 0
		for i := 0; i < n; i++ {
			totalCost += in[i]
			v := i
			// Đi ngược theo cạnh vào để phát hiện chu trình
			for v != root && id[v] == -1 && vis[v] != i {
				vis[v] = i
				v = pre[v]
			}

			// Nếu phát hiện chu trình
			if v != root && id[v] == -1 {
				for id[v] == -1 {
					id[v] = cycleCount
					v = pre[v]
				}
				cycleCount++
			}
		}

		// Nếu không tồn tại chu trình nào, ta đã tìm được Directed MST
		if cycleCount == 0 {
			break
		}

		// 3. Đánh số lại các đỉnh không nằm trong chu trình
		for i := 0; i < n; i++ {
			if id[i] == -1 {
				id[i] = cycleCount
				cycleCount++
			}
		}

		// 4. Co chu trình và tính lại trọng số các cạnh
		newEdges := make([]Edge, 0, len(edges))
		for _, e := range edges {
			u := id[e.u]
			v := id[e.v]
			if u != v {
				newEdges = append(newEdges, Edge{
					u:    u,
					v:    v,
					cost: e.cost - in[e.v], // Điều chỉnh trọng số
				})
			}
		}

		edges = newEdges
		n = cycleCount
		root = id[root]
	}

	return totalCost
}

func main() {
	// Khởi tạo đồ thị có hướng gồm 4 đỉnh (0 đến 3)
	// Gốc được chỉ định: đỉnh 0
	n := 4
	root := 0

	edges := []Edge{
		{u: 0, v: 1, cost: 10},
		{u: 0, v: 2, cost: 2},
		{u: 0, v: 3, cost: 10},
		{u: 1, v: 2, cost: 1},
		{u: 2, v: 1, cost: 2},
		{u: 2, v: 3, cost: 4},
		{u: 3, v: 1, cost: 1},
	}

	cost := ChuLiuEdmonds(n, root, edges)
	if cost == -1 {
		fmt.Println("Không tồn tại cây phân nhánh bao phủ toàn bộ đồ thị từ gốc!")
	} else {
		fmt.Printf("Trọng số Minimum Spanning Arborescence từ gốc %d: %d\n", root, cost)
	}
}

4. Phân tích độ phức tạp thuật toán

Tiêu chí	Cài đặt lặp cơ bản (Code trên)	Cài đặt tối ưu (Tarjan / Skew Heap)
Độ phức tạp thời gian	$O(V \cdot E)$	$O(E \log V)$
Độ phức tạp bộ nhớ	$O(V + E)$	$O(V + E)$
Cơ chế co chu trình	Tái cấu trúc mảng cạnh sau mỗi vòng	Sử dụng Disjoint Set Union (DSU) và Priority Queue có thể gộp (Meldable Heap)
Trường hợp áp dụng	Đồ thị mật độ trung bình, cài đặt ngắn gọn	Đồ thị rất lớn ( $V, E \ge 10^5$ )

Số lần co chu trình tối đa: Mỗi vòng lặp phát hiện ít nhất một chu trình có $\ge 2$ đỉnh, làm giảm số đỉnh của đồ thị ít nhất 1. Do đó, số lần co tối đa là $V - 1$ .
Mỗi vòng lặp: Duyệt qua toàn bộ danh sách cạnh tốn $O(E)$ , phát hiện chu trình tốn $O(V)$ . Do đó, tổng thời gian là $O(V \cdot (E + V)) = O(V \cdot E)$ .

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

Định tuyến Multicast & Broadcast trong Mạng máy tính: Xây dựng cây phân phối gói tin từ một máy chủ nguồn (Source) đến toàn bộ các máy trạm với độ trễ hoặc chi phí truyền dẫn một chiều tối thiểu.
Xử lý ngôn ngữ tự nhiên (Dependency Parsing): Trong phân tích cú pháp phụ thuộc (Depedency Trees), mỗi câu được mô hình hóa thành một đồ thị có hướng mà các từ là đỉnh và mối quan hệ ngữ pháp là cạnh có trọng số (log-probability). Thuật toán Chu-Liu/Edmonds được dùng để tìm cây cú pháp chuẩn xác nhất cho câu.
Quy hoạch mạng lưới cấp nước & Điện một chiều: Thiết lập hệ thống đường ống hoặc đường dây truyền tải từ nhà máy phát đến các trạm phân phối nơi dòng chảy chỉ có thể di chuyển theo một chiều duy nhất do chênh lệch áp suất hoặc điện áp.

cấu trúc dữ liệu