Đồ thị & Ghép cặp
Edmonds Blossom Algorithm (General Matching)
ID: #285
Xem trên trang chủ
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
ID: #335
Xem trên trang chủ
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
ID: #377
Xem trên trang chủ
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.