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 是终端节点数。

参数

返回

笔记

对于具有最小边的树，Steiner在图的两个边之间放置了最小的权值。

工具书类