主要内容

toposort

有向无环图的拓扑顺序

折叠所有页面

语法

n = topsort (G)
n = topsort (G，'Order'，算法)
[n,H] = topsort (＿＿＿）

描述

例子

n= toposort (G）返回拓扑顺序的节点G这样I < j对于每条边(n (i)、n (j))在G。有向图G不能有任何循环。

例子

n= toposort (G“秩序”,算法）指定排序算法。例如,toposort (G,“秩序”,“稳定”)使用基于节点的字典顺序的稳定排序算法。

例子

(n，H= topsort (＿＿＿）另外返回有向图H它的节点是给定的拓扑顺序。您可以使用以前语法中的任何输入参数组合。

例子

全部折叠

打开实时脚本

创建并绘制代表大学数学课程进度的图表。两门课程之间的边表示课程要求。

A = [0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0];名称= {学我的，“线性代数”，“微积分二世”，…“多元微积分”，“拓扑结构”，…“微分方程”，“实分析”};G =有向图(A，人名);情节(G)

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

找到课程的拓扑排序，以确定它们应该完成的正确顺序。

N = topsort (G)
N =1×71 3 7 2 4 6 5
G.Nodes.Name (N,:)
ans =7 x1细胞{“微积分I”}{“微积分II”}{“实分析”}{“线性代数”}{“多元微积分”}{“微分方程”}{“拓扑”}
打开实时脚本

使用逻辑邻接矩阵创建有向图，然后绘制该图。

rng默认的;A = tril(spand (10,10,0.3)， -1)~=0;G =有向图(A);[~，G] = topsort (G);情节(G)

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

找出图节点的拓扑排序。尽管G已经是拓扑顺序了，(1 2 3 4 5 6 7 8 9 10)，toposort重新排序节点。

toposort (G)
ans =1×102 1 4 10 9 8 5 7 3 6

指定订单作为“稳定”使用稳定排序算法，使排序先对索引较小的节点排序。稳定排序不重新排列G如果它已经是拓扑顺序。

toposort (G,“秩序”，“稳定”）
ans =1×101 2 3 4 5 6 7 8 9 10

输入参数

全部折叠

输入图形，指定为a有向图对象。G必须是有向无环图。使用isdag为了证实这一点G不包含循环。

使用有向图创建有向图。

例子:G =有向图([1 2]，[2 3])

排序算法，指定为“快”或“稳定”：

“快”(默认)

基于深度优先搜索。一个节点在考虑了它的所有后代之后被添加到列表的开头。

如果G已经是拓扑顺序，此方法仍然可能对节点重新排序。
“稳定”

基于字典顺序的。n (1)是索引最小的节点，n (2)下一个最小值n (1)等等。

如果G是拓扑顺序的吗H是不变的n是1: numnodes (G)。

例子:[n,H] = topsort (G，'有序'，'稳定')

输出参数

全部折叠

节点索引，作为行向量返回。

拓扑排序图，返回为有向图对象。H是同一个图形吗G，但节点按照n。

更多关于

全部折叠

拓扑顺序

有向图的拓扑排序是图中节点的排序，使得每个节点出现在其后继节点(后代节点)之前。

考虑一个有向图，其节点表示任务，其边表示某些任务必须在其他任务之前完成的依赖关系。对于这样的图，图节点的拓扑排序产生一个有效的序列，其中任务可以执行。

版本历史

在R2015b中引入

另请参阅

||