Hopkroft-Karp algoritam
U računarstvu, Hopcroft-Karp algoritam je algoritam koji kao ulaz ima bipartitni graf, a kao izlaz daje uparivanje sa maksimalnim brojem grana, najveći skup grana koje nemaju zajedničke krajnje tačke. Vremenska složenost algoritma je  u najgorem slučaju, gde je  skup grana, a  skup čvorova grafa. U slučaju gustih grafova složenost postaje ključna  , a za slučajne grafove je linearna. 
Algoritam su razvili John Hopcroft i Richard Karp (1973 godine). Kao i prethodni algoritmi koji se odnose na uparivanje kao sto su Mađarski algoritam i rad Edmonds-a (1965), Hopcroft-Karp algoritam stalno povećava veličinu delimičnog uparivanja pronalaženjem alternirajućih puteva.
Međutim, umesto da pronalazi samo jedan alternirajući put po iteraciji, algoritam pronalazi maksimalni skup najkraćih alternirajućih puteva. Kao rezultat toga samo  iteracija je potrebno. Isti princip je korišćen pri razvijanju složenijih algoritama za ne-bipartitno uparivanje sa istom asimptotskom složenošću kao i Hopcroft-Karp algoritam.

Alternirajući putevi 
Teme koje ne pripada grani koja se nalazi u skupu delimično uparenih grana , se zove slobodno(neupareno) teme. Osnovni koncept na kom se algoritam zasniva je vezan za alternirajuće puteve, puteve koji počinju i završavaju se neuparenim čvorom, a naizmenično prolaze kroz grane koje su ušle u skup uparenih i kroz one koje nisu. Broj grana na tom putu mora biti neparan, jer pocinje i završava se neuparenim čvorom. Neka je  skup čvorova sa njihovim granama, a  skup uparenih čvorova sa njihovim granama . Alternirajući put  za dato uparivanje  je put između dva neuparena čvora, pri čemu su grane puta  naizmenično u , odnosno . Broj grana koje pripadaju skupu  ima za jedan više nego onih koje pripadaju skupu  . Prema tome, ako iz uparivanja izbacimo sve grane koje pripadaju skupu , a ubacimo sve one koje pripadaju skupu , dobićemo uparivanje sa jednom granom više. Jasno je da ako za dato uparivanje postoji alternirajući put, onda ono nije optimalno. Ispostavlja se da je i obrnuto tvrđenje tačno. Uparivanje je optimalno ako i samo ako nema alternirajući put.

Alternirajući put u problemu uparivanja je blisko povezan sa alternirajućim putevima u problemu maksimalnog protoka. Moguće je transformisati problem bipartitnog uparivanja u primer problema maksimalnog protoka, tako sto alternirajući putevi u problemu uparivanja postanu alternirajući putevi u problemu protoka . U stvari, generalizacija tehnike koja se koristi u Hopcroft-Karp algoritmu je poznata kao Dinic algoritam.
 Input: Bipartite graph 
 Output: Matching 
 
 repeat
  maksimalan skup čvorova koji ne pripadaju najkraćim alternirajućim putevima
 
 until

Algoritam 
Neka  i  budu dva skupa u bipartitnom grafu , i neka se uparivanje iz  u  u bilo koje vreme može predstaviti kao skup .
Algoritam se radi u fazama. Svaka faza se sastoji od sledećih koraka. 
 BFS pretraga deli particije čvorova grafa na slojeve. Slobodni čvorovi iz  se koriste kao polazna temena za pretragu, i formira se prvi sloj particije. Tokom prvog nivoa pretrage možemo proći samo kroz neuparene ivice (pošto slobodni čvorovi iz U po definiciji ne pripadaju uparenim granama), u narednim nivoima pretrage, prolazićemo naizmenično kroz uparene i neuparene grane. Prilikom traženja susednih čvorova počev od čvorova iz  , možemo proći jedino kroz neuparene grane, dok iz čvorova koji pripadaju  možemo proći samo kroz uparene grane. Pretraga se završava na prvom sloju  gde su pronađeni jedan ili više slobodnih čvorova iz .
 Svi slobodni čvorovi iz  na sloju  se nalaze u skupu . Cvor  se nalazi u  ako i samo ako je kraj najkraćeg alternirajućeg puta.
 Algoritam pronalazi maksimalan skup čvorova koji ne pripadaju alternirajućim putevima dužine . Ovaj skup može biti napravljen DFS pretragom iz  do slobodnih čvorova iz , korišćenjem BFS slojeva kao vodič, DFS pretragom možemo proći kroz grane koje vode do neposećenih čvorova na prethodnom sloju, a DFS stablo sadrži naizmenično uparene i neuparene grane. Čim je pronađen alternirajući put koji sadrži jedan od čvorova iz , DFS pretraga se nastavlja iz sledećeg početnog čvora.
 Svaki od puteva koji je pronađen na ovaj način se koristi za uvećanje .
