Hopcroft-Karp Algorithm (1) 썸네일형 리스트형 147. Hopcroft-Karp Algorithm 앞에서 이분 그래프에서 포드-풀커슨 방법 등으로 최대 매칭을 구하면 시간복잡도가 $O(nm)$이 나온다고 했다. 이를 개선하여 시간복잡도를 $O(\sqrt{n}m)$으로 줄인 것이 호프크로프트-카프 알고리즘(Hopcroft-Karp Algorithm)이다. 내용을 소개하기에 앞서 이전에 어떤 세미나에서 발표자료로 사용한 PDF를 첨부한다. 자료가 충실해서 이 글보다 이해하기 쉬울 수 있다.이 알고리즘은 다음과 같은 방법으로 작동한다.그래프의 간선들에 방향을 정한다. (정점 그룹을 $\text{L}$과 $\text{R}$로 나눌 수 있을 때) 간선이 매칭에 포함되어 있으면 $\text{R} \to \text{L}$ 방향, 그렇지 않다면 $\text{L} \to \text{R}$ 방향으로 한다.$\text{.. 이전 1 다음
