Cấu trúc dữ liệu và Giải thuật Bài 61: Giới thiệu Luồng mạng (Network Flow) và Thuật toán Ford-Fulkerson.

Chúng ta đã khép lại Chương 12 với các cấu trúc truy vấn khoảng nâng cao. Bước sang Chương 13: Đồ thị nâng cao & Luồng mạng, chúng ta sẽ đối mặt với một lớp bài toán mang tính thực tiễn cực kỳ cao trong các hệ thống phân tán, viễn thông và logistics: Bài toán Luồng cực đại (Maximum Flow Problem).

Hãy tưởng tượng bạn là kỹ sư hạ tầng mạng tại một công ty Cloud lớn. Bạn có một hệ thống cáp quang phức tạp kết nối từ Trung tâm dữ liệu nguồn (Source - $s$) đến Máy chủ đích (Sink - $t$) đi qua hàng loạt các trạm trung chuyển. Mỗi đường cáp quang có một giới hạn băng thông tối đa (Capacity). Câu hỏi đặt ra là: Lượng dữ liệu lớn nhất có thể truyền tải từ nguồn $s$ đến đích $t$ trong mỗi giây là bao nhiêu mà không làm quá tải bất kỳ đường cáp nào?

Đây chính là bài toán Luồng mạng được giải quyết bởi nền tảng lý thuyết mạng và thuật toán kinh điển Ford-Fulkerson.

1. Giải phẫu một Mạng lưới Luồng (Flow Network)

Một Mạng lưới luồng là một Đồ thị có hướng $G = (V, E)$, trong đó mỗi cạnh $(u, v)$ sở hữu một chỉ số gọi là Dung lượng tối đa (Capacity - $c(u, v)$).

Hệ thống phải tuân thủ 2 định luật vật lý nghiêm ngặt:

1. Ràng buộc dung lượng (Capacity Constraint): Dòng chảy thực tế đi qua một cạnh $f(u, v)$ không bao giờ được phép vượt quá dung lượng tối đa của cạnh đó ($0 \le f(u, v) \le c(u, v)$).

2. Bảo toàn luồng (Flow Conservation): Tại mọi đỉnh trung gian (không phải nguồn $s$ và đích $t$), tổng lượng dòng chảy đi vào phải đúng bằng tổng lượng dòng chảy đi ra. Nước chảy vào bao nhiêu thì phải thoát ra bấy nhiêu, không được tích tụ lại ở trạm trung chuyển.

2. Tư duy của Thuật toán Ford-Fulkerson và Đồ thị Thặng dư (Residual Graph)

Phản xạ tự nhiên của lập trình viên là tìm một đường đi từ $s$ đến $t$ rồi bơm tối đa dữ liệu vào đó cho đến khi nghẽn, sau đó tìm đường khác. Tuy nhiên, cách làm này sẽ thất bại vì một quyết định sai lầm ở bước đầu có thể bóp nghẹt toàn bộ các cơ hội tối ưu về sau.

Năm 1956, Lester Ford và Delbert Fulkerson đã giải quyết bài toán này bằng một thiên tài kỹ thuật gọi là Đồ thị thặng dư (Residual Graph).

Bên cạnh đồ thị gốc, họ duy trì một đồ thị thặng dư ghi nhận dung lượng còn lại có thể khai thác trên mỗi cạnh:

• Nếu một cạnh có dung lượng $c = 10$ và đang tải luồng $f = 4$, dung lượng thặng dư theo chiều xuôi là $10 - 4 = 6$.

• Điểm đột phá nằm ở Cạnh nghịch đảo (Reverse Edge): Đồ thị tự động mở một đường lùi với dung lượng bằng chính lượng luồng đã chảy qua ($4$). Điều này tạo ra một "Cơ chế sửa sai" (Undo): Nếu ở bước sau hệ thống nhận ra việc đẩy luồng qua hướng đó làm kẹt các đường khác, thuật toán có thể "rút bớt" dòng chảy cũ để nhường chỗ cho các đường đi tối ưu hơn.

Quá trình tìm kiếm các đường đi từ $s$ đến $t$ trên đồ thị thặng dư được gọi là Đường tăng luồng (Augmenting Path). Thuật toán cứ lặp đi lặp lại việc tìm đường tăng luồng, bơm dung lượng vào đó, cập nhật đồ thị thặng dư cho đến khi không còn tìm thấy bất kỳ đường đi nào nữa. Lúc đó, ta đạt được Luồng cực đại (Max Flow).

3. Triển khai Edmonds-Karp (Biến thể tối ưu của Ford-Fulkerson) bằng Golang

Nếu dùng thuật toán DFS thuần túy để tìm đường tăng luồng, Ford-Fulkerson có thể lặp vô hạn hoặc chạy rất chậm nếu dung lượng có giá trị thực hoặc số nguyên lớn. Trong thực tế, các kỹ sư luôn sử dụng Edmonds-Karp Algorithm — một biến thể thay thế DFS bằng BFS (Breadth-First Search) để luôn tìm đường đi ngắn nhất, đảm bảo thuật toán kết thúc với độ phức tạp đa thức tuyệt đối.

