什么是有向无环图

发布网友发布时间：2022-05-10 03:03

我来回答

共2个回答

热心网友时间：2023-07-27 01:08

有向无环图指的是一个无回路的有向图。如果有一个非有向无环图，且A点出发向B经C可回到A，形成一个环。将从C到A的边方向改为从A到C，则变成有向无环图。有向无环图的生成树个数等于入度非零的节点的入度积。

如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。

因为有向图中一个点经过两种路线到达另一个点未必形成环，因此有向无环图未必能转化成树，但任何有向树均为有向无环图。

扩展资料

检查一个有向图是否存在环要比无向图复杂。对于无向图来说，若深度优先遍历过程中遇到回边，则必定存在环；而对于有向图来说，这条回边有可能是指向深度优先生成森林中另一棵生成树上顶点的弧。

有向无环图是描述一项工程或系统的进行过程的有效工具。

除最简单的情况之外，几乎所有的工程都可分为若干个称作活动的子工程，而这些子工程之间，通常受着一定条件的约束，如其中某些子工程的开始必须在另一些子工程完成之后。

参考资料来源：百度百科-有向无环图

热心网友时间：2023-07-27 01:09

如图所示为一个非有向无环图，因为A点出发向B经C可回到A，形成一个环。将从C到A的边方向改为从A到C，则变成有向无环图。
中文名
有向无环图
外文名
DAG （Directed acyclic graph）
在图论中，如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。
因为有向图中一个点经过两种路线到达另一个点未必形成环，因此有向无环图未必能转化成树，但任何有向树均为有向无环图。

性质：有向无环图的生成树个数等于入度非零的节点的入度积。