Having trouble understanding the Hopcroft-Karp algorithm for maximum matching

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?

Answer 1

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.