Đồ thị & Ghép cặp

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

Đồ thị & Ghép cặp

Edmonds Blossom Algorithm (General Matching)

Thời gian (Time) O(V^4)
Không gian (Space) O(V)

Mô tả nguyên lý

Thuật toán tìm cặp ghép cực đại trên đồ thị tổng quát (vô hướng bất kỳ không giới hạn đồ thị hai phía).

Cài đặt mẫu (Implementation)

// Phát hiện và thu gọn các chu trình lẻ (blossoms) thành siêu đỉnh để tìm đường tăng tiến.
Đồ thị & Ghép cặp

Edmonds Blossom General Matching

Thời gian (Time) O(V^4)
Không gian (Space) O(V)

Mô tả nguyên lý

Tìm cặp ghép cực đại trên đồ thị tổng quát vô hướng bất kỳ (xử lý chu trình lẻ hoa hồng - blossom).

Cài đặt mẫu (Implementation)

// Thu gọn các chu trình lẻ thành siêu đỉnh trong quá trình tìm đường tăng tiến.
Đồ thị & Ghép cặp

Hopcroft-Karp Bipartite Matching

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

Mô tả nguyên lý

Tìm ghép cặp cực đại trong đồ thị hai phía với tốc độ tối ưu.

Cài đặt mẫu (Implementation)

// Kết hợp BFS tìm nhiều đường tăng tiến ngắn nhất đồng thời và tăng cường bằng DFS.