学习匈牙利算法的基础相关概念，顺便解决实际遇到的一个整体最优分配问题。

一、图

图是由“顶点”和“边”所组成的集合，通常用G=(V,E)来表示。

其中V是所有顶点所组成的集合，而E代表所有边所组成的集合。

图的种类有两种

无向图。以(V1,V2)表示其边。
有向图。以<V1,V2>表示其边。

1.1 无向图

无向图的基础概念以书中的截图展示如下。

1.2 有向图

有向图的基础概念以书中的截图展示如下。

1.3 图的数据表示法

图的常见表示法如下

邻接矩阵
- 使用一个二维矩阵表示图，A[i][j]表示从顶点i到顶点j的边。
- 优点：查找两顶点是否有边时效率高，适用于稠密图。
- 缺点：空间复杂度高。需要O(n^2)的存储空间。对于稀疏图来说，非常浪费空间。
邻接表
- 使用一个链表数组进行存储，每个顶点对应一个链表，链表中存储与该顶点直接相连的其他顶点。
- 优点：添加边和遍历相连顶点更高效；节省空间，特别适用于稀疏图。
- 缺点：查找是否有边时效率不如邻接矩阵。

这些表示方法根据不同场景和需求有各自的优缺点，具体选用哪种表示方法取决于图的规模、边的数量和使用场景。

二、匈牙利算法与KM算法

2.1 相关概念

最大匹配

一个图G=(V,E)，其中V是顶点集，E是边集。

如果可以将顶点集V划分为两个不相交的集合V1和V2，并且满足图中的每条边都只连接V1和V2中的一个顶点。这种图G就叫做二分图。

设G为二分图，若在G的子图M中，任意两条边都没有公共顶点，那么称M为二分图G中的一组匹配。对应的点，叫做匹配点；对应的边，叫做匹配边。

在二分图中，包含边数最多的一组匹配，称为二分图的最大匹配。

交替路径与增广路径

从一个非匹配点出发，依次经过非匹配边、匹配边、非匹配边……形成的路径叫做交替路径。

从一个非匹配点出发，走交替路径，即依次经过非匹配边、匹配边、非匹配边……若能到达另一个非匹配点，则这条路径称为增广路径。

如下图所示，1、2、4、5均为匹配点，(1,5)、(2,4)为匹配边。

3->5->1->4->2->7，这条路径就是一条增广路径。观察增广路径，会发现非匹配边比匹配边多了一条。

此时将原匹配边删除，保留非匹配边作为匹配边，就叫做增广路径取反。

匈牙利算法

通过不停地寻找增广路径来增加匹配边，找不到增广路径时，就达到了最大匹配。这个就叫做匈牙利算法。

匈牙利算法有两种实现方式

DFS(Depth First Search，即深度优先搜索)
BFS(Breadth First Search，即广度优先搜索)

完全匹配与完美匹配

在二分图中，若存在一个匹配，一侧的每一个顶点，都与另一侧的一个顶点匹配，则称此匹配为二分图的完全匹配。

在二分图中，若存在一个匹配，其左侧和右侧顶点数相等且均为N个顶点，若最大匹配也为N条边，则称此匹配为二分图的完美匹配。

完全匹配与完美匹配的对比

特性	完全匹配	完美匹配
覆盖范围	部分顶点可能未被匹配	所有顶点都被匹配
顶点数要求	——	偶数
两者关系	——	完美匹配一定是完全匹配
场景示例	相亲大会，将女性全都分配出去，但允许存在男性光棍	相亲大会，男女一样多，全部配对

完全匹配与最大匹配的对比

特性	完全匹配	最大匹配
目标	某侧顶点全匹配	匹配边数最多
两者关系	完全匹配一定是最大匹配	最大匹配不一定是完全匹配

二分图中，边权和最大的完美匹配，叫做二分图的最大权完美匹配。

KM算法

2.2 实现-最大匹配

实际场景：正在举办相亲大会，各个男女都有多个好感对象。通过算法让相亲大会能产生最多的情侣配对。

示例代码：

public class MaximumMatching {

    /**
     * 获取二分图的最大匹配数
     *
     * @param graph 邻接矩阵表示的二分图，graph[u][v] == 1 表示从左边集合的顶点 u 到右边集合的顶点 v 存在一条边
     * @return 最大匹配数
     */
    public static int getMaximumMatching(int[][] graph) {
        int n = graph.length; // 左集合的顶点数
        int m = graph[0].length; // 右集合的顶点数

        // 匹配对：match[v] 表示右集合顶点 v 当前匹配的左集合顶点
        int[] match = new int[m];
        for (int i = 0; i < m; i++) {
            match[i] = -1; // 初始化为 -1，表示未匹配
        }

        int maxMatching = 0; // 最大匹配数
        for (int u = 0; u < n; u++) {
            // 用于标记右集合顶点是否在当前 DFS 中访问过
            boolean[] visited = new boolean[m];
            if (dfs(graph, u, visited, match)) {
                maxMatching++;
            }
        }

        return maxMatching;
    }

    /**
     * 深度优先搜索，尝试为左集合顶点 u 寻找增广路径
     *
     * @param graph   邻接矩阵
     * @param u       左集合的当前顶点
     * @param visited 标记右集合顶点是否已访问
     * @param match   匹配对
     * @return 是否找到增广路径
     */
    private static boolean dfs(int[][] graph, int u, boolean[] visited, int[] match) {
        for (int v = 0; v < graph[u].length; v++) {
            if (graph[u][v] == 1 && !visited[v]) {
                visited[v] = true; // 标记 v 为已访问
                // 如果 v 未匹配，或者 v 的当前匹配点可以重新匹配
                if (match[v] == -1 || dfs(graph, match[v], visited, match)) {
                    match[v] = u; // 将 v 匹配给 u
                    return true;
                }
            }
        }
        return false;
    }
}