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