【算法小总结】二分图最大匹配的非递归方法-阿里云开发者社区

开发者社区> 光仔december> 正文

【算法小总结】二分图最大匹配的非递归方法

简介:
+关注继续查看

二分图最大匹配的非递归方法

 

代码:

#define SIZE 100

int mat[SIZE][SIZE]; /*图矩阵*/

int match1[SIZE];
int match2[SIZE];

int queue[SIZE];
int head,tail;

int pre[SIZE];

int maxMatch(int N){
    int ret = 0;
    memset(match1,-1,sizeof(match1));
    memset(match2,-1,sizeof(match2));

    for(int i=0;i<N;i++){
        memset(pre,-1,sizeof(pre));
        head = tail = 0;
        queue[tail++] = i;
        while(head < tail && match1[i]==-1){
            int u = queue[head++];
            for(int j =0;j<N&&match1[i]==-1;j++)
                if(mat[u][j] && pre[j]==-1){
                    queue[tail++] = match2[j];
                    pre[j]=u;
                    if(queue[tail-1]<0){
                        for(int t=j,k=0;t>=0;j=t){
                            match2[j]=k=pre[j];
                            t=match1[k];
                            match1[k]=j;
                        }
                    }
                }
        }
    }
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
JVM中垃圾收集算法总结
通过前面的介绍我们了解了对象创建和销毁的过程。那么JVM中垃圾收集器具体对对象回收采用的是什么算法呢?本文主要记录下JVM中垃圾收集的几种算法。
7 0
Java基础-11总结Eclipse使用,API,Object类
你需要的是什么,直接评论留言。 获取更多资源加微信公众号“Java帮帮” (是公众号,不是微信好友哦) 还有“Java帮帮”今日头条号,技术文章与新闻,每日更新,欢迎阅读 学习交流请加Java帮帮交流QQ群553841695 分享是一种美德,分享更快乐! 1:Eclipse的概述使用(掌握) 1:Eclipse的安装 2:用
1537 0
+关注
光仔december
目前致力于JavaEE(struts/hibernate/spring/MyBatis等框架)、数据库(Mysql/oracle)、静态页面(Html/Css)技术和脚本(JavaSript/JQuery/Ajax)等技术方面的研究
497
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载