steiner_tree#
- steiner_tree(G, terminal_nodes, weight='weight')[源代码]#
返回图形的最小Steiner树的近似值。
最小Steiner树
G
w、 r.t一套terminal_nodes
里面有棵树吗G
它跨越这些节点,并且在所有这些树中具有最小的大小(边权重的总和)。最小Steiner树可以通过计算度量闭包子图的最小生成树来逼近 G 由终端节点诱导,其中度量闭包 G 是一个完整的图,其中每一条边都由节点之间的最短路径距离加权。 G . 该算法生成一个树,其权重在最佳斯坦纳树权重的(2-(2/t))因子内,其中 t 是终端节点数。
- 参数
- G网络X图表
- terminal_nodes列表
要找到其最小Steiner树的终端节点的列表。
- 返回
- 网络X图表
最小斯坦纳树的近似
G
诱导terminal_nodes
.
笔记
对于具有最小边的树,Steiner在图的两个边之间放置了最小的权值。
工具书类
- 1
维基百科上的Steiner_uTree_uu问题。https://en.wikipedia.org/wiki/Steineru treeu问题