Hopcroft-Karp 演算法（Hopcroft-Karp algorithm）
/ HOP-croft KARP /
找最大二分圖匹配的樸素做法，是一次次找一條增廣（交錯）路徑並翻轉它，這可能要多達 V 次增廣，每次都得搜尋一回。Hopcroft-Karp 用驅動 Dinic 的同一個洞見來加速：不是每回合一條路徑，而是一次找出並翻轉一整批極大的最短增廣路徑。批次處理把回合數從 V 砍到約 sqrt(V)。
每個階段做兩件事。第一，從所有未匹配的左頂點做 BFS，算出最短增廣路徑的長度，並按距離把圖分層。第二，用 DFS 找出一組極大的、頂點不相交的最短增廣路徑，並同時沿它們全部增廣。關鍵分析：每個階段後，最短增廣路徑的長度嚴格增加，而可證在 O(sqrt(V)) 個階段後，剩下的匹配距最大值不超過 sqrt(V)，故只需再 O(sqrt(V)) 次單路徑增廣——總共 O(sqrt(V)) 個階段。每個階段是對整個圖的一次 BFS 加一次 DFS，花 O(E)，故演算法以 O(E * sqrt(V)) 執行。這恰是 Dinic 的界特化到單位容量（匹配）網路，這並非巧合：Hopcroft-Karp 就是穿上匹配外衣的 Dinic。
Hopcroft-Karp 是最大二分圖匹配的標準快速演算法，藉由利用單位容量結構，勝過樸素的 O(V * E) 增廣路徑法與埃德蒙茲-卡普一般的 O(V * E^2)。當匹配很大、圖很大時——指派問題、二分覆蓋、排程——它正是對的工具。兩個誠實的提醒：O(E * sqrt(V)) 的界只給無權二分圖匹配（最小成本或最大權匹配需要匈牙利演算法或最小成本流），而一般非二分圖對應的快速演算法是 Micali-Vazirani，不是 Hopcroft-Karp。
在一個 V = 10000 個頂點的二分圖上，樸素的增廣路徑匹配器可能要做多達約 5000 次增廣搜尋；Hopcroft-Karp 約在 sqrt(10000) = 100 個階段內完成，每個階段只是對邊做一次線性掃描。最短增廣路徑的批次處理就是全部的勝因。
每階段批次處理所有最短增廣路徑，階段數降到 O(sqrt(V))——Dinic 的想法，特化到匹配。
Hopcroft-Karp 只解無權二分圖匹配。加權／最小成本的指派要用匈牙利演算法或最小成本流；一般非二分圖的快速對應是 Micali-Vazirani，不是這個演算法。