Main Content

toposort

有向无环图的拓扑顺序

全页折叠

语法

n = toposort(G)
n = toposort(G,'Order',algorithm)
[n,H] = toposort(___)

说明

n = toposort(G) 返回 G 中符合以下条件的节点拓扑顺序：G 中每条边 (n(i),n(j)) 的 i < j。有向图 G 不能包含任何循环。

示例

n = toposort(G,'Order',algorithm) 指定排序算法。例如，toposort(G,'Order','stable') 对节点使用基于字典编纂顺序的稳定排序算法。

示例

[n,H] = toposort(___) 还返回有向图 H，其节点采用给定的拓扑顺序。您可以使用上述语法中的任何输入参量组合。

示例

示例

全部折叠

打开实时脚本

创建并绘制一个图，它表示大学数学课程的进阶顺序。两个课程之间的边表示课程要求。

A = [0 1 1 0 0 0 0
     0 0 0 1 0 0 0
     0 1 0 1 0 0 1
     0 0 0 0 1 1 0
     0 0 0 0 0 0 0
     0 0 0 0 1 0 0
     0 0 0 0 1 0 0];
names = {'Calculus I','Linear Algebra','Calculus II', ...
    'Multivariate Calculus','Topology', ...
    'Differential Equations','Real Analysis'};
G = digraph(A,names);
plot(G)

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

找出课程的拓扑排序来确定正确的课程完成顺序。

N = toposort(G)
N = 1×7

     1     3     7     2     4     6     5


G.Nodes.Name(N,:)
ans = 7x1 cell
    {'Calculus I'            }
    {'Calculus II'           }
    {'Real Analysis'         }
    {'Linear Algebra'        }
    {'Multivariate Calculus' }
    {'Differential Equations'}
    {'Topology'              }
打开实时脚本

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

rng default;
A = tril(sprand(10, 10, 0.3), -1)~=0;
G = digraph(A);
[~,G] = toposort(G);
plot(G)

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

找出图节点的拓扑排序。即使 G 已为拓扑顺序 (1 2 3 4 5 6 7 8 9 10)，toposort 仍会对节点重新排序。

toposort(G)
ans = 1×10

     2     1     4    10     9     8     5     7     3     6

指定 Order 作为 'stable' 以使用稳定排序算法，这样会按照较小索引优先的顺序对节点进行排序。稳定排序不对已形成拓扑顺序的 G 进行重新排列。

toposort(G,'Order','stable')
ans = 1×10

     1     2     3     4     5     6     7     8     9    10

输入参数

全部折叠

输入图，指定为 digraph 对象。G 必须为有向无环图。使用 isdag 确认 G 不包含循环。

使用 digraph 创建有向图。

示例: G = digraph([1 2],[2 3])

排序算法，指定为 'fast' 或 'stable'：

'fast'（默认值）

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

如果 G 已为拓扑顺序，此方法仍可能会对各节点重新排序。

'stable'

基于字典编纂顺序。n(1) 是具有最小索引的节点，n(2) 是具有次小索引的节点（在存在 n(1) 的情况下），以此类推。

如果 G 已为拓扑顺序，则 H 不变，且 n 是 1:numnodes(G)。

示例: [n,H] = toposort(G,'Order','stable')

输出参量

全部折叠

节点索引，以行向量形式返回。

按拓扑方式排序的图，以 digraph 对象形式返回。H 是与 G 相同的图，但根据 n 对节点进行了重新排序。

详细信息

全部折叠

拓扑顺序

有向图的拓扑排序即是对图中节点进行排序，使得每个节点都出现在其后继节点（后代）之前。

假设具有一个有向图，其节点表示任务，边表示各任务完成顺序的依赖关系。对于此类图，对图节点进行拓扑排序会形成一个有效的任务执行序列。

版本历史记录

在 R2015b 中推出

另请参阅

| |