Main Content

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

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. The axes 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. The axes 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 不变,且 n1:numnodes(G)

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

输出参数

全部折叠

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

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

详细信息

全部折叠

拓扑顺序

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

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

另请参阅

| |

在 R2015b 中推出