两个图算法的改进

Minty算法和Mayeda—Seshu算法是求无向连通图树清单的两个直观算法,它们都比矩阵算法节省计算时间。然而,它们仍然较复杂。本文分别对这两个算法提出了改进措施,大大降低了计算复杂性。改进后的算法既简单又直观易懂。对于Minty算法,我们提出了一个不完全算法;对Mayeda—Seshu算法,我们则避开了求基本割集这一复杂步骤。

Improvment of two Graph Algorithms

Minty algorithm and Mayeda-Seshu Algorithm are two intuitive algorithms finding list of spanning tree of undirected connected graph. Its computation time is less than the matrix algorithm's, but still more complex. The improvements of two graph algorithms are presented, it decrease the complexity. Two improved algorithms are simple and intuitive. For Minty algorithm, we give a incomplete algorithm. For Mayeda-Seshu alorithm, we avoid complex process of finding base cut-set.