Biconnected Components & Block-Cut Tree
Mô tả nguyên lý
Phân rã đồ thị thành các thành phần song liên thông và cây cầu cắt (Block-Cut Tree).
Cài đặt mẫu (Implementation)
// Dựa trên DFS và mảng low/discovery time để gom nhóm các đỉnh không bị ngắt kết nối khi mất một đỉnh.
Eulerian Path and Circuit
Mô tả nguyên lý
Tìm đường đi hoặc chu trình đi qua tất cả các cạnh của đồ thị đúng một lần (Hierholzer).
Cài đặt mẫu (Implementation)
function findEulerianPath(&$graph, $u, &$path) {
while (!empty($graph[$u])) {
$v = array_pop($graph[$u]);
findEulerianPath($graph, $v, $path);
}
$path[] = $u;
}
Gomory-Hu Cut Tree Construction
Mô tả nguyên lý
Biểu diễn toàn bộ các lát cắt cực tiểu giữa mọi cặp đỉnh trong đồ thị vô hướng thành một cây gọn.
Cài đặt mẫu (Implementation)
// Thực hiện V-1 lần tính toán luồng cực đại trên các phân vùng đồ thị con.
Stoer-Wagner Min Cut Algorithm
Mô tả nguyên lý
Tìm lát cắt nhỏ nhất (Global Minimum Cut) trong đồ thị vô hướng trọng số không âm.
Cài đặt mẫu (Implementation)
// Thuật toán thu gọn các cặp đỉnh liên tiếp cho đến khi đồ thị chỉ còn hai siêu đỉnh.
Yen Algorithm (K-Shortest Paths)
Mô tả nguyên lý
Tìm K đường đi ngắn nhất từ một đỉnh nguồn đến đỉnh đích trong đồ thị có trọng số.
Cài đặt mẫu (Implementation)
// Kết hợp thuật toán đường đi ngắn nhất cơ bản với việc sinh các đường đi lệch nhánh tiềm năng.