匈牙利算法二分图匹配

匈牙利算法是用来求解二分图的最大匹配的算法。在二分图的匹配中，给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。而二分图的最大匹配则是指所有匹配中包含边数最多的一组匹配，其边数即为最大匹配数。匈牙利算法就是在判断一个图是否是二分图的基础上，求解二分图的最大匹配的算法。
该算法的核心思想是通过不断寻找增广路径来增加匹配的边数。假设已经有一个暂时的匹配关系，当寻找到一个未被匹配的顶点时，就会进一步寻找与该顶点相连的未被匹配的顶点，如果找到了一条增广路径，就可以将匹配的边数增加，直到无法找到增广路径为止。
通过不断寻找增广路径并增加匹配的边数，最终可以得到二分图的最大匹配。这就是匈牙利算法的基本原理。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [二分图的匹配——匈牙利算法](https://blog.csdn.net/HangHug_L/article/details/114106714)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]