有人能用简单的语言向我解释一个有向无环图是什么？

Question

有人能用简单的语言向我解释一个有向无环图是什么？我看过维基百科,但它并没有真正让我看到它在编程中的用途.

Answer 1

graph =由节点组成的结构,它们通过边缘相互连接

directed =节点(边)之间的连接有一个方向:A - > B与B - > A不同

acyclic ="non-circular"=通过跟随边缘从节点移动到节点,第二次永远不会遇到相同的节点.

有向无环图的一个很好的例子是树.但请注意,并非所有有向无环图都是树.

Answer 2

带有指向其他点的线条的点

Answer 3

我看到许多答案表明DAG(有向无环图)的含义,但没有答案的应用程序.这是一个非常简单的 -

先决条件图 - 在工程课程中,每个学生都面临着选择遵循诸如先决条件等要求的科目的任务.现在很明显,如果没有算法[A]的必修课程,就不能参加人工智能课程[B].因此B依赖于A或者更好地表示A具有指向B的边缘.因此,为了到达节点B,您必须访问节点A.很快就会清楚地将所有具有其先决条件的主题添加到图形中,它将变成一个有向无环图.

如果有一个循环,那么你永远不会完成一个课程:p

大学中允许学生注册课程的软件系统可以将主题建模为节点,以确保学生在注册当前课程之前已经参加了必修课程.

我的教授给出了这个类比,它最好帮助我理解DAG,而不是使用一些复杂的概念!

另一个实时示例 - > 实时示例DAG如何在版本系统中使用

Answer 4

在编程中使用有向无环图包括或多或少表示连通性和因果关系的任何东西.

例如,假设您有一个可在运行时配置的计算管道.作为一个例子,假设计算A,B,C,D,E,F和G彼此依赖:A取决于C,C取决于E和F,B取决于D和E,D取决于F.这可以表示为DAG.将DAG放入内存后,您可以编写算法:

• 确保以正确的顺序计算计算(拓扑排序)
• 如果计算可以并行完成但每次计算都有最大执行时间,则可以计算整个集合的最大执行时间

在许多其他事情.

在应用程序编程领域之外,任何体面的自动构建工具(make,ant,scons等)都将使用DAG来确保程序组件的正确构建顺序.

Answer 5

几个答案给出了使用图形的例子(例如网络建模),你已经问过"这与编程有什么关系？".

该子问题的答案是它与编程没有多大关系.它与解决问题有关.

就像链表是用于某些类问题的数据结构一样,图表对于表示某些关系很有用.链接列表,树,图和其他抽象结构只与编程有关,因为您可以在代码中实现它们.它们存在于更高的抽象层次.它不是关于编程,而是关于在问题解决方案中应用数据结构.

Answer 6

有向无环图(DAG)具有以下属性,可将它们与其他图区分开来:

1. 他们的边缘显示方向.
2. 他们没有周期.

好吧,我现在可以想到一个用途--DAG(称为Wait-For-Graphs - 更多技术细节)在检测死锁时非常方便,因为它们说明了一组进程和资源(都是DAG中的节点)之间的依赖关系.检测到循环时会发生死锁.

我希望这有帮助.

干杯

Answer 7

我假设你已经知道了基本的图形术语; 否则你应该从关于图论的文章开始.

定向是指边(连接)具有方向的事实.在图中,这些方向用箭头表示.相反的是无向图,其边不指定方向.

非循环意味着,如果从任意节点X开始并遍历所有可能的边缘,则无法返回到X而不返回已使用的边缘.

几个应用:

• 电子表格; 这在DAG文章中有解释.
• 修订控制:如果您查看该页面中的图表,您将看到修订控制代码的演变是定向的(它在本图中"向下")和非循环(它永远不会回到"向上") .
• 家谱:它是针对的(你是你父母的孩子,而不是相反)和非循环(你的祖先永远不能成为你的后代).

Answer 8

DAG 是一个图形，其中所有内容都沿同一方向流动，并且没有节点可以引用回自身。

想想祖先树；它们实际上是 DAG。

所有 DAG 都有

• 节点（存储数据的地方）
• 有向边（指向同一方向）
• 祖先节点（没有父母的节点）
• 叶子（没有孩子的节点）

DAG 不同于树。在树状结构中，每两个节点之间必须有唯一的路径。在 DAG 中，一个节点可以有两个父节点。

这是一篇关于 DAG的好文章。我希望这有帮助。