minspantree
图的最小生成树
描述
例子
立方体图的最小生成树
创建和绘制一个立方体图和加权边缘。
s = [1 1 1 2 4 5 3 6 7 8 8 8];4 t = [3 2 3 4 5 6 7 2 6 7 5];重量= [100 10 10 10 10 20 30 50 70 10];图G = (s t重量);p =情节(G,“EdgeLabel”,G.Edges.Weight);
计算并绘制图的最小生成树的图。T
包含相同的节点G
,但边缘的一个子集。
(T, pred) = minspantree (G);突出(p T)
从根节点指定最小生成森林
多个组件创建和绘制图表。
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 =情节(G,“布局”,“分层”);
找到图的最小生成森林,开始节点我
。突出情节的森林。图的节点名称进行到最小生成树图。
(T, pred) = minspantree (G,“类型”,“森林”,“根”findnode (G,“我”));突出(p T)
用前任节点的向量,pred
,创建一个版本的最小生成森林。这棵树的边缘都是直接从根节点在每个组件(节点我
和一个
)。
rootedTree =有向图(pred (pred ~ = 0),找到(pred ~ = 0), [], G.Nodes.Name);情节(rootedTree)
输入参数
G
- - - - - -输入图
图
对象
输入图,指定为一个图
对象。使用图
创建一个无向图对象。
例子:图G = (1、2)
名称-值参数
指定可选的双参数作为Name1 = Value1,…,以=家
,在那里的名字
参数名称和吗价值
相应的价值。名称-值参数必须出现在其他参数,但对的顺序无关紧要。
R2021a之前,用逗号来分隔每一个名称和值,并附上的名字
在报价。
例子:(T, pred) = minspantree (G,‘法’,‘稀疏’)
方法
- - - - - -最小生成树算法
“密集”
(默认)|“稀疏”
最小生成树算法,指定为逗号分隔组成的“方法”
其中一个选项表中。
选项 | 描述 |
---|---|
“密集” (默认) |
一本正经的算法。该算法从根节点开始,将边缘添加到树遍历图。 |
“稀疏” |
克鲁斯卡算法。这个算法排序所有的边缘按重量,然后将它们添加到树如果他们不创建一个循环。 |
根
- - - - - -根节点
1
(默认)|节点索引|节点名称
根节点,指定为逗号分隔组成的“根”
和节点索引或节点名称。默认的根节点1
。
如果
“方法”
是“密集”
(默认),然后根节点开始节点。如果
“方法”
是“稀疏”
根节点,那么只用于计算pred
向量的前任节点。
您可以指定根节点在任何这些格式:
价值 | 例子 |
---|---|
标量节点索引 | 1 |
特征向量节点名 | “一个” |
字符串标量节点名 | “一个” |
类型
- - - - - -类型的最小生成树
“树”
(默认)|“森林”
类型的最小生成树,指定为逗号分隔组成的“类型”
其中一个选项表中。
选项 | 描述 |
---|---|
“树” |
只有一个返回树。包含根节点的树。 |
“森林” |
返回一个最小生成树的森林。换句话说,指定 |
输出参数
T
——最小生成树
图
对象
最小生成树,作为一个返回图
对象。
pred
——前任节点
向量
前任节点,作为一个向量返回的节点指标。pred(我)
节点索引节点的前任吗我
。按照惯例,pred (rootNode) = 0
。如果类型
是“树”
,然后pred (I) = NaN
对所有节点我
不是在同一个组件作为根节点。
pred
指定一个版本的最小生成树,与所有边缘直接从根节点。
更多关于
最小生成树
连通图的生成树是一个连接的子图中的每个节点图,但不包含周期。可以有许多生成树对于任何给定的图。通过将重量分配给每条边,不同的生成树被分配一个数字的总重量。然后生成树的最小生成树的边缘有最少的总重量。
对于平等边的图,所有生成树是最小生成树,因为穿越n
节点需要n - 1
边缘。
版本历史
另请参阅
MATLAB命令
你点击一个链接对应MATLAB命令:
运行该命令通过输入MATLAB命令窗口。Web浏览器不支持MATLAB命令。万博1manbetx
你也可以从下面的列表中选择一个网站:
表现最好的网站怎么走吗
选择中国网站(中文或英文)最佳站点的性能。其他MathWorks国家网站不优化的访问你的位置。