匈牙利算法

二分图最大匹配算法(Hungarian Algorithm)

这个算法的操作与原理及其数学证明都很繁与困难,理解如何应用以及应用场景即可


一、概论介绍

  • 最大匹配:在二分图中最多能找到多少条没有公共端点的边(配对)

示例
image

不难发现,这个二分图的最大匹配是如下(不唯一)

但是最大匹配数为 4

image

  • 下面我们严谨的表述一遍最大匹配

在 G 的一个子图 M 中,M 的边集中的任意两条边都不依附于同一个顶点,则称 M 是一个匹配

选择这样的边数最大的子集称为图的最大匹配问题,最大匹配的边数称为最大匹配数

如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。

  • 下面介绍两个基本概念(交替路与增广路)

交替路: 从一个未匹配点出发,依次经过非匹配边、匹配边、非匹配边...形成的路径叫交替路

增广路:从一个未匹配点出发,走交替路,如果途径另一个未匹配点(出发的点不算),则这条交替路称为增广路(agumenting path)

二、算法原理

原理:增广路的性质,增广路中的匹配边总是比未匹配边多一条,所以如果我们放弃一条增广路中的匹配边,选取未匹配边作为匹配边,则匹配的数量就会增加

匈牙利算法就是在不断寻找增广路,如果找不到增广路,就说明达到了最大匹配

可以数学证明这种算法得到的解即为最大匹配数

这个算法的严谨数学证明是比较难的,这里就不加以赘述了,感兴趣可以结合上学期离散数学的图论知识证明,不需要使用任何定理

举例使用:

起始状态尚未匹配,全部都是非匹配边和非匹配点

image

任意选中 x1 与任意其中一个点 y1 匹配

image

选中第二个点 x2,x1 没有已霸占 x2 的任何一个对象,故 x2 与任意一个 y2 匹配即可

image

选中 x3,发现 x3 的第一对象 y1 已经被 x1 占了,于是找出 x3 出发的的交错路径 x3-y1-x1-y4,把交错路中已在匹配上的边 x1-y1 从匹配中去掉,反而匹配剩余的边 x3-y1,x1-y4,这就是增广路技巧

具体操作中将使用 DFS 深度优先搜索

接着选择 x4,发现没有增广路,于是只好选择 y3

image

接着选择 x5,发现有增广路:x5-y4-x1-y1-x3-y7,于是变成如下

image

最后选择 x6,x6 无对象可选,而且没有增广路,于是 x6 没法匹配

此结果即为最大匹配

Code-hxw

typedef struct tagMaxMatch{
    int edge[COUNT][COUNT];
    bool on_path[COUNT];
    int path[COUNT];
    int max_match;
}GRAPH_MATCH;
void outputRes(int *path){
    for (int i = 0 ; i<COUNT; i++) {
        printf("%d****%d\n",i,*(path+i));  
    }
}
void clearOnPathSign(GRAPH_MATCH *match){
    for (int j = 0 ; j < COUNT ; j++) {
        match->on_path[j] = false;
    }
}
//dfs算法
bool FindAugPath(GRAPH_MATCH *match , int xi){
  
    for (int yj = 0 ; yj < COUNT; yj++) {
        if ( match->edge[xi][yj] == 1 && !match->on_path[yj]) { 
             match->on_path[yj] = true;
            if (match->path[yj] == -1 || FindAugPath(match,match->path[yj])) { 
                  match->path[yj] = xi; 
                  return true;
            }
        }
    }
    return false;
}
void Hungary_match(GRAPH_MATCH *match){
    for (int xi = 0; xi<COUNT ; xi++) {
          FindAugPath(match, xi);
          clearOnPathSign(match);
    }
    outputRes(match->path);
}
int main() {
    GRAPH_MATCH *graph = (GRAPH_MATCH *)malloc(sizeof(GRAPH_MATCH));
    for (int i = 0 ; i < COUNT ; i++) {
        for (int j = 0 ; j < COUNT ; j++) {
            graph->edge[i][j] = 0;
        }
    }
    graph->edge[0][1] = 1;
    graph->edge[0][0] = 1;
    graph->edge[1][1] = 1;
    graph->edge[1][2] = 1;
    graph->edge[2][1] = 1;
    graph->edge[2][0] = 1;
    graph->edge[3][2] = 1;
//举例
    for (int j = 0 ; j < COUNT ; j++) {
        graph->path[j] = -1;
        graph->on_path[j] = false;
    }
    Hungary_match(graph);   
}

参考学习资料:

**[1]**​匈牙利算法(二分图) - 神犇(shenben) - 博客园 (cnblogs.com)

  • 算法
    428 引用 • 254 回帖 • 24 关注
