基于深度优先搜索的一般图匹配算法

• 作者: 胡绍华 虞成诚 钟声
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 匹配问题 组合优化算法 图匹配
• 年，卷（期）: 2008,（12）
• 所属期刊栏目: 图形与图像
• 页码范围: 45-48
• 页数: 4页
• 分类号: TP301.6
• 字数: 3911字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2008.12.012

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	钟声	海南大学计算机科学与技术系	36	173	8.0	11.0
2	虞成诚	海南大学计算机科学与技术系	1	9	1.0	1.0
3	胡绍华		1	9	1.0	1.0