Mô phỏng thuật toán Ghép cặp nhị phân (Kuhn)

Kuhn Maximum Bipartite Matching · Nhóm: Đồ thị

Ghép cặp nhị phân (Kuhn) (Kuhn Maximum Bipartite Matching), nhóm Đồ thị.

Mã Python

def kuhn(adj, lefts):
    match = {}            # R -> L
    def try_aug(u, used):
        for v in adj[u]:
            if v in used: continue
            used.add(v)
            if v not in match \
               or try_aug(match[v], used):
                match[v] = u
                return True
        return False
    for u in lefts:
        try_aug(u, set())
    return match

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.