教程目录

想要实际看看算法是如何工作的吗?

通过交互式可视化深入理解算法运行过程

查看算法可视化

有向无环图

介绍

有向无环图(Directed Acyclic Graph,简称DAG)是一种没有环的有向图。在DAG中,如果从顶点A出发沿着有向边行走,永远不可能回到顶点A,也就是说图中不存在环路。DAG在计算机科学中有着广泛的应用,尤其是在表示依赖关系、任务调度和执行顺序等场景中。

有向无环图中的关键概念包括:

  • 顶点(Vertex):图中的节点,通常用数字或字母标识。
  • 有向边(Directed Edge):从一个顶点指向另一个顶点的带方向连接,通常表示为有序对(u,v)。
  • 路径(Path):从一个顶点到另一个顶点经过的边的序列。
  • 拓扑排序(Topological Sort):将DAG中的所有顶点排列成一个线性序列,使得图中任何一条边(u,v)对应的顶点u在序列中都出现在v之前。
  • 源点(Source):入度为0的顶点,即没有边指向该顶点。
  • 汇点(Sink):出度为0的顶点,即没有从该顶点出发的边。

核心特性

  • 无环性:DAG中不存在环路,从任意顶点出发无法回到该顶点
  • 拓扑排序:总是可以将DAG的顶点排列成一个线性序列,使得所有边都从序列的前面指向后面
  • 依赖表示:非常适合表示依赖关系,如软件包依赖、任务调度的先后顺序
  • 可预测性:由于没有循环依赖,DAG的行为更加可预测
  • 单向流动:信息在DAG中只能沿一个方向流动,没有反馈循环
  • 层次结构:可以组织成层次结构,每一层的节点只依赖于更低层的节点

...

目录