Adj[v]
means the adjacency list of v
i.e. the list of its adjacent vertices. G1
and G2
are the partitions of the graph. As Hopcroft-Kapr algorithm is for bipartite graphs the solution suggests that the graph is partitioned in two partitions namely G1
and G2
.
Having trouble understanding the Hopcroft-Karp algorithm for maximum matching
-
23-09-2022 - |
Question
Here's the pseudo-code for this algorithm (source):
/*
G = G1 ∪ G2 ∪ {NIL}
where G1 and G2 are partition of graph and NIL is a special null vertex
*/
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
I'm trying to decide what each variable should be. It seems like G1
and G2
in the code start off as the same size as G
, but they're initialized to NIL
. However, in the BFS algorithm, what is Adj[v]
exactly? What would this be analogous to in a typical graph scenario?
La solution
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow