匈牙利算法的一个重要概念是增广路径, 具体思路是对于图的每个顶点都寻找其增广路径, 然后将其加入匹配顶点当中, 而对于每个顶点 A 寻找增广路径的过程中, 如果另一个顶点 B 和顶点 A 有连接且在此轮循环中没有被访问过, 则进行下一步处理: 如果顶点 B 没有匹配的顶点或者虽然有匹配的顶点但是能找出另一个匹配的顶点 C 而把当前匹配的顶点让给顶点 A, 则把顶点 A 和顶点 C 匹配, 而顶点 B 也在递归的过程中更改了匹配顶点, 如此下去关于匈牙利算法还有一个重要的定理: 如果从一个顶点 A 出发, 没有找到增广路径, 那么无论再从别的点出发找到多少增广路径来改变现在的匹配, 从 A 出发都永远找不到增广路径所以后面顶点的处理对前面顶点的处理没有影响具体代码如下:
- public class Hungary {int[][] graph; // 需要计算的图的邻接矩阵, 注意每个顶点和它自己的连接被设置成了 0 另外 graph 需要是 n*n 的矩阵
- int[] match; // 记录每个顶点的匹配顶点假如 match[0]=1, 就是说顶点 0 和顶点 1 已经匹配
- int len; // 图的顶点的个数
- boolean[] used; // 在从每个顶点搜索其增广路径的循环中, 记录每个顶点是否已经被访问过
- public Hungary(int[][] graph) {
- this.graph = graph;
- len = graph.length;
- used = new boolean[len];
- match = new int[len];
- for (int i = 0; i < len; i++) {
- match[i] = -1;
- used[i] = false;
- }
- }
- // 寻找顶点 x 的增广路径如果能够寻找到则返回 true, 否则返回 false
- // 匈牙利算法一个重要的定理: 如果从一个顶点 A 出发, 没有找到增广路径, 那么无论再从别的点出发找到多少增广路径来改变现在的匹配, 从 A 出发都永远找不到增广路径
- boolean findAugmentPath(int x) {
- for (int i = 0; i < len; i++) {
- if (graph[x][i] == 1) { // 顶点 x 和顶点 i 之间有连接需要注意的一点是我们在输入需要计算的图的邻接矩阵的时候把对角线上的元素设置为 0
- if (!used[i]) { // 如果顶点 i 还未访问
- used[i] = true;
- // 如果顶点 i 还未匹配, 或者与顶点 i 匹配的那个顶点可以换个顶点匹配 (也就是说可以把顶点 i 让给当前顶点 x), 则把顶点 x 和顶点 i 为对方的匹配顶点
- // 由于上一步已经将顶点 i 设置成 used, 所以 findAugmentPath(match[i]) 不会再考虑顶点 i 了
- if (match[i] == -1 || findAugmentPath(match[i])) {
- match[x] = i;
- match[i] = x;
- System.out.println(x + "------>" + i);
- return true;
- }
- }
- }
- }
- return false;
- }
- void search() {
- // 对于每个顶点都循环处理
- for (int i = 0; i < len; i++) {
- if (match[i] == -1) { // 如果当前顶点已经有匹配的顶点了, 就略过此顶点
- clearUsed(); // 新的一轮搜索, 把 used 数组设置成 false
- System.out.println("开始匹配顶点" + i);
- findAugmentPath(i);
- }
- }
- System.out.println();
- System.out.println();
- System.out.println();
- for (int i = 0; i < len; i++) {
- System.out.println(i + "------>" + match[i]);
- }
- }
- void clearUsed() {
- for (int i = 0; i < len; i++) {
- used[i] = false;
- }
- }
- public static void main(String[] args) {
- int[][] graph = {{0, 0, 0, 0, 1, 0, 1, 0},
- {0, 0, 0, 0, 1, 0, 0, 0},
- {0, 0, 0, 0, 1, 1, 0, 0},
- {0, 0, 0, 0, 0, 0, 1, 1},
- {1, 1, 1, 0, 0, 0, 0, 0},
- {0, 0, 1, 0, 0, 0, 0, 0},
- {1, 0, 0, 1, 0, 0, 0, 0},
- {0, 0, 0, 1, 0, 0, 0, 0}};
- new Hungary(graph).search();
- }
- }
来源: http://blog.csdn.net/Q_AN1314/article/details/79488562