A Flexible Algorithm for Generating All the Spanning Trees in Undirected Graphs
A Flexible Algorithm for Generating All the Spanning Trees in Undirected Graphs
复制标题
一种生成无向图中所有生成树的灵活算法
DOI：
10.1007/pl00009171
复制
发表时间：
1997
期刊：
影响因子：
1.1
通讯作者：
Tomomi Matsui
中科院分区：
文献类型：
--
作者：
Tomomi Matsui
本文提出了一种生成无向图中所有生成树的算法。该算法所需的时间为O(n+m+τn)，其中给定的图有顶点、中间和τ生成树。为了显式地输出所有的生成树，该算法的时间复杂度是最优的，算法遵循生成树多面体骨架图上的一种特殊的根树结构。遍历有根树结构的规则与时间复杂性无关。从这个意义上说，我们的算法是灵活的。如果我们采用深度优先搜索规则，我们也可以节省内存需求(n+m)。广度优先实现需要同样多的ASO(m+τn)空间，但当有并行计算机可用时，这可能具有优势。当给定的图被加权时，最佳优先搜索规则为最小生成树问题提供了一种排序算法。当有最小生成树时，排序算法需要O(n+m+τn)时间和(m+τn)空间。
In this paper we propose an algorithm for generating all the spanning trees in undirected graphs. The algorithm requiresO (n+m+ τ n)time where the given graph hasnvertices,medges, andτspanning trees. For outputting all the spanning trees explicitly, this time complexity is optimal.Our algorithm follows a special rooted tree structure on the skeleton graph of the spanning tree polytope. The rule by which the rooted tree structure is traversed is irrelevant to the time complexity. In this sense, our algorithm is flexible.If we employ the depth-first search rule, we can save the memory requirement toO (n+m).A breadth-first implementation requires as much asO (m+ τ n)space, but when a parallel computer is available, this might have an advantage. When a given graph is weighted, the best-first search rule provides a ranking algorithm for the minimum spanning tree problem. The ranking algorithm requiresO (n+ m + τ n)time andO (m+ τ n)space when we have a minimum spanning tree.
影响因子：
--
作者：
PRIM, RC
通讯作者：
PRIM, RC