视频字幕
有向无环图，简称DAG，是图论中的一个重要概念。它是一种有向图，但与普通有向图不同的是，DAG中不存在任何环路。这意味着从任意一个顶点出发，沿着有向边行走，永远无法回到起始顶点。
DAG具有几个重要特性。首先是无环性，这是DAG最基本的特征。其次，DAG可以进行拓扑排序，将顶点按照依赖关系排成线性序列。第三，DAG具有明确的层次结构，我们可以将顶点分为不同的层级。最后，DAG常用来表示任务间的依赖关系。
拓扑排序是对有向无环图顶点的一种线性排序。排序的结果保证对于图中的每一条有向边，起点都在终点之前出现。拓扑排序在任务调度、课程安排、编译依赖等场景中有重要应用。这里展示的是一个典型的拓扑排序结果。
通过对比可以清楚看出DAG和含环图的区别。左边的DAG中，所有的边都指向同一个方向，不存在回路。而右边的含环图中，存在一个明显的环路，可以从任意顶点出发沿着有向边回到起始点。这个根本差异决定了两种图的不同应用场景。
DAG在现实世界中有着广泛的应用。在项目管理中，我们可以用DAG来表示任务之间的依赖关系，确保任务按正确的顺序执行。在编译系统中，DAG用来表示模块间的依赖关系。在数据处理流水线中，DAG描述数据的流向和处理步骤。这些应用都利用了DAG无环和有序的特性。