摘要
Minty算法和Mayeda—Seshu算法是求无向连通图树清单的两个直观算法,它们都比矩阵算法节省计算时间。然而,它们仍然较复杂。本文分别对这两个算法提出了改进措施,大大降低了计算复杂性。改进后的算法既简单又直观易懂。对于Minty算法,我们提出了一个不完全算法;对Mayeda—Seshu算法,我们则避开了求基本割集这一复杂步骤。
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.
出处
《贵州大学学报（自然科学版）》
1991年第4期213-219,共7页
Journal of Guizhou University:Natural Sciences
基金
贵州大学科学基金
关键词
无向连通图
支撑树
M算法
M-S算法
undirected connected graph
spanning tree
base cut-set
Minty algorithm Mayeda-Seshu algorithm
