A Hopcroft–Karp algoritmus egy hatékony módszer a kétszeresen összefüggő gráfok (bipartite graphs) maximális párosításának meghatározására. Az algoritmus a Ford-Fulkerson-algoritmus speciális változata, amely optimalizált lépések révén javítja a futási időt.
A Hopcroft–Karp algoritmus iteratív módon működik:
Az algoritmus addig ismétli ezeket a lépéseket, amíg nem talál növelő utat.
A Hopcroft–Karp algoritmus futási ideje , ahol: - ( E ): az élek száma, - ( V ): a csúcsok száma.
Ez gyorsabb, mint az alap Ford-Fulkerson-alapú megközelítések, amelyek ( O(VE) )-s futási időt biztosítanak.
HopcroftKarp(G): M = üres párosítás while True: növelő_út_hossz = BFS(G, M) if növelő_út_hossz == ∞: break while True: növelő_út = DFS(G, M, növelő_út_hossz) if növelő_út == None: break Bővítsd a párosítást M-t a növelő út szerint return M
from collections import deque, defaultdict
def hopcroft_karp(graph, U, V):
pair_u = {u: None for u in U}
pair_v = {v: None for v in V}
dist = {}
def bfs():
queue = deque()
for u in U:
if pair_u is None:
dist = 0
queue.append(u)
else:
dist = float('inf')
dist = float('inf')
while queue:
u = queue.popleft()
if dist < dist:
for v in graph:
if dist] == float('inf'):
dist] = dist + 1
queue.append(pair_v)
return dist != float('inf')
def dfs(u):
if u is not None:
for v in graph:
if dist] == dist + 1:
if dfs(pair_v):
pair_v = u
pair_u = v
return True
dist = float('inf')
return False
return True
matching = 0
while bfs():
for u in U:
if pair_u is None:
if dfs(u):
matching += 1
return matching, pair_u, pair_v
# Példa gráf
graph = {
'A': ,
'B': ,
'C': ,
'D': ,
'E':
}
U =
V =
matching, pair_u, pair_v = hopcroft_karp(graph, U, V)
print(f"Maximális párosítás mérete: {matching}")
print(f"Párosítás: {pair_u}")
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
using namespace std;
const int INF = numeric_limits<int>::max();
bool bfs(vector<vector<int>>& graph, vector<int>& pair_u, vector<int>& pair_v, vector<int>& dist, int U) {
queue<int> q;
for (int u = 0; u < U; ++u) {
if (pair_u == -1) {
dist = 0;
q.push(u);
} else {
dist = INF;
}
}
dist = INF;
while (!q.empty()) {
int u = q.front();
q.pop();
if (dist < dist) {
for (int v : graph) {
if (dist] == INF) {
dist] = dist + 1;
q.push(pair_v);
}
}
}
}
return dist != INF;
}
bool dfs(vector<vector<int>>& graph, vector<int>& pair_u, vector<int>& pair_v, vector<int>& dist, int u) {
if (u != -1) {
for (int v : graph) {
if (dist] == dist + 1) {
if (dfs(graph, pair_u, pair_v, dist, pair_v)) {
pair_v = u;
pair_u = v;
return true;
}
}
}
dist = INF;
return false;
}
return true;
}
int hopcroft_karp(vector<vector<int>>& graph, int U, int V) {
vector<int> pair_u(U, -1), pair_v(V, -1);
vector<int> dist(U + 1);
int matching = 0;
while (bfs(graph, pair_u, pair_v, dist, U)) {
for (int u = 0; u < U; ++u) {
if (pair_u == -1) {
if (dfs(graph, pair_u, pair_v, dist, u)) {
++matching;
}
}
}
}
return matching;
}
int main() {
int U = 5, V = 3;
vector<vector<int>> graph = {
{0, 1}, // A -> 1, 2
{0}, // B -> 1
{1, 2}, // C -> 2, 3
{2}, // D -> 3
{2} // E -> 3
};
int result = hopcroft_karp(graph, U, V);
cout << "Maximális párosítás mérete: " << result << endl;
return 0;
}
A Hopcroft–Karp algoritmus az egyik leghatékonyabb módszer a maximális párosítás megtalálására kétszeresen összefüggő gráfokban. Kiváló teljesítménye miatt széles körben alkalmazzák optimalizációs és hálózati problémákban.