Algoritam se završava kada BFS pretragom nije pronađen ni jedan alternirajući put.

Analiza 
Svaka faza se sastoji od jedne BFS pretrage i jedne DFS pretrage. Dakle, vremenska složenost jedne faze je linearna. Složenost prvih  faza u grafu sa  čvorova i  grana je  .
Može se pokazati da svaka faza povećava dužinu najkraćeg alternirajućeg puta za najmanje jedan, faza pronalazi maksimalan skup alternirajućih puteva zadate dužine, tako da ostali alternirajući putevi moraju biti duži. Zato, kada se početnih  faza algoritma završi, preostali najkraći alternirajući put ima najmanje  grana .Međutim, simetrična razlika eventualno optimalnog uparivanja i delimičnog uparivanja  tokom prvih faza formira kolekciju čvorova i grana koje su disjunktne alternirajućim putevima i naizmeničnim ciklusima. Ukoliko je svaki put u kolekciji bar dužine  , može biti najvise  puteva u kolekciji, i velicina optimalnog uparivanja se može razlikovati od velicine  za najvise  grana. Pošto svaka faza algoritma povećava veličinu uparivanja za barem jedan, može postojati najviše  dodatnih faza pre nego što se algoritam završi.
Pošto algoritam ima najviše  faza, njegova složenost je u najgorem slučaju  .
U mnogim slučajevima,algoritam ima bolju vremensku složenost. Na primer, u prosečnom slučaju, za slučajne oskudne bipartitne grafove, Bast et al. Je pokazao da sa velikom verovatnoćom sva neoptimalna uparivanja imaju alternirajuće puteve logaritamske dužine. Kao posledica, za ove grafove, Hopcroft-Karp algoritam ima  faza, a ukupna složenost je  .

Ne-bipartitni grafovi 

Ista ideja o pronalaženju maksimalnog skupa najkraćih alternirajućih puteva se koristi i za pronalaženje maksimalnog uparivanja u ne-bipartitnim grafovima, i iz istih razloga, algoritam baziran na ovoj ideji ima  faza. Međutim, za ne-bipartitne grafove je teže pronaći alternirajuće puteve u svakoj fazi. Nadovezujući se na rad nekoliko sporijih prethodnika, Micali i Vazirani (1980) su pokazali kako se može implementirati pojedinačna faza sa linearnom složenošću, što je rezultovalo algoritmom koji ima istu vremensku složenost kao Hopcroft-Karp algoritam za bipartitne grafove. Micali-Vazirani tehnika je kompleksna i njeni autori nemaju kompletan dokaz, alternativne metode za ovaj problem su kasnije opisali drugi autori.

Pseudokod 
 
 1 //G = G1 ∪ G2 ∪ {NIL}
 2 //G1 i G2 su particije grafa a NIL specijalni null čvor
 3 
 4 
 5    function BFS ()
 6    for v in G1
 7        if Pair_G1[v] == NIL
 8            Dist[v] = 0
 9           Enqueue(Q,v)
 10       else
 11           Dist[v] = ∞
 12    Dist[NIL] = ∞
 13    while Empty(Q) == false
 14        v = Dequeue(Q)
 15        if Dist[v] < Dist[NIL] 
 16            for each u in Adj[v]
 17                if Dist[ Pair_G2[u] ] == ∞
 18                    Dist[ Pair_G2[u] ] = Dist[v] + 1
 19                    Enqueue(Q,Pair_G2[u])
 20    return Dist[NIL] != ∞

 1    function DFS (v)
 2    if v != NIL
 3        for each u in Adj[v]
 4            if Dist[ Pair_G2[u] ] == Dist[v] + 1
 5                if DFS(Pair_G2[u]) == true
 6                    Pair_G2[u] = v
 7                    Pair_G1[v] = u
 8                    return true
 9        Dist[v] = ∞
 10           return false
 11   return true

 1    function Hopcroft-Karp
 2        for each v in G
 3            Pair_G1[v] = NIL
 4            Pair_G2[v] = NIL
 5        matching = 0
 6        while BFS() == true
 7            for each v in G1
 8                if Pair_G1[v] == NIL
 9                    if DFS(v) == true
 10                       matching = matching + 1
 11    return matching

