Hungray匈牙利算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Hungray匈牙利算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1895字，纯文字阅读大概需要3分钟。

内容图文

一、解决问题

在二分图中，使得两两匹配对数最多。

 

例如：如果虚线表示暧昧关系，则男女能配多少对

二、思想

匈牙利算法的思想就是让。二分图右侧节点与之匹配的左侧节点如果能让出来，则移动左侧节点的匹配。否则寻找本次左侧节点的新匹配。

尽可能多的去让出来。例如：

• 男1与女a匹配。
• 男2与女a有暧昧，但是男1让不出来。因此男2与女c匹配
• 男3与女b匹配
• 男4无人匹配
• 男5与女b匹配，但是b让不出来，则5与d匹配

 

 

三、Code

 1 package algorithm;
 2 
 3 import java.util.Arrays;
 4 
 5 public class HungaryTest {
 6 
 7     //妹子数目
 8     private static int m = 4;
 9     //男数目
10     private static int n = 5;
11 
12     //男女是否暧昧, 即图是否链接
13     private static boolean[][] line = new boolean[n][m];
14 
15     // 本次妹子是否匹配
16     private static boolean[] used;
17 
18     //妹子属于谁
19     private static int[] girl = new int[m];
20 
21     //最终匹配个数
22     private static int all = 0;
23 
24     public static void init() {
25         Arrays.fill(girl, -1);
26         line[0][0] = true;
27         line[1][0] = true;
28         line[1][2] = true;
29         line[2][1] = true;
30         line[3][1] = true;
31         line[4][1] = true;
32         line[4][3] = true;
33     }
34 
35     private static boolean find(int x) {
36         for (int i = 0; i < m; i++) {
37             if (line[x][i] && !used[i]) {
38                 used[i] = true;
39                 if (girl[i] == -1 || find(girl[i])) {
40                     girl[i] = x;
41                     return true;
42                 }
43             }
44         }
45         return false;
46     }
47 
48     public static void main(String[] args) {
49         init();
50         for (int i = 0; i < n; i++) {
51             used = new boolean[m];
52             find(i);
53         }
54 
55         for(int i = 0; i < m; i++){
56             if(girl[i] != -1) System.out.println("girl " + i + " boy " + girl[i]);
57         }
58     }
59 }

 

结果：

内容总结

以上是互联网集市为您收集整理的Hungray匈牙利算法全部内容，希望文章能够帮你解决Hungray匈牙利算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---