WOLFRAM

Wolfram 语言与系统参考资料中心

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

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

FindSpanningTree[g]

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

FindSpanningTree[{g,v},…]

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

FindSpanningTree[{vw,…},…]

使用规则 vw 指定图 g.

更多信息和选项
Details and Options Details and Options
范例  
基本范例  
范围  
推广和延伸  
选项  
EdgeWeight  
Method  
应用  
属性和关系  
可能存在的问题  
巧妙范例  
参见
相关指南
历史
按以下格式引用：

FindSpanningTree

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

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

FindSpanningTree[g]

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

FindSpanningTree[{g,v},…]

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

FindSpanningTree[{vw,…},…]

使用规则 vw 指定图 g.

更多信息和选项

范例

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

基本范例  (1)

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

Wolfram Language code: g = [image];
Wolfram Language code: FindSpanningTree[g]

高亮显示生成树：

Wolfram Language code: HighlightGraph[g, %, GraphHighlightStyle -> "Thick"]

范围  (10)

FindSpanningTree 适用于点的列表：

Wolfram Language code: FindSpanningTree[RandomReal[1, {20, 2}]]

字符串列表：

Wolfram Language code: FindSpanningTree[{"cat", "dog", "do", "cap", "dock"}]

测地位置列表：

Wolfram Language code: FindSpanningTree[{GeoPosition[{41, 20}], GeoPosition[{5, 20}], GeoPosition[{49, 32}], GeoPosition[{53, 28}], GeoPosition[{47, 29}]}]

FindSpanningTree 适用于无向图：

Wolfram Language code: FindSpanningTree[[image]]

有向图：

Wolfram Language code: FindSpanningTree[[image]]

加权图：

Wolfram Language code: FindSpanningTree[[image]]

多重图：

Wolfram Language code: FindSpanningTree[[image]]

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

Wolfram Language code: FindSpanningTree[{[image], 4}]

使用规则指定图：

Wolfram Language code: FindSpanningTree[{1 -> 3, 2 -> 1, 3 -> 6, 4 -> 6, 1 -> 5, 5 -> 4, 6 -> 1}]

FindSpanningTree 适用于大型图：

Wolfram Language code: g = GridGraph[{10, 10, 10, 10, 10}];
Wolfram Language code: VertexCount[FindSpanningTree[g]]//Timing

推广和延伸  (1)

找到最大生成树：

