minspantree
图的最小生成树
说明
示例
立方体图的最小生成树
使用加权边创建并绘制一个立方体图。
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);
计算并在图上方绘制图的最小生成树。T
包含的节点与 G
相同,但包含的边仅为后者的子集。
[T,pred] = minspantree(G); highlight(p,T)
始于指定根节点的最小生成森林
创建并绘制一个包含多个分量的图。
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');
找出图的最小生成森林,从节点 i
开始。在绘图中突出显示生成的森林。图节点名称显示在最小生成树图中。
[T,pred] = minspantree(G,'Type','forest','Root',findnode(G,'i')); highlight(p,T)
使用前趋节点向量 pred
创建有向最小生成森林。此树中的所有边都从每个分量中的根节点(节点 i
和 a
)向外发出。
rootedTree = digraph(pred(pred~=0),find(pred~=0),[],G.Nodes.Name); plot(rootedTree)
输入参数
G
— 输入图
graph
对象
输入图,指定为 graph
对象。使用 graph
创建一个无向图对象。
示例: G = graph(1,2)
名称-值参数
将可选的参量对组指定为 Name1=Value1,...,NameN=ValueN
,其中 Name
是参量名称,Value
是对应的值。名称-值参量必须出现在其他参量之后,但参量对组的顺序无关紧要。
在 R2021a 之前,使用逗号分隔每个名称和值,并用引号将 Name
引起来。
示例: [T,pred] = minspantree(G,'Method','sparse')
Method
— 最小生成树算法
'dense'
(默认) | 'sparse'
最小生成树算法,指定为逗号分隔的对组,其中包含 'Method'
和下表中的选项之一。
选项 | 描述 |
---|---|
'dense' (默认值) | Prim 的算法。此算法从根节点开始,在遍历图时将边添加到树中。 |
'sparse' | Kruskal 的算法。此算法按权重对所有边排序,然后将不构成循环的边添加到树中。 |
Root
— 根节点
1
(默认) | 节点索引 | 节点名称
根节点,以逗号分隔的对组形式指定,该对组由 'Root'
和一个节点索引或节点名称组成。默认根节点是 1
。
如果
'Method'
是'dense'
(默认值),则根节点是起始节点。如果
'Method'
是'sparse'
,则根节点仅用于计算pred
,即前趋节点的向量。
您可以使用以下任一格式指定根节点:
值 | 示例 |
---|---|
标量节点索引 | 1 |
字符向量节点名称 | 'A' |
字符串标量节点名称 | "A" |
Type
— 最小生成树的类型
'tree'
(默认) | 'forest'
最小生成树的类型,指定为逗号分隔的对组,其中包含 'Type'
和下表中的选项之一。
选项 | 描述 |
---|---|
'tree' | 仅返回单一树。树包含根节点。 |
'forest' | 返回最小生成树的森林。换言之,指定 |
输出参量
T
— 最小生成树
graph
对象
最小生成树,以 graph
对象形式返回。
pred
— 前趋节点
向量
前趋节点,以节点索引的向量形式返回。pred(I)
是节点 I
的前趋节点的节点索引。按照惯例,pred(rootNode) = 0
。如果 Type
是 'tree'
,则对于与根节点不在同一分量中的所有节点 I
,pred(I) = NaN
。
pred
指定有向的最小生成树,所有边从根节点向外发出。
详细信息
最小生成树
对于连通图,生成树是一个子图,其中连接图中的每个节点但不包含任何循环。对于任一给定图,可以有许多生成树。通过为每条边分配权重,不同生成树均被分配一个表示其各边总权重的数字。然后,最小生成树就是各边的总权重最小的生成树。
对于边权重相等的图,所有生成树都是最小生成树,因为遍历 n
个节点需要 n-1
条边。
扩展功能
基于线程的环境
使用 MATLAB® backgroundPool
在后台运行代码或使用 Parallel Computing Toolbox™ ThreadPool
加快代码运行速度。
版本历史记录
在 R2015b 中推出
另请参阅
MATLAB 命令
您点击的链接对应于以下 MATLAB 命令:
请在 MATLAB 命令行窗口中直接输入以执行命令。Web 浏览器不支持 MATLAB 命令。
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)