Hungary algorithm

Posted on Edited on In Waline:

I came into contact with this algorithm because I saw a problem called prime significant other. That is to say, you are given a string of numbers, and you choose two numbers to add. If their sum is a prime number, then this pair is called a prime significant other. Then we need to find how many pairs of prime numbers significant other can be found at most in this string of numbers.

The solution to this problem is first to divide the number into two parts, one part is even and the other part is odd, because the addition of two even numbers or the addition of two odd numbers must still be even and cannot be prime.

So the problem becomes to choose one of the even numbers, then choose one of the odd numbers, and see how many pairs are added to the prime number at most. This problem uses the Hungary algorithm.

Hungary algorithm is mainly used to solve some problems related to bipartite graph matching, so let’s first understand bipartite graph.

Bipartite graph

Bipartite graph: Also known as bipartite graph, it is a special model in graph theory. Let G = (V, E) be an undirected graph. If vertices V can be divided into two disjoint subsets (A, B), and the two vertices i and j associated with each edge in the graph belong to these two different sets of vertices (i δ A, j δ B), then the graph G is said to be a bipartite graph.

In simple terms, if all vertices in the graph can be divided into two sets, and the heads and tails of all edges in the graph do not belong to the same set of vertices, but span both sets, then the graph is a bipartite graph.

Let’s take another look at this picture:

This graph doesn’t look like a bipartite graph at first glance, but if we translate its appearance, we will find that it is actually a bipartite graph

Hungary algorithm

Pre-concept

In graph theory, a matching is a set of edges where no two edges have common vertices.

** Maximum match **: The match with the largest number of matched edges among all matches of a graph is called the maximum match of this graph.

** Perfect match **: A graph is a perfect match if all vertices in a match are matching points. A perfect match must be the maximum match (any point of a perfect match has already matched, and adding a new matching edge will definitely conflict with an existing matching edge), but not every graph has a perfect match.

** Alternate Path **: Starting from an unmatched point, passing through non-matching edges, matching edges, and non-matching edges in turn… The path formed is called an alternate path.

** Augmenting Path **: Starting from an unmatched point, take an alternate path. If you pass through another unmatched point (the starting point does not count), this alternate path is called an augmenting path (agumenting path).

** Augmented path properties **:

  1. The path length of P must be odd, and neither the first nor the last edge belongs to M, because the two endpoints belong to two sets and do not match.
  2. P can obtain a larger match M 'after inversion operation.
  3. M is the maximum match of G if and only if there is no augmented path with respect to M.

Basic principle of algorithm

Hungary algorithm: The maximum matching algorithm that uses augmented paths to find bipartite graphs is called the Hungary algorithm. (Hungary mathematician Edmonds proposed it in 1965).

The basic idea: by finding an augmented path, the matching and non-matching edges in the augmented path are exchanged with each other, so that an additional matching edge will be created until the augmented path cannot be found.

One thing to be sure of here is that this process is to find matching and non-matching edges from existing edges, and cannot create new edges

Let’s take the last figure above as an example to explain the process of the entire algorithm:

  1. Starting from the vertex a, follow the alternate path. The first non-matching edge is, reaching the vertex e, and e is the non-matching point, forming an augmented path. Let it be a matching edge, and the vertices a and e are matching vertices.
  2. Starting from vertex b, the first non-matching edge is, reach vertex e, select the matching edge, reach a, select the non-matching edge, g is the non-matching point, find an augmented path, exchange the matching edge in the augmented path with The non-matching edge, that is, b-e, a-g becomes the matching edge, and a-e becomes the non-matching edge.
  3. Starting from the vertex c, the first non-matching edge is, reaches the vertex e, and then proceeds according to the alternate path, reaches the vertex b, cannot continue to move forward, and b is already a matching point, so no new grace path is found
  4. Starting from vertex c, select the second non-matching edge
  5. Starting from vertex d, select non-matching edge, reach vertex g, select matching edge, reach vertex a, select non-matching edge to reach vertex e, select matching edge, reach top b, there is no edge to choose, and no augmentation path is found
  6. Continue from vertex d, select the non-matching edge, find the augmented path, change the edge to the matching edge, and the algorithm ends.

Finally, the result we get is the following figure, and the red line in the following figure is the maximum match obtained by the algorithm:

Algorithm implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//Numbering of vertices and edges starts from 0
//adjacency list storage

struct Edge
{
    int from;
    int to;
    int weight;

    Edge(int f, int t, int w):from(f), to(t), weight(w) {}
};

Vector < int > G [__maxNodes];/* G [i] stores the number of edges starting from vertex i */
vector<Edge> edges;
typedef vector<int>::iterator iterator_t;
int num_nodes;
int num_left;
int num_right;
int num_edges;
Int matching [__maxNodes];/* store the solution result */
int check[__maxNodes];

bool dfs(int u)
{
    for (iterator_t i = G[u].begin(); i != G[u].end(); ++i) { // 对 u 的每个邻接点
        int v = edges[*i].to;
        If (! check [v ]) { // request is not in alternate path
            Check [v] = true;//put an alternate path
            if (matching[v]  -1 || dfs(matching[v])) {
                //If it is an uncovered point, indicating that the alternate path is an augmented path, the path is exchanged and success is returned
                matching[v] = u;
                matching[u] = v;
                return true;
            }
        }
    }
    Return false;//no augmentation path exists, return failed
}

int hungarian()
{
    int ans = 0;
    memset(matching, -1, sizeof(matching));
    for (int u=0; u < num_left; ++u) {
        if (matching[u]  -1) {
            memset(check, 0, sizeof(check));
            if (dfs(u))
                ++ans;
        }
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
queue<int> Q;
int prev[__maxNodes];
int Hungarian()
{
    int ans = 0;
    memset(matching, -1, sizeof(matching));
    memset(check, -1, sizeof(check));
    for (int i=0; i<num_left; ++i) {
        if (matching[i]  -1) {
            while (!Q.empty()) Q.pop();
            Q.push(i);
            Prev [i] = -1;//set i as the starting point of the path
            Bool flag = false;//no augmentation path found
            while (!Q.empty() && !flag) {
                int u = Q.front();
                for (iterator_t ix = G[u].begin(); ix != G[u].end() && !flag; ++ix) {
                    int v = edges[*ix].to;
                    if (check[v] != i) {
                        check[v] = i;
                        Q.push(matching[v]);
                        If (matching [v] > = 0 ) { // this point is a matching point
                            prev[matching[v]] = u;
                        } else {//Find unmatched point, alternate path becomes augmented path
                            flag = true;
                            int d=u, e=v;
                            while (d != -1) {
                                int t = matching[d];
                                matching[d] = e;
                                matching[e] = d;
                                d = prev [d];
                                e = t;
                            }
                        }
                    }
                }
                Q.pop();
            }
            if (matching[i] != -1) ++ans;
        }
    }
    return ans;
}

Reference article: https://www.cxyxiaowu.com/874.html