有向无环图
介绍
有向无环图(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中只能沿一个方向流动,没有反馈循环
- 层次结构:可以组织成层次结构,每一层的节点只依赖于更低层的节点
...