호프크로프트 카프

호프크로프트 카프 알고리즘(Hopcroft-Karp Algorithm)은 더 빠른 시간복잡도의 이분 매칭 알고리즘으로

앞서 이분 매칭에서 배운 포드-풀커슨 알고리즘을 변형한 방법의 시간복잡도는

정점 개수가 V 간선 개수가 E일 때 O(VE)였으나

호프크로프트 카프 알고리즘의 시간복잡도는 O(V^(1/2)E)입니다.

이 알고리즘에서 아래와 같은 새로운 용어를 사용합니다.

1. 교차 경로(Alternating Path) : 그래프 위의 경로 중 매칭되어 있지 않은 정점으로부터 시작하여

매칭을 이어주고 있지 않은 간선과 이어주고 있는 간선이 교차하는 규칙이 반복되는 경로

2. 증가 경로(Augmenting Path) : 양 끝 정점이 매칭되어 있지 않은 교차 경로

증가 경로가 존재하면 이를 뒤집어 반드시 매칭 크기를 1 늘릴 수 있다는 것과

앞서 배운 디닉 알고리즘을 응용하여 동작원리는 아래과 같습니다.

1. A그룹에 속해 있고 매칭되어 있지 않은 정점 레벨이 0으로 시작하여 교차 경로를 따라 레벨 그래프 생성한다.

2. 레벨이 0인 정점부터 증가경로 체크한다.

3. 더이상 증가경로를 찾지 못할 때까지 반복한다.

이 알고리즘을 이용하여 이분 매칭을 빠르게 구할 수 있습니다.

기본 문제

1733번: 등번호