有向无环图 (DAG)

定义

在计算机科学和数学中，有向无环图 (DAG) 指一种无向循环的有向图。

说明

在图论中，图指一组通过称为边的直线连接的顶点。在有向图或有向无环图中，每条边都与从起始顶点到结束顶点的方向相关联。如果我们沿着边的方向行进，并且发现沿着任何路径都没有形成闭合回路，我们称之为无有向循环。形成的图是有向无环图。

DAG 始终按照拓扑顺序排列，即对于图中的每条边，边的起始顶点在序列中的出现早于边的结束顶点。

示例

在上面的有向图中，如果我们查找自任意节点（例如 u）的路径，我们将永远找不到返回 u 的路径。因此，这是一个 DAG。

应用领域

DAG 的一些主要应用领域有 −

• 计算机网络中的路由

• 作业调度

• 数据处理

• 系谱

• 引文图

Moumita

更新于：22-2月-2021

14K+ 浏览次数

开始你的 职业生涯

完成课程认证

开始