Wolfram Language code: g = [image];
Wolfram Language code: eweight = AnnotationValue[{g, #}, EdgeWeight]& /@ EdgeList[g]
Wolfram Language code: FindSpanningTree[g, EdgeWeight -> -1 * eweight]

选项  (5)

EdgeWeight  (1)

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

Wolfram Language code: FindSpanningTree[[image]]

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

Wolfram Language code: FindSpanningTree[[image], EdgeWeight -> {3, 4, 5, 1, 2, 3, 7}]

Method  (4)

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

Wolfram Language code: {WheelGraph[7], WheelGraph[7, EdgeWeight -> RandomReal[1, 12]]}
Wolfram Language code: Table[HighlightGraph[g, FindSpanningTree[g]], {g, %}]

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

Wolfram Language code: g = [image];
Wolfram Language code: HighlightGraph[g, FindSpanningTree[g, Method -> "Prim"]]

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

Wolfram Language code: g = [image];
Wolfram Language code: HighlightGraph[g, FindSpanningTree[g, Method -> "Kruskal"]]

"MinimumCostArborescence" 可用于有向图：

Wolfram Language code: g = [image];
Wolfram Language code: HighlightGraph[g, FindSpanningTree[g, Method -> "MinimumCostArborescence"]]
Wolfram Language code: FindShortestTour

应用  (7)

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

Wolfram Language code: g = [image];
Wolfram Language code: fibernetwork = FindSpanningTree[g];
Wolfram Language code: HighlightGraph[g, fibernetwork, GraphHighlightStyle -> "Thick"]

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

Wolfram Language code: locations = RandomReal[1, {10, 2}];
Wolfram Language code: vname = {"H1", "H2", "H3", "H4", "H5", "H6", "H7", "H8", "H9", "H10"};
Wolfram Language code: phonenetwork = FindSpanningTree[locations, VertexLabels -> Table[i -> vname[[i]], {i, 10}]]

算出的电话线的总长度：

Wolfram Language code: Total[AnnotationValue[{phonenetwork, #}, EdgeWeight]& /@ EdgeList[phonenetwork]]

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

Wolfram Language code: g = CompleteGraph[10, EdgeWeight -> RandomInteger[5, 45]];
Wolfram Language code: FindSpanningTree[{g, 1}]

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

Wolfram Language code: Annotate[%, VertexLabels -> "Name"]

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

Wolfram Language code: g = [image];

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

Wolfram Language code: distances = With[{coords = VertexCoordinates /. Options[g, VertexCoordinates]}, Map[EuclideanDistance[coords[[VertexIndex[g, First[#]]]], coords[[VertexIndex[g, Last[#]]]]]&, EdgeList[g]]];
Wolfram Language code: FindSpanningTree[g, EdgeWeight -> distances];

显示高速公路：

Wolfram Language code: HighlightGraph[g, %, GraphHighlightStyle -> "DehighlightGray"]

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

Wolfram Language code: g = GridGraph[{20, 30}, EdgeWeight -> RandomReal[10, 1150]];

最小生成树：

Wolfram Language code: tree = FindSpanningTree[{g, 1}];

自定义迷宫的风格：

Wolfram Language code: style = {Background -> GrayLevel[0], EdgeStyle -> {Directive[GrayLevel[1], Thickness[0.017], Opacity[1], CapForm["Square"]]}, VertexShapeFunction -> "Square", VertexSize -> {.2, .2}, VertexStyle -> Directive[White, EdgeForm[]]};

迷宫图：

Wolfram Language code: Graph[tree, VertexCoordinates -> GraphEmbedding[g], style]

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

Wolfram Language code: completeGraph[n_, dist_] := CompleteGraph[n, EdgeWeight -> RandomVariate[dist, n * (n - 1) / 2]]
Wolfram Language code: Table[completeGraph[n, UniformDistribution[]], {n, 4, 7}]

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

Wolfram Language code: size[g_] := With[{edges = EdgeList[FindSpanningTree[{g, 1}]]}, Total[AnnotationValue[{g, #}, EdgeWeight]& /@ edges]]
Wolfram Language code: Table[size[completeGraph[n, UniformDistribution[]]], {n, 4, 7}]

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

Wolfram Language code: Mean[Table[size[completeGraph[n, UniformDistribution[]]], {n, 100, 200}]]
Wolfram Language code: Zeta[3.]

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

Wolfram Language code: europe = ["europe capital"];
Wolfram Language code: FindSpanningTree[europe]

可视化国家之间的路径：

Wolfram Language code: GeoGraphPlot[%]

属性和关系  (2)

生成树图是树图：

Wolfram Language code: g = [image];
Wolfram Language code: FindSpanningTree[g]
Wolfram Language code: TreeGraphQ[%]

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

Wolfram Language code: g = GraphData["DodecahedralGraph"];
Wolfram Language code: BreadthFirstScan[g, 1, {"PrevisitVertex" -> (#&)}]
Wolfram Language code: HighlightGraph[g, TreeGraph[VertexList[g], %]]

使用 DepthFirstScan 找到生成树：

Wolfram Language code: DepthFirstScan[g, 1, {"PrevisitVertex" -> (#&)}]
Wolfram Language code: HighlightGraph[g, TreeGraph[VertexList[g], %]]

可能存在的问题  (1)

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

Wolfram Language code: g = GraphData[{"Circulant", {10, {2, 4}}}]
Wolfram Language code: FindSpanningTree[g]

突出显示生成树：

Wolfram Language code: HighlightGraph[g, Subgraph[%, #]& /@ ConnectedComponents[%]]

巧妙范例  (1)

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

Wolfram Language code: dist = TransformedDistribution[Normalize[{x, y, z}], {x, y, z}ProductDistribution[{NormalDistribution[], 3}]];
Wolfram Language code: g = RandomGraph[SpatialGraphDistribution[200, 0.3, dist]];
Wolfram Language code: HighlightGraph[g, FindSpanningTree[g]]
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_2026_findspanningtree, author="Wolfram Research", title="{FindSpanningTree}", year="2021", howpublished="\url{https://reference.wolfram.com/language/ref/FindSpanningTree.html}", note=[Accessed: 09-September-2026]}

BibLaTeX

@online{reference.wolfram_2026_findspanningtree, organization={Wolfram Research}, title={FindSpanningTree}, year={2021}, url={https://reference.wolfram.com/language/ref/FindSpanningTree.html}, note=[Accessed: 09-September-2026]}