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

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

1> Roland Bouma..：

---

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

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

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

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

---

所有有向树都是DAG,但并非所有DAG都是树.DAG A-> B,A-> C,B-> C不能表示为树,因为节点C具有多于一个父节点.

---

它通常用箭头表示，但实际上只是A和B之间存在关系。在您的程序中，这可能是邻接矩阵中代表这两个节点的索引中的真值。

---

边缘的定向性不是将DAG与树分开的唯一特征.与树不同,DAG可以具有多于| V | -1的边.例如,A-> B,A-> C,B-> D,C-> D是DAG但显然不是树,因为它具有相同数量的边和节点.

2> smartcaveman..：

---

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

---

......在一个方向

---

这是最好的答案之一,因为它是一种简单的方式来描述隐藏在复杂术语中的简单概念(如果我们提出这个问题,我们可能不知道图论......甚至需要知道).我的变体会像"跳酒,你永远不能去同一个酒吧两次".虽然来自另一个答案的家族树示例可能在概念上更简单,特别是对于我们这些不是大学生或酗酒者的人.

---

您必须包括“线不形成循环的地方”，否则，您只是在描述有向图，而不是有向无环图。

3> human.js..：

---

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

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

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

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

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

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

---

这应该是排名最高的答案.简单的类比并没有使用OP无法轻易理解的教科书定义.

4> Jason S..：

---

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

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

确保以正确的顺序计算计算(拓扑排序)

如果计算可以并行完成但每次计算都有最大执行时间,则可以计算整个集合的最大执行时间

在许多其他事情.

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

5> Jonathon Fau..：

---

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

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

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

6> Arnkrishn..：

---

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

他们的边缘显示方向.

他们没有周期.

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

我希望这有帮助.

干杯

7> Johannes Sas..：

---

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

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

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

几个应用:

电子表格; 这在DAG文章中有解释.

修订控制:如果您查看该页面中的图表,您将看到修订控制代码的演变是定向的(它在本图中"向下")和非循环(它永远不会回到"向上") .

家谱:它是针对的(你是你父母的孩子,而不是相反)和非循环(你的祖先永远不能成为你的后代).