minspantree

图的最小生成树

全页折叠

语法

T = minspantree(G)
T = minspantree(G,Name,Value)
[T,pred] = minspantree(___)

说明

T = minspantree(G) 返回图 G 的最小生成树 T。

示例

T = minspantree(G,Name,Value) 使用一个或多个名称-值对组参量指定的其他选项。例如，minspantree(G,'Method','sparse') 使用 Kruskal 的算法来计算最小生成树。

示例

[T,pred] = minspantree(___) 支持上述语法中的任何输入参量，且可返回前趋节点的向量 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];
weights = [100 10 10 10 10 20 10 30 50 10 70 10];
G = graph(s,t,weights);
p = plot(G,'EdgeLabel',G.Edges.Weight);

Figure contains an axes object. The axes object contains an object of type graphplot.

计算并在图上方绘制图的最小生成树。T 包含的节点与 G 相同，但包含的边仅为后者的子集。

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

Figure contains an axes object. The axes object contains an object of type graphplot.

打开实时脚本

创建并绘制一个包含多个分量的图。 

s = {'a' 'a' 'a' 'b' 'b' 'c' 'e' 'e' 'f' 'f' 'f' 'f' 'g' 'g'};
t = {'b' 'c' 'd' 'c' 'd' 'd' 'f' 'g' 'g' 'h' 'i' 'j' 'i' 'j'};
G = graph(s,t);
p = plot(G,'Layout','layered');

Figure contains an axes object. The axes object contains an object of type graphplot.

找出图的最小生成森林，从节点 i 开始。在绘图中突出显示生成的森林。图节点名称显示在最小生成树图中。

[T,pred] = minspantree(G,'Type','forest','Root',findnode(G,'i'));
highlight(p,T)

Figure contains an axes object. The axes object contains an object of type graphplot.

使用前趋节点向量 pred 创建有向最小生成森林。此树中的所有边都从每个分量中的根节点（节点 i 和 a）向外发出。

rootedTree = digraph(pred(pred~=0),find(pred~=0),[],G.Nodes.Name);
plot(rootedTree)

Figure contains an axes object. The axes object contains an object of type graphplot.

输入参数

全部折叠

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

示例: G = graph(1,2)

名称-值参数

全部折叠

以 Name1=Value1,...,NameN=ValueN 的形式指定可选参量对组，其中 Name 是参量名称，Value 是对应的值。名称-值参量必须出现在其他参量之后，但对各个参量对组的顺序没有要求。

在 R2021a 之前，使用逗号分隔每个名称和值，并用引号将 Name 引起来。

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

最小生成树算法，指定为逗号分隔的对组，其中包含 'Method' 和下表中的选项之一。

选项描述
'dense'（默认值）Prim 的算法。此算法从根节点开始，在遍历图时将边添加到树中。
'sparse'Kruskal 的算法。此算法按权重对所有边排序，然后将不构成循环的边添加到树中。

根节点，以逗号分隔的对组形式指定，该对组由 'Root' 和一个节点索引或节点名称组成。默认根节点是 1。

  • 如果 'Method' 是 'dense'（默认值），则根节点是起始节点。

  • 如果 'Method' 是 'sparse'，则根节点仅用于计算 pred，即前趋节点的向量。

您可以使用以下任一格式指定根节点：

值示例
标量节点索引1
字符向量节点名称'A'
字符串标量节点名称"A"

最小生成树的类型，指定为逗号分隔的对组，其中包含 'Type' 和下表中的选项之一。

选项描述
'tree'

仅返回单一树。树包含根节点。

'forest'

返回最小生成树的森林。换言之，指定 'forest' 可计算图中所有连通分量的最小生成树。

输出参量

全部折叠

最小生成树，以 graph 对象形式返回。

前趋节点，以节点索引的向量形式返回。pred(I) 是节点 I 的前趋节点的节点索引。按照惯例，pred(rootNode) = 0。如果 Type 是 'tree'，则对于与根节点不在同一分量中的所有节点 I，pred(I) = NaN。

pred 指定有向的最小生成树，所有边从根节点向外发出。

详细信息

全部折叠

扩展功能

全部展开

基于线程的环境
使用 MATLAB® backgroundPool 在后台运行代码或使用 Parallel Computing Toolbox™ ThreadPool 加快代码运行速度。

版本历史记录

在 R2015b 中推出

另请参阅

| |