Dưới đây là cài đặt chuẩn mực sử dụng Ma trận kề (Adjacency Matrix):

Go

package main

import (
	"fmt"
	"math"
)

// Tìm đường đi ngắn nhất từ s đến t trên đồ thị thặng dư bằng BFS
func bfs(rGraph [][]int, s, t int, parent []int) bool {
	visited := make([]bool, len(rGraph))
	queue := []int{s}
	visited[s] = true
	parent[s] = -1

	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]

		for v := 0; v < len(rGraph); v++ {
			// Nếu chưa thăm và dung lượng thặng dư > 0
			if !visited[v] && rGraph[u][v] > 0 {
				queue = append(queue, v)
				parent[v] = u
				visited[v] = true
				if v == t {
					return true // Đã tìm thấy đường đi tới đích t
				}
			}
		}
	}
	return false
}

// Thuật toán Edmonds-Karp (Ford-Fulkerson kết hợp BFS)
// Độ phức tạp thời gian: O(V * E^2)
func MaxFlow(graph [][]int, s, t int) int {
	numVertices := len(graph)
	
	// Tạo đồ thị thặng dư (Residual Graph), ban đầu sao chép hoàn toàn từ đồ thị gốc
	rGraph := make([][]int, numVertices)
	for i := range graph {
		rGraph[i] = make([]int, numVertices)
		copy(rGraph[i], graph[i])
	}

	parent := make([]int, numVertices)
	maxFlow := 0

	// Lặp lại việc tìm đường tăng luồng bằng BFS
	for bfs(rGraph, s, t, parent) {
		// 1. Tìm dung lượng thặng dư nhỏ nhất dọc theo đường đi vừa tìm được
		pathFlow := math.MaxInt32
		for v := t; v != s; v = parent[v] {
			u := parent[v]
			if rGraph[u][v] < pathFlow {
				pathFlow = rGraph[u][v]
			}
		}

		// 2. Cập nhật dung lượng thặng dư cho các cạnh xuôi và cạnh ngược (Undo mechanism)
		for v := t; v != s; v = parent[v] {
			u := parent[v]
			rGraph[u][v] -= pathFlow // Trừ dung lượng cạnh xuôi
			rGraph[v][u] += pathFlow // Cộng dồn dung lượng cạnh ngược (cho phép đổi hướng)
		}

		// Cộng dồn vào tổng luồng cực đại
		maxFlow += pathFlow
	}

	return maxFlow
}

4. Phân tích Hiệu năng (Big-O)

• Thời gian (Edmonds-Karp): $O(V \cdot E^2)$ (với $V$ là số đỉnh và $E$ là số cạnh). Nhờ sử dụng BFS tìm đường ngắn nhất, số lần lặp của thuật toán bị chặn trên một cách chặt chẽ, loại bỏ hoàn toàn rủi ro chạy vô hạn của Ford-Fulkerson nguyên thủy.

• Không gian (RAM): $O(V^2)$ để lưu trữ ma trận kề của đồ thị thặng dư.

5. Ứng dụng Thực tế trong Kiến trúc Hệ thống

Bài toán Luồng mạng có vẻ trừu tượng, nhưng nó là chìa khóa giải quyết rất nhiều bài toán tối ưu hóa công nghiệp:

• Định tuyến dữ liệu & Băng thông mạng (Network Routing): Các nhà cung cấp viễn thông sử dụng thuật toán Max Flow để tính toán công suất truyền tải tối đa qua các tuyến cáp quang ngầm giữa các trạm trung tâm mà không làm nghẽn mạch.

• Hệ thống phân bổ tài nguyên & Lập lịch công việc (Task Scheduling / Bipartite Matching): Chuyển đổi bài toán phân công hàng ngàn nhân sự (hoặc server tính toán) vào các dự án sao cho khớp với kỹ năng và thời gian thành một bài toán luồng mạng chuẩn mực để tìm ra hiệu suất khai thác tối đa.

• Phân phối hàng hóa chuỗi cung ứng (Logistics): Tối ưu hóa lưu lượng xe tải vận chuyển hàng từ các kho tổng đến các điểm phân phối qua các tuyến đường có giới hạn trọng tải khác nhau.

Việc làm chủ Network Flow mở ra một tầm nhìn toán học cực kỳ sắc bén khi xử lý các tài nguyên giới hạn trong hệ thống phân tán. Khi các bài toán mạng lưới vượt ra ngoài các luồng tuyến tính đơn thuần và đòi hỏi việc phân tách cấu trúc thành các thành phần liên thông mạnh, chúng ta sẽ bước sang một kỹ thuật duyệt đồ thị đỉnh cao khác.