Hopcroft-Karp-algoritmus
Kiejtés
- IPA: [ ˈhopt͡sroftkɒrpɒlɡoritmuʃ]
Főnév
Hopcroft–Karp algoritmus
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.
Alapfogalmak
- Kétszeresen összefüggő gráf:
- Egy gráf ( G = (V, E) ), amely két diszjunkt halmazból áll: ( U ) és ( V ). Az élek csak ( U )-ból ( V )-be vezethetnek (és fordítva).
- Párosítás (Matching):
- A gráf egy éleinek olyan részhalmaza, amelyben egyetlen csúcs sem szerepel egynél többször.
- Maximális párosítás:
- Egy párosítás, amely a lehető legtöbb élből áll.
- Növelő út (Augmenting Path):
- Olyan út, amely felváltva tartalmaz párosításban szereplő és nem szereplő éleket, és az út két végpontja nem tartozik a párosításhoz.
Algoritmus működése
A Hopcroft–Karp algoritmus iteratív módon működik:
- Szélességi keresés (BFS):
- Találd meg az összes legrövidebb növelő utat a párosítás bővítéséhez.
- Mélységi keresés (DFS):
- Az összes lehetséges növelő utat dolgozd fel párhuzamosan.
- Párosítás bővítése:
- A növelő utak segítségével frissítsd a párosítást.
Az algoritmus addig ismétli ezeket a lépéseket, amíg nem talál növelő utat.
Időbonyolultság
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.
Algoritmus Pszeudokód
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
Példa Pythonban
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[u] is None:
dist[u] = 0
queue.append(u)
else:
dist[u] = float('inf')
dist[None] = float('inf')
while queue:
u = queue.popleft()
if dist[u] < dist[None]:
for v in graph[u]:
if dist[pair_v[v]] == float('inf'):
dist[pair_v[v]] = dist[u] + 1
queue.append(pair_v[v])
return dist[None] != float('inf')
def dfs(u):
if u is not None:
for v in graph[u]:
if dist[pair_v[v]] == dist[u] + 1:
if dfs(pair_v[v]):
pair_v[v] = u
pair_u[u] = v
return True
dist[u] = float('inf')
return False
return True
matching = 0
while bfs():
for u in U:
if pair_u[u] is None:
if dfs(u):
matching += 1
return matching, pair_u, pair_v
# Példa gráf
graph = {
'A': ['1', '2'],
'B': ['1'],
'C': ['2', '3'],
'D': ['3'],
'E': ['3']
}
U = ['A', 'B', 'C', 'D', 'E']
V = ['1', '2', '3']
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}")
Példa C++-ban
#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[u] == -1) {
dist[u] = 0;
q.push(u);
} else {
dist[u] = INF;
}
}
dist[-1] = INF;
while (!q.empty()) {
int u = q.front();
q.pop();
if (dist[u] < dist[-1]) {
for (int v : graph[u]) {
if (dist[pair_v[v]] == INF) {
dist[pair_v[v]] = dist[u] + 1;
q.push(pair_v[v]);
}
}
}
}
return dist[-1] != 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[u]) {
if (dist[pair_v[v]] == dist[u] + 1) {
if (dfs(graph, pair_u, pair_v, dist, pair_v[v])) {
pair_v[v] = u;
pair_u[u] = v;
return true;
}
}
}
dist[u] = 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[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;
}
Előnyök
- Hatékony futási idő:
- (O(E )), ami gyorsabb, mint az alapvető párosítási algoritmusok.
- Könnyen implementálható:
- Bár komplexebb, a BFS és DFS kombinációja jól érthető.
Hátrányok
- Speciális gráfok:
- Kizárólag kétszeresen összefüggő gráfokra alkalmazható.
- Memóriaköltség:
- Nagy gráfok esetén a memóriahasználat megnövekedhet.
Alkalmazások
- Munkaerő-kiosztás:
- Feladatok és munkavállalók hatékony párosítása.
- Házassági probléma:
- Stabil párosítások keresése.
- Hálózatok:
- Adatátvitel és útvonal-optimalizáció kétszeresen összefüggő gráfokban.
Összegzés
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.
- Hopcroft-Karp-algoritmus - Értelmező szótár (MEK)
- Hopcroft-Karp-algoritmus - Etimológiai szótár (UMIL)
- Hopcroft-Karp-algoritmus - Szótár.net (hu-hu)
- Hopcroft-Karp-algoritmus - DeepL (hu-de)
- Hopcroft-Karp-algoritmus - Яндекс (hu-ru)
- Hopcroft-Karp-algoritmus - Google (hu-en)
- Hopcroft-Karp-algoritmus - Helyesírási szótár (MTA)
- Hopcroft-Karp-algoritmus - Wikidata
- Hopcroft-Karp-algoritmus - Wikipédia (magyar)