Main Content

本页的翻译已过时。点击此处可查看最新英文版本。

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. The axes contains an object of type graphplot.

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

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

Figure contains an axes. The axes 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. The axes contains an object of type graphplot.

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

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

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

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

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

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

输入参数

全部折叠

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

示例: G = graph(1,2)

名称-值对组参数

指定可选的、以逗号分隔的 Name,Value 对组参数。Name 为参数名称,Value 为对应的值。Name 必须放在引号中。您可采用任意顺序指定多个名称-值对组参数,如 Name1,Value1,...,NameN,ValueN 所示。

示例: [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',则对于与根节点不在同一分量中的所有节点 Ipred(I) = NaN

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

详细信息

全部折叠

最小生成树

对于连通图,生成树是一个子图,其中连接图中的每个节点但不包含任何循环。对于任一给定图,可以有许多生成树。通过为每条边分配权重,不同生成树均被分配一个表示其各边总权重的数字。然后,最小生成树就是各边的总权重最小的生成树。

对于边权重相等的图,所有生成树都是最小生成树,因为遍历 n 个节点需要 n-1 条边。

另请参阅

| |

在 R2015b 中推出