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

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

单位：海南大学计算机科学与技术系 海南海口570228 南昌广播电视大学 江西南昌330000