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

摘要

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