Đồ thị nâng cao

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 5)

Đồ thị nâng cao

Biconnected Components & Block-Cut Tree

Thời gian (Time) O(V + E)
Không gian (Space) O(V + E)

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.
Đồ thị nâng cao

Eulerian Path and Circuit

Thời gian (Time) O(V + E)
Không gian (Space) O(V + E)

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;
}
Đồ thị nâng cao

Gomory-Hu Cut Tree Construction

Thời gian (Time) O(V * MaxFlow)
Không gian (Space) O(V^2)

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.
Đồ thị nâng cao

Stoer-Wagner Min Cut Algorithm

Thời gian (Time) O(V * E + V^2 log V)
Không gian (Space) O(V^2)

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.
Đồ thị nâng cao

Yen Algorithm (K-Shortest Paths)

Thời gian (Time) O(K * V * (E + V log V))
Không gian (Space) O(K * V)

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.