1 操作
XiaoweiH 在 2024-10-10 00:26:33 更新了该帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • 倾城之链
    23 引用 • 66 回帖 • 137 关注
  • Postman

    Postman 是一款简单好用的 HTTP API 调试工具。

    4 引用 • 3 回帖 • 3 关注
  • 又拍云

    又拍云是国内领先的 CDN 服务提供商,国家工信部认证通过的“可信云”,乌云众测平台认证的“安全云”,为移动时代的创业者提供新一代的 CDN 加速服务。

    21 引用 • 37 回帖 • 545 关注
  • Git

    Git 是 Linux Torvalds 为了帮助管理 Linux 内核开发而开发的一个开放源码的版本控制软件。

    209 引用 • 358 回帖
  • Facebook

    Facebook 是一个联系朋友的社交工具。大家可以通过它和朋友、同事、同学以及周围的人保持互动交流,分享无限上传的图片,发布链接和视频,更可以增进对朋友的了解。

    4 引用 • 15 回帖 • 453 关注
  • API

    应用程序编程接口(Application Programming Interface)是一些预先定义的函数,目的是提供应用程序与开发人员基于某软件或硬件得以访问一组例程的能力,而又无需访问源码,或理解内部工作机制的细节。

    77 引用 • 430 回帖 • 2 关注
  • 单点登录

    单点登录(Single Sign On)是目前比较流行的企业业务整合的解决方案之一。SSO 的定义是在多个应用系统中,用户只需要登录一次就可以访问所有相互信任的应用系统。

    9 引用 • 25 回帖
  • WiFiDog

    WiFiDog 是一套开源的无线热点认证管理工具,主要功能包括:位置相关的内容递送;用户认证和授权;集中式网络监控。

    1 引用 • 7 回帖 • 587 关注
  • OAuth

    OAuth 协议为用户资源的授权提供了一个安全的、开放而又简易的标准。与以往的授权方式不同之处是 oAuth 的授权不会使第三方触及到用户的帐号信息(如用户名与密码),即第三方无需使用用户的用户名与密码就可以申请获得该用户资源的授权,因此 oAuth 是安全的。oAuth 是 Open Authorization 的简写。

    36 引用 • 103 回帖 • 9 关注
  • V2Ray
    1 引用 • 15 回帖 • 1 关注
  • golang

    Go 语言是 Google 推出的一种全新的编程语言,可以在不损失应用程序性能的情况下降低代码的复杂性。谷歌首席软件工程师罗布派克(Rob Pike)说:我们之所以开发 Go,是因为过去 10 多年间软件开发的难度令人沮丧。Go 是谷歌 2009 发布的第二款编程语言。

    497 引用 • 1387 回帖 • 283 关注
  • 旅游

    希望你我能在旅途中找到人生的下一站。

    90 引用 • 899 回帖
  • 周末

    星期六到星期天晚,实行五天工作制后,指每周的最后两天。再过几年可能就是三天了。

    14 引用 • 297 回帖
  • 心情

    心是产生任何想法的源泉,心本体会陷入到对自己本体不能理解的状态中,因为心能产生任何想法,不能分出对错,不能分出自己。

    59 引用 • 369 回帖
  • 房星科技

    房星网,我们不和没有钱的程序员谈理想,我们要让程序员又有理想又有钱。我们有雄厚的房地产行业线下资源,遍布昆明全城的 100 家门店、四千地产经纪人是我们坚实的后盾。

    6 引用 • 141 回帖 • 585 关注
  • 链书

    链书(Chainbook)是 B3log 开源社区提供的区块链纸质书交易平台,通过 B3T 实现共享激励与价值链。可将你的闲置书籍上架到链书,我们共同构建这个全新的交易平台,让闲置书籍继续发挥它的价值。

    链书社

    链书目前已经下线,也许以后还有计划重制上线。

    14 引用 • 257 回帖
  • V2EX

    V2EX 是创意工作者们的社区。这里目前汇聚了超过 400,000 名主要来自互联网行业、游戏行业和媒体行业的创意工作者。V2EX 希望能够成为创意工作者们的生活和事业的一部分。

    17 引用 • 236 回帖 • 325 关注
  • SSL

    SSL(Secure Sockets Layer 安全套接层),及其继任者传输层安全(Transport Layer Security,TLS)是为网络通信提供安全及数据完整性的一种安全协议。TLS 与 SSL 在传输层对网络连接进行加密。

    70 引用 • 193 回帖 • 432 关注
  • C

    C 语言是一门通用计算机编程语言,应用广泛。C 语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言。

    85 引用 • 165 回帖 • 1 关注
  • Latke

    Latke 是一款以 JSON 为主的 Java Web 框架。

    71 引用 • 535 回帖 • 786 关注
  • Kafka

    Kafka 是一种高吞吐量的分布式发布订阅消息系统,它可以处理消费者规模的网站中的所有动作流数据。 这种动作(网页浏览,搜索和其他用户的行动)是现代系统中许多功能的基础。 这些数据通常是由于吞吐量的要求而通过处理日志和日志聚合来解决。

    36 引用 • 35 回帖
  • CloudFoundry

    Cloud Foundry 是 VMware 推出的业界第一个开源 PaaS 云平台,它支持多种框架、语言、运行时环境、云平台及应用服务,使开发人员能够在几秒钟内进行应用程序的部署和扩展,无需担心任何基础架构的问题。

    5 引用 • 18 回帖 • 167 关注
  • ngrok

    ngrok 是一个反向代理,通过在公共的端点和本地运行的 Web 服务器之间建立一个安全的通道。

    7 引用 • 63 回帖 • 624 关注
  • 创业

    你比 99% 的人都优秀么?

    84 引用 • 1399 回帖 • 1 关注
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3187 引用 • 8213 回帖
  • Lute

    Lute 是一款结构化的 Markdown 引擎,支持 Go 和 JavaScript。

    25 引用 • 191 回帖 • 16 关注
  • TextBundle

    TextBundle 文件格式旨在应用程序之间交换 Markdown 或 Fountain 之类的纯文本文件时,提供更无缝的用户体验。

    1 引用 • 2 回帖 • 47 关注