# toposort

有向无环图的拓扑顺序

函数库: TyMath

# 语法

n, H = toposort(G)
n, H = toposort(G, algorithm)

# 说明

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

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

# 示例

节点的拓扑排序

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

using TyMath
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);

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

N = toposort(G)[1]

N = 7-element Vector{Int64}:
 1
 3
 7
 2
 4
 6
 5

G.Nodes.nodeNames[N,:]

ans = 7×1 Matrix{String}:
 "Calculus I"
 "Calculus II"
 "Real Analysis"
 "Linear Algebra"
 "Multivariate Calculus"
 "Differential Equations"
 "Topology"

稳定拓扑排序

使用逻辑邻接矩阵创建有向图。

using TyMath
G=DiGraph([6,7,7,7,7,8,9,9,9,10,10,10,10,10],[4,1,2,3,6,5,2,7,8,1,2,4,7,8]);
G = toposort(G)[2];

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

toposort(G)[1]

ans = 10-element Vector{Int64}:
  2
  1
  4
 10
  9
  8
  5
  7
  3
  6

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

toposort(G,"stable")

ans = 10-element Vector{Int64}:
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10

# 输入参数

G - 输入图

DiGraph 对象

输入图，指定为 DiGraph 对象。可使用 DiGraph 创建有向图对象。

示例： G = DiGraph([1,2],[2,3])

algorithm - 排序算法

"fast" （默认） | "stable"

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

"fast"（默认值）

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

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

'stable'

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

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

示例： n,H = toposort(G,"stable")

# 输出参数

n - 节点索引

行向量

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

H - 拓扑排序图

DiGraph 对象

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

# 详细信息

拓扑顺序

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

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

# 另请参阅

DiGraph | isdag | reordernodes