FindSpanningTree

FindSpanningTree[{v1,v2,…,vn}]

求可最小化 vi 之间总距离的生成树.

FindSpanningTree[g]

求可最小化顶点之间总距离的图 g 的生成树.

FindSpanningTree[{g,v},…]

找到 g 包括顶点 v 的连通分量的生成树.

FindSpanningTree[{vw,…},…]

使用规则 vw 指定图 g.

更多信息和选项

范例

打开所有单元关闭所有单元

基本范例  (1)

找到一个图的最小生成树：

高亮显示生成树：

范围  (10)

FindSpanningTree 适用于点的列表：

字符串列表：

测地位置列表：

FindSpanningTree 适用于无向图：

有向图：

加权图：

多重图：

找到指定起始根的最小生成树：

使用规则指定图：

FindSpanningTree 适用于大型图：

推广和延伸  (1)

找到最大生成树：

选项  (5)

EdgeWeight  (1)

默认情况下，如果可用，边的权值取其 EdgeWeight 注释，否则为1：

使用 EdgeWeight->weights 设置边的权值：

Method  (4)

方法是根据输入自动选择：

"Prim" 可用于无向稠密图：

"Kruskal" 可用于无向稀疏图：

"MinimumCostArborescence" 可用于有向图：

应用  (7)

一个公司正在为一些芝加哥郊区筹划光纤网络. 它仅具有将它们的光纤沿某些走廊的优先通行权. 这些走廊中的某一些可能更昂贵. 找到连接走廊的子图，使得与各郊区连接总成本最低：

电话公司的任务是为一个有 10 户人家的村庄提供电话线. 每个节点都是一个房子，每个房子都有一个位置. 找到一种使用最少电话线连接所有房屋的方法：

算出的电话线的总长度：

一个二维数组，各行具有相似的元素，仅在几个地方有区别. 表示行 和 的不同元素的数目. 该数组可以如此存储：表示一个整行，而其他各行用不同于另一行的元素表示来存储. 我们可以将各矩阵的行作为顶点进行模拟，其中用边连接每个顶点，用 的权值表示相异元素的个数. 使用最小权值生成树找到一个有效的存储方案：

完全存储第1行，对于其他行，仅存储位置和不同于其父级的元素：

建设州际高速公路系统，连接所有非洲国家的地理中心：

最小化各国之间的总距离：

显示高速公路：

从具有随机权值的格子图，生成迷宫：

最小生成树：

自定义迷宫的风格：

迷宫图：

对于具有均匀分布随机权值的完全图，求最小生成树的期望尺寸：

生成树的大小可表示为生成树的边权的总和：

对于大型完全图，期望尺寸趋近 TemplateBox[{3}, Zeta]：

求访问欧洲国家的最小生成树：

可视化国家之间的路径：

属性和关系  (2)

生成树图是树图：

BreadthFirstScan 可用于找到图的生成树：

使用 DepthFirstScan 找到生成树：

可能存在的问题  (1)

不连通图给出每个连通分量的生成树：

突出显示生成树：

巧妙范例  (1)

随机图的最小生成树，顶点在球体上均匀分布：

Wolfram Research (2014)，FindSpanningTree，Wolfram 语言函数，https://reference.wolfram.com/language/ref/FindSpanningTree.html （更新于 2021 年）.

文本

Wolfram Research (2014)，FindSpanningTree，Wolfram 语言函数，https://reference.wolfram.com/language/ref/FindSpanningTree.html （更新于 2021 年）.

CMS

Wolfram 语言. 2014. "FindSpanningTree." Wolfram 语言与系统参考资料中心. Wolfram Research. 最新版本 2021. https://reference.wolfram.com/language/ref/FindSpanningTree.html.

APA

Wolfram 语言. (2014). FindSpanningTree. Wolfram 语言与系统参考资料中心. 追溯自 https://reference.wolfram.com/language/ref/FindSpanningTree.html 年

BibTeX

@misc{reference.wolfram_2024_findspanningtree, author="Wolfram Research", title="{FindSpanningTree}", year="2021", howpublished="\url{https://reference.wolfram.com/language/ref/FindSpanningTree.html}", note=[Accessed: 21-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_findspanningtree, organization={Wolfram Research}, title={FindSpanningTree}, year={2021}, url={https://reference.wolfram.com/language/ref/FindSpanningTree.html}, note=[Accessed: 21-November-2024 ]}