Algorithms for Generating All Spanning Trees of Undirected, Directed and Weighted Graphs
Algorithms for Generating All Spanning Trees of Undirected, Directed and Weighted Graphs
复制标题
生成无向图、有向图和加权图的所有生成树的算法
DOI：
10.1007/bfb0028284
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
H. Ramesh
中科院分区：
文献类型：
--
作者：
S. Kapoor;H. Ramesh
我们提出的算法枚举所有的生成树有向，无向和加权图。该算法使用搜索树技术来构造计算树。计算树用于通过列出生成树之间的相对差异而不是整个生成树本身来输出所有生成树。对于无向情形，对于一个顶点数为V，边数为E，生成树数为N的图，其树的构造和排序都需要O（N+V+E）时间.该算法是最优的，是基于交换非树边与树边在一个基本的循环。一个类似的交换技术被用来在O（NV+V3）时间内构造有向图的计算树。列出树的时间为O（N）。对于一个加权图，我们展示了如何使用计算树在O（NlogV+VE）时间内按权重对生成树进行排序。
We present algorithms for enumerating all spanning trees in directed, undirected and weighted graphs. The algorithms use a search tree technique to construct a computation tree. The computation tree is used to output all the spanning trees by listing the relative differences between spanning trees rather than the entire spanning trees themselves. For the undirected case, both the construction and the listing of the trees are shown to requireO(N+V+E) time for a graph withVvertices,Eedges andNspanning trees. This algorithm is optimal and is based on exchanging non-tree edges with tree edges in a fundamental cycle. A similar exchange technique is used to construct the computation tree for a directed graph inO(NV+V3) time. The time for listing out the trees remainsO(N). For a weighted graph, we show how to sort the spanning trees by weight using the computation tree inO(NlogV+VE) time.