Shulou(Shulou.com)05/31 Report--

Most people do not understand the knowledge points of this article "how to achieve the Hungarian algorithm in C++", so the editor summarizes the following contents to you. The content is detailed, the steps are clear, and it has a certain reference value. I hope you can get something after reading this article. Let's take a look at this "how C++ realizes the Hungarian algorithm" article.

I. introduction of Hungarian algorithm

The Hungarian algorithm (Hungarian algorithm) is mainly used to solve some problems related to bipartite graph matching, so let's take a look at bipartite graphs first.

Bipartite graph (Bipartite graph) is a special kind of graph, which can be divided into two parts, and the vertices in each part are not connected to each other. The following picture is a typical bipartite diagram.

As you can see, in the above bipartite graph, the endpoints of each edge are in the point sets X and Y, respectively. The Hungarian algorithm is mainly used to solve two problems: the maximum matching number and the minimum point covering number of bipartite graphs.

This is too abstract to say, let's start with practical problems.

II. Maximum matching problem

After reading the above, I believe the reader will feel in the clouds: what is this? What's the use? So let's tamper with this dichotomy a little bit and look like this:

Now Boys and Girls are two point sets, in which the points are boys and girls, indicating that there is an "ambiguous relationship" between them. The biggest matching problem is that if you are a matchmaker and you can match any man and woman who have an affair, how many couples can you make? (mathematical expression: how many edges without common endpoints can be found in a bipartite graph)

Now let's see how the Hungarian algorithm works:

Let's start with B1 (equality between men and women, and it's okay from the girls' side). He has an affair with G2, so let's connect him to G2 for the time being. (note that you are only imagining it on paper as a matchmaker, and you have no real action. The arrangements at this time are temporary).

Let's see that B2 also likes G2. At this time, G2 already has a "famous flower" (although it is only what we imagined), so what should we do? Let's go back and see if the boyfriend who is currently arranged in G2 is B1. Is there any other option? Yes, G4 G4 has not been arranged yet, so let's arrange G4 for B1.

Then B3, B3 and G1. As for B4, he is only in love with G4 is currently equipped with B1. B1 can also choose G2 in addition to G4, but if B1 chooses the original B2 of G2MagneG2, there will be no choice. We made a big circle and found that B4 can only be doomed to be single, poor. (in fact, G3, which has never been considered, is even more pitiful.)

This is the flow of the Hungarian algorithm. As for the implementation, let's take a look at the code:

Int M, N; / / M, N represent the number of elements in the left and right sets int Map [MAXM] [MAXN]; / / adjacency matrix store int p [MAXN]; / / record the left element corresponding to the current right element bool vis [MAXN]; / / record whether the right element has been accessed bool match (int I) {for (int j = 1; j)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.