Reference 

Grafovski algoritmi
U računarstvu , Hopcroft-Karp algoritam je algoritam koji kao ulaz ima bipartitni graf , a kao izlaz daje uparivanje sa maksimalnim brojem grana , najveći skup grana koje nemaju zajedničke krajnje tačke . Vremenska složenost algoritma je u najgorem slučaju , gde je skup grana , a skup čvorova grafa . U slučaju gustih grafova složenost postaje ključna , a za slučajne grafove je linearna . Algoritam su razvili John Hopcroft i Richard Karpgodine ) . Kao i prethodni algoritmi koji se odnose na uparivanje kao sto su Mađarski algoritam i rad Edmonds-a Hopcroft-Karp algoritam stalno povećava veličinu delimičnog uparivanja pronalaženjem alternirajućih puteva . Međutim , umesto da pronalazi samo jedan alternirajući put po iteraciji , algoritam pronalazi maksimalni skup najkraćih alternirajućih puteva . Kao rezultat toga samo iteracija je potrebno . Isti princip je korišćen pri razvijanju složenijih algoritama za ne-bipartitno uparivanje sa istom asimptotskom složenošću kao i Hopcroft-Karp algoritam . Alternirajući putevi Teme koje ne pripada grani koja se nalazi u skupu delimično uparenih grana , se zove slobodno( neupareno ) teme . Osnovni koncept na kom se algoritam zasniva je vezan za alternirajuće puteve , puteve koji počinju i završavaju se neuparenim čvorom , a naizmenično prolaze kroz grane koje su ušle u skup uparenih i kroz one koje nisu . Broj grana na tom putu mora biti neparan , jer pocinje i završava se neuparenim čvorom . Neka je skup čvorova sa njihovim granama , a skup uparenih čvorova sa njihovim granama \ . Alternirajući put za dato uparivanje je put između dva neuparena čvora , pri čemu su grane puta naizmenično u , odnosno \ . Broj grana koje pripadaju skupu ima za jedan više nego onih koje pripadaju skupu \ . Prema tome , ako iz uparivanja izbacimo sve grane koje pripadaju skupu , a ubacimo sve one koje pripadaju skupu , dobićemo uparivanje sa jednom granom više . Jasno je da ako za dato uparivanje postoji alternirajući put , onda ono nije optimalno . Ispostavlja se da je i obrnuto tvrđenje tačno . Uparivanje je optimalno ako i samo ako nema alternirajući put . Alternirajući put u problemu uparivanja je blisko povezan sa alternirajućim putevima u problemu maksimalnog protoka . Moguće je transformisati problem bipartitnog uparivanja u primer problema maksimalnog protoka , tako sto alternirajući putevi u problemu uparivanja postanu alternirajući putevi u problemu protoka \ . U stvari , generalizacija tehnike koja se koristi u Hopcroft-Karp algoritmu je poznata kao Dinic algoritam . Input : Bipartite graph Output : Matching repeat maksimalan skup čvorova koji ne pripadaju najkraćim alternirajućim putevima until Algoritam Neka i budu dva skupa u bipartitnom grafu , i neka se uparivanje iz u u bilo koje vreme može predstaviti kao skup \ . Algoritam se radi u fazama . Svaka faza se sastoji od sledećih koraka . BFS pretraga deli particije čvorova grafa na slojeve . Slobodni čvorovi iz se koriste kao polazna temena za pretragu , i formira se prvi sloj particije . Tokom prvog nivoa pretrage možemo proći samo kroz neuparene ivice ( pošto slobodni čvorovi iz U po definiciji ne pripadaju uparenim granama ) , u narednim nivoima pretrage , prolazićemo naizmenično kroz uparene i neuparene grane . Prilikom traženja susednih čvorova počev od čvorova iz , možemo proći jedino kroz neuparene grane , dok iz čvorova koji pripadaju možemo proći samo kroz uparene grane . Pretraga se završava na prvom sloju gde su pronađeni jedan ili više slobodnih čvorova iz \ . Svi slobodni čvorovi iz na sloju se nalaze u skupu \ . Cvor se nalazi u ako i samo ako je kraj najkraćeg alternirajućeg puta . Algoritam pronalazi maksimalan skup čvorova koji ne pripadaju alternirajućim putevima dužine \ . Ovaj skup može biti napravljen DFS pretragom iz do slobodnih čvorova iz , korišćenjem BFS slojeva kao vodič , DFS pretragom možemo proći kroz grane koje vode do neposećenih čvorova na prethodnom sloju , a DFS stablo sadrži naizmenično uparene i neuparene grane . Čim je pronađen alternirajući put koji sadrži jedan od čvorova iz , DFS pretraga se nastavlja iz sledećeg početnog čvora . Svaki od puteva koji je pronađen na ovaj način se koristi za uvećanje \ . Algoritam se završava kada BFS pretragom nije pronađen ni jedan alternirajući put . Analiza Svaka faza se sastoji od jedne BFS pretrage i jedne DFS pretrage . Dakle , vremenska složenost jedne faze je linearna . Složenost prvih faza u grafu sa čvorova i grana je \ . Može se pokazati da svaka faza povećava dužinu najkraćeg alternirajućeg puta za najmanje jedan , faza pronalazi maksimalan skup alternirajućih puteva zadate dužine , tako da ostali alternirajući putevi moraju biti duži . Zato , kada se početnih faza algoritma završi , preostali najkraći alternirajući put ima najmanje grana \ .Međutim , simetrična razlika eventualno optimalnog uparivanja i delimičnog uparivanja tokom prvih faza formira kolekciju čvorova i grana koje su disjunktne alternirajućim putevima i naizmeničnim ciklusima . Ukoliko je svaki put u kolekciji bar dužine , može biti najvise puteva u kolekciji , i velicina optimalnog uparivanja se može razlikovati od velicine za najvise grana . Pošto svaka faza algoritma povećava veličinu uparivanja za barem jedan , može postojati najviše dodatnih faza pre nego što se algoritam završi . Pošto algoritam ima najviše faza , njegova složenost je u najgorem slučaju \ . U mnogim slučajevima ,algoritam ima bolju vremensku složenost . Na primer , u prosečnom slučaju , za slučajne oskudne bipartitne grafove , Bast et al . Je pokazao da sa velikom verovatnoćom sva neoptimalna uparivanja imaju alternirajuće puteve logaritamske dužine . Kao posledica , za ove grafove , Hopcroft-Karp algoritam ima faza , a ukupna složenost je \ . Ne-bipartitni grafovi Ista ideja o pronalaženju maksimalnog skupa najkraćih alternirajućih puteva se koristi i za pronalaženje maksimalnog uparivanja u ne-bipartitnim grafovima , i iz istih razloga , algoritam baziran na ovoj ideji ima faza . Međutim , za ne-bipartitne grafove je teže pronaći alternirajuće puteve u svakoj fazi . Nadovezujući se na rad nekoliko sporijih prethodnika , Micali i Vaziranisu pokazali kako se može implementirati pojedinačna faza sa linearnom složenošću , što je rezultovalo algoritmom koji ima istu vremensku složenost kao Hopcroft-Karp algoritam za bipartitne grafove . Micali-Vazirani tehnika je kompleksna i njeni autori nemaju kompletan dokaz , alternativne metode za ovaj problem su kasnije opisali drugi autori . Pseudokod / /G = G1 ∪ G2 ∪ { NIL } / / G1 i G2 su particije grafa a NIL specijalni null čvor function BFS ( ) for v in G1 if Pair_G1[ v ] == NIL Dist[ v ] = 0 Enqueue( Q,v ) else Dist[ v ] = ∞ Dist[ NIL ] = ∞ while Empty( Q ) == false v = Dequeue( Q ) if Dist[ v ] < Dist[ NIL ] for each u in Adj[ v ] if Dist [ Pair_G2[ u ] ] == ∞ Dist [ Pair_G2[ u ] ] = Dist[ v ] + 1 Enqueue( Q,Pair_G2[ u ] ) return Dist[ NIL ] != ∞ function DFS ( v ) if v != NIL for each u in Adj[ v ] if Dist [ Pair_G2[ u ] ] == Dist[ v ] + 1 if DFS( Pair_G2[ u ] ) == true Pair_G2[ u ] = v Pair_G1[ v ] = u return true Dist[ v ] = ∞ return false return true function Hopcroft-Karp for each v in G Pair_G1[ v ] = NIL Pair_G2[ v ] = NIL matching = 0 while BFS ( ) == true for each v in G1 if Pair_G1[ v ] == NIL if DFS( v ) == true matching = matching + 1 return matching Reference Grafovski algoritmi