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

Matching Algorithms for General Graphs Based on Depth-First Search

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

For the matching problem of general graphs, the Edmonds algorithm is usually used. When the breadth-first search algorithm is used to find an augmenting-path,a ＂flower＂ may be produced. In order to solve this problem, we can cut short the ＂flower＂ into a point, and keep on searching, then the obtained graph after finding the augmenting-path is rehabilitated. The time efficiency of the algorithm is O（n^4） since the graph is cut short and rehabilitated. However, when using the Gabow algorithm to find the augmenting-path, we should assign a fixed serial number to node and edges, and use different arrays and pseudo node, thus we need not to deal with the ＂flower＂, and the time efficiency of this algorithm is O（nS）, but the space efficiency of the algorithm is reduced. This paper proposes a depth-first search algorithm, and it is shown that using the proposed algorithm, the ＂flowers＂ will not appear when searching an augmenting-path. Moreover, the time effi- ciency is increased to O（n ＊ degree（n））, where degree（n） denotes the average degree of nodes. In addition, when either ap- pending or deleting the edges in the graph, maximum matching can be computed quickly. It should be pointed out that if we follow this idea to consider the breadth-first search, the order of magnitude is identical to the one in depth-first search.