主要内容

minspantree

图的最小生成树

折叠所有页面

语法

T = minspantree(G)
T = minspantree(G，名称，值)
[T,pred] = minspantree(___）

描述

例子

T= minspantree (G）返回最小生成树，T，表示图形G．

例子

T= minspantree (G，名称,值）使用由一个或多个名称-值对参数指定的其他选项。例如,minspantree (G,‘法’,‘稀疏’)使用Kruskal算法来计算最小生成树。

例子

［T，pred= minspanttree (___）还返回一个由前一个节点组成的向量，pred，使用以前语法中的任何输入参数。

例子

全部折叠

打开实时脚本

创建并绘制带有加权边的立方体图。

S = [1 1 1 2 5 3 6 4 7 8 8 8];T = [2 3 4 5 3 6 4 7 2 6 7 5];权重= [100 10 10 10 10 20 10 30 50 10 70 10];G =图(s,t，权重);p = plot(G，“EdgeLabel”, G.Edges.Weight);

图中包含一个轴对象。axis对象包含一个graphplot类型的对象。

计算并在图的顶部绘制图的最小生成树。T包含相同的节点G，而是边的子集。

[T,pred] = minspantree(G);突出(p T)

图中包含一个轴对象。axis对象包含一个graphplot类型的对象。

打开实时脚本

创建并绘制具有多个组件的图形。

S = {“一个”“一个”“一个”“b”“b”“c”“e”“e”“f”“f”“f”“f”‘g’‘g’};T = {“b”“c”' d '“c”' d '' d '“f”‘g’‘g’“h”“我”“j”“我”“j”};G =图(s,t);p = plot(G，“布局”，“分层”）;

图中包含一个轴对象。axis对象包含一个graphplot类型的对象。

求图的最小生成林，从节点开始我．在图中突出显示生成的森林。图节点名称被带入最小生成树图。

[T,pred] = minspantree(G，“类型”，“森林”，“根”findnode (G,“我”));突出(p T)

图中包含一个轴对象。axis对象包含一个graphplot类型的对象。

使用前一个节点的向量，pred，以创建最小生成林的有向版本。该树中的所有边都指向远离每个组件(节点)中的根节点的方向我而且一个）.

rootedTree = digraph(pred(pred~=0)，find(pred~=0)，[]，G.Nodes.Name);情节(rootedTree)

图中包含一个轴对象。axis对象包含一个graphplot类型的对象。

输入参数

全部折叠

输入图形，指定为a图对象。使用图创建一个无向图对象。

例子:G =图(1,2)

名称-值参数

指定可选参数对为Name1 = Value1,…,以=家,在那里的名字参数名称和价值对应的值。名称-值参数必须出现在其他参数之后，但对的顺序无关紧要。

在R2021a之前，使用逗号分隔每个名称和值，并将其括起来的名字在报价。

例子:[T,pred] = minspantree(G，'Method'，'sparse')

最小生成树算法，由逗号分隔的对组成“方法”这是表格中的一个选项。

选项 描述
“密集”(默认) 一本正经的算法。该算法从根节点开始，在遍历图时向树中添加边。
“稀疏” 克鲁斯卡算法。该算法根据权重对所有边进行排序，如果它们没有创建循环，则将它们添加到树中。

根节点，指定为逗号分隔的对，由“根”和节点索引或节点名。默认根节点为1．

  • 如果“方法”是“密集”(默认值)，则根节点是开始节点。

  • 如果“方法”是“稀疏”，则根节点仅用于计算pred为前一节点的向量。

你可以用以下格式指定根节点:

价值 例子
标量节点索引 1
字符向量节点名称 “一个”
字符串标量节点名称 “一个”

最小生成树的类型，指定为由逗号分隔的对组成“类型”这是表格中的一个选项。

选项 描述
“树”

只返回一个树。树包含根节点。
“森林”

返回一个最小生成树的森林。换句话说，就是指定“森林”计算图中所有连通组件的最小生成树。

输出参数

全部折叠

最小生成树，返回为图对象。

前任节点，作为节点索引的向量返回。pred(我)节点索引是节点的前身吗我．按照惯例,pred(rootNode) = 0．如果类型是“树”,然后pred(I) = NaN对于所有节点我与根节点不在同一个组件中的。

pred指定最小生成树的有向版本，所有边都指向远离根节点。

更多关于

全部折叠

最小生成树

对于连通图，生成树是一个子图，它连接图中的每个节点，但不包含循环。对于任何给定的图都可以有很多生成树。通过为每条边分配权重，不同的生成树将为其边的总权重分配一个数字。最小生成树就是其边的总权值最小的生成树。

对于边权值相等的图，由于遍历，所有的生成树都是最小生成树n节点需要n - 1边缘。

版本历史

在R2015b中引入

另请参阅

||