Topological Order

释义 Definition

拓扑序（拓扑排序的结果）：在一个有向无环图（DAG）中，把所有顶点排成一个线性序列，使得对每条有向边 u → v，顶点 u 都出现在 v 之前。常用于表示依赖关系（先做什么、后做什么）。

（注：在数学里也可指偏序集的“线性扩展”，但计算机科学语境最常见的是图论中的拓扑序。）

发音 Pronunciation (IPA)

/ˌtɑːpəˈlɑːdʒɪkəl ˈɔːrdər/

例句 Examples

A topological order helps us schedule tasks with dependencies.
拓扑序能帮助我们安排有依赖关系的任务顺序。

If the graph has a cycle, then no topological order exists, so the build system cannot determine a valid compilation sequence.
如果图中存在环，就不存在拓扑序，因此构建系统无法确定有效的编译顺序。

词源 Etymology

topological 来自 topology（拓扑学），源于希腊语 topos（地点）+ -logia（学问）；order 表示“顺序/排序”。“拓扑序”这一术语把“结构关系（边的先后约束）”转化为“线性顺序”的概念，因而得名。

相关词 Related Words

• Topological Sort
• Directed Acyclic Graph
• Dependency Graph
• Partial Order
• Linear Extension
• Kahn's Algorithm
• Depth-First Search

文学与经典作品 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常称 CLRS）— 在有向无环图章节中用“topological order”描述拓扑排序输出序列。
• The Algorithm Design Manual（Steven S. Skiena）— 在图算法与调度/依赖问题中讨论拓扑序。
• Algorithms（Robert Sedgewick & Kevin Wayne）— 在DAG与排序相关内容中使用该术语说明先后约束的线性化。