Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs
Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs
复制标题
枚举无向图和加权图的所有生成树的算法
DOI：
10.1137/s009753979225030x
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
H. Ramesh
中科院分区：
文献类型：
--
作者：
S. Kapoor;H. Ramesh
在本文中，我们提出了算法的枚举生成树的无向图，有和没有重量。
该算法使用搜索树技术来构造计算树。计算树可以用于通过仅输出生成树之间的相对变化而不是整个生成树本身来输出所有生成树。计算树的建设和上市的树所示，需要$O（N+V+E）$操作的情况下，无向图没有权重。基本算法基于在基本循环中交换边缘。对于加权图（无向）的情况下，我们表明，生成树的计算树的节点可以排序的重量增加的顺序，在$O（N\log V+VE）$时间。生成树本身可以在$O（NV）$ time中列出。这里$N$，$V$和$E$分别表示图的生成树、顶点和边的数量。
In this paper, we present algorithms for enumeration of spanning trees in undirected graphs, with and without weights.
The algorithms use a search tree technique to construct a computation tree. The computation tree can be used to output all spanning trees by outputting only relative changes between spanning trees rather than the entire spanning trees themselves. Both the construction of the computation tree and the listing of the trees is shown to require $O(N+V+E)$ operations for the case of undirected graphs without weights. The basic algorithm is based on swapping edges in a fundamental cycle. For the case of weighted graphs (undirected), we show that the nodes of the computation tree of spanning trees can be sorted in increasing order of weight, in $O(N\log V+VE)$ time. The spanning trees themselves can be listed in $O(NV)$ time. Here $N$, $V$, and $E$ refer respectively to the number of spanning trees, vertices, and edges of the graph.