文献类型：期刊文章

作　　者：虞成诚[1] 钟声[1] 胡绍华[2]

机构地区：[1]海南大学计算机科学与技术系,海南海口570228 [2]南昌广播电视大学,江西南昌330000

出　　处：《计算机工程与科学》

基　　金：海南省自然科学基金资助项目(80636);海南省教育厅资助项目(Hjkj200705)

年　　份：2008

卷　　号：30

期　　号：12

起止页码：45-48

语　　种：中文

收录情况：CSCD、CSCD2011_2012、JST、ZGKJHX、普通刊

摘　　要：对于一般图的匹配问题,Edmonds算法以Berge定理为基础,采用广度优先搜索增广路,图中可能存在"花"。遇到这种情况,要对它进行缩减"花"处理,再进行搜索。当找到增广路时,要将缩减图恢复,算法显得复杂。Gabow等算法使用先给固的顶点和边编号,并使用了不同数组和虚拟顶点,避免了处理花。算法的复杂性为O(n3),但增加了空间复杂性。本文提出的基于深度优先搜索算法,在搜索增广路时不会出现"花"的情况,算法相对简单;同时,算法时间效率为O(n*degree(n)),degree(n)为顶点的平均度数。另外,当图的边动态增减时,使用该算法可以很快调整最大匹配,并且该算法空间复杂性在同一数量级也可以推广到广度优先搜索。

关 键 词：匹配问题  组合优化算法  图匹配

分 类 号：TP301.6]