有人可以用简单的术语向我解释一个定向的非循环图是什么？

有人可以用简单的术语向我解释一个定向的非循环图是什么？ 我看过维基百科，但它并没有真正让我看到它在编程中的使用。

graph =由节点组成的结构，它们之间用边连接

定向=节点（边）之间的连接有一个方向：A→B不同于B→A

acyclic =“non-circular”=通过跟踪边缘从一个节点移动到另一个节点，您将永远不会再次遇到同一个节点。

有向非循环图的一个很好的例子是一棵树。 但是请注意，并非所有有向无环图都是树。

在编程中使用有向无环图的例子包括或多或less的表示连通性和因果关系的东西。

例如，假设您有一个可在运行时configuration的计算pipe道。 举一个例子，假devise算A，B，C，D，E，F和G互相依赖：A取决于C，C取决于E和F，B取决于D和E，D取决于F.这可以表示为一个DAG。 一旦你在内存中的DAG，你可以写algorithm来：

  • 确保计算按照正确的顺序进行评估（ 拓扑sorting ）
  • 如果可以并行执行计算，但每个计算都有最大执行时间，则可以计算整个集合的最大执行时间

在许多其他事情之中。

在应用程序编程之外，任何像样的自动化构build工具（make，ant，scons等）都将使用DAG来确保程序组件的正确构build顺序。

点与线指向其他点

我看到很多答案表明DAG（定向非循环图）的含义，但没有答案的应用程序。 这是一个非常简单的 –

先决条件 – 在工程课程中，每个学生都面临着select符合要求的科目的任务，例如先决条件。 现在很清楚，如果没有algorithm[A]的必备课程，你就不能参加人工智能课程[B]。 因此B依赖于A或更好的条件A具有指向B的边。因此，为了到达节点B，必须访问节点A.很快将清楚的是，在将具有其前提条件的所有主题添加到图，它会变成一个有向无环图。

如果有一个循环，那么你永远不会完成一个课程：

大学的一个软件系统允许学生注册课程，可以将学科build模为节点，以确保学生在注册当前课程之前已经采取了先决条件。

我的教授给了这个比喻，最好的帮助我理解DAG，而不是使用一些复杂的概念！

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

有向无环图（DAG）具有以下与其他graphics有区别的属性：

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

那么，我现在可以想到一个用法 – DAG（称为等待图 – 更多技术细节 ）在检测死锁方面很方便，因为它们说明了一组进程和资源之间的依赖关系（两者都是DAG中的节点） 。 检测到周期时会发生死锁。

我希望这有帮助。

干杯

有几个答案给出了使用graphics的例子（例如networkingbuild模），并且你问“这与编程有什么关系？”。

这个子问题的答案是，它与编程没有太大的关系。 这与解决问题有关。

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

我假设你已经知道基本的graphics术语; 否则你应该从图论的文章开始。

定向是指边缘（连接）具有方向的事实。 在图中，这些方向用箭头表示。 相反的是一个无向图，其边不指定方向。

非循环意味着，如果从任意任意节点X开始，遍历所有可能的边，则不必返回到已经使用的边。

几个应用：

  • 电子表格; 这在DAG文章中有解释。
  • 版本控制 ：如果你看一下该页面的图表，你会发现版本控制代码的发展是直接的（在图中是“向下”的），非循环的（它永远不会回升） 。
  • 家谱：指导（你是你父母的孩子，而不是其他方式）和非循环（你的祖先永远不可能是你的后裔）。

在编程中使用各种各样的graphics来模拟各种不同的现实世界的关系。 例如，社交networking通常由图表表示（在这种情况下是循环的）。 同样，networking拓扑，家庭树木，航空公司的路线，…

从一个源代码甚至三个地址（TAC）代码的angular度来看，你可以很容易地在这个页面上看到问题…

http://cgm.cs.mcgill.ca/~hagha/topic30/topic30.html#Exptree

如果转到expression式树节，然后向下翻页，则会显示树的“拓扑sorting”，以及如何评估expression式的algorithm。

所以在这种情况下，您可以使用DAG来评估expression式，这是很方便的，因为评估通常是被解释的，并且使用这样的DAG评估器将会使得简单的解释器更快，因为它不会推动并popup到堆栈，常见的子expression式。

非古埃及（即英语）计算DAG的基本algorithm是这样的：

1）使你的DAG对象如此

您需要一个实时列表，该列表包含当前所有的DAG节点和DAG子expression式。 DAG子expression式是DAG节点，或者也可以将其称为内部节点。 我的意思是现场DAG节点是，如果你分配给一个variablesX然后它变得活着。 然后使用X的公共子expression式使用该实例。 如果再次分配了X，则创build一个新的DAG NODE，并将其添加到实时列表中，旧的X将被删除，因此下一个使用X的子expression式将引用新实例，因此不会与子expression式冲突只是使用相同的variables名称。

一旦将variables赋给variablesX，那么在赋值点上生活的所有DAG子expression式节点都会变成非活的，因为新赋值使用旧值使子expression式的含义无效。 

class Dag { TList LiveList; DagNode Root; } // In your DagNode you need a way to refer to the original things that // the DAG is computed from. In this case I just assume an integer index // into the list of variables and also an integer index for the opertor for // Nodes that refer to operators. Obviously you can create sub-classes for // different kinds of Dag Nodes. class DagNode { int Variable; int Operator;// You can also use a class DagNode Left; DagNode Right; DagNodeList Parents; }

所以你要做的就是在自己的代码中遍历你的树，比如源代码中的expression式树。 例如，调用现有的节点XNode。

因此，对于每个XNode，您需要决定如何将其添加到DAG中，并且可能已经存在于DAG中。

这是非常简单的伪代码。 不打算编译。 

 DagNode XNode::GetDagNode(Dag dag) { if (XNode.IsAssignment) { // The assignment is a special case. A common sub expression is not // formed by the assignment since it creates a new value. // Evaluate the right hand side like normal XNode.RightXNode.GetDagNode(); // And now take the variable being assigned to out of the current live list dag.RemoveDagNodeForVariable(XNode.VariableBeingAssigned); // Also remove all DAG sub expressions using the variable - since the new value // makes them redundant dag.RemoveDagExpressionsUsingVariable(XNode.VariableBeingAssigned); // Then make a new variable in the live list in the dag, so that references to // the variable later on will see the new dag node instead. dag.AddDagNodeForVariable(XNode.VariableBeingAssigned); } else if (XNode.IsVariable) { // A variable node has no child nodes, so you can just proces it directly DagNode n = dag.GetDagNodeForVariable(XNode.Variable)); if (n) XNode.DagNode = n; else { XNode.DagNode = dag.CreateDagNodeForVariable(XNode.Variable); } return XNode.DagNode; } else if (XNode.IsOperator) { DagNode leftDagNode = XNode.LeftXNode.GetDagNode(dag); DagNode rightDagNode = XNode.RightXNode.GetDagNode(dag); // Here you can observe how supplying the operator id and both operands that it // looks in the Dags live list to check if this expression is already there. If // it is then it returns it and that is how a common sub-expression is formed. // This is called an internal node. XNode.DagNode = dag.GetOrCreateDagNodeForOperator(XNode.Operator,leftDagNode,RightDagNode) ); return XNode.DagNode; } }

所以这是看待它的一种方法。 树的基本步行，只是join和引用Dag节点。 dag的根就是例如树根返回的DagNode。

显然，示例过程可以分解成更小的部分或者作为具有虚拟function的子类。

至于sortingDag，你从左到右通过每个DagNode。 换句话说，遵循DagNodes左手边，然后是右手边。 数字是相反的。 换句话说，当你到达一个没有子节点的DagNode的时候，给这个节点分配当前的sorting数字并且增加sorting数字，这样recursion解除数字按照升序排列。

此示例仅处理具有零个或两个子节点的树。 显然有些树有两个以上的孩子，所以逻辑依然是一样的。 而不是计算左右，从左到右计算等… 

 // Most basic DAG topological ordering example. void DagNode::OrderDAG(int* counter) { if (this->AlreadyCounted) return; // Count from left to right for x = 0 to this->Children.Count-1 this->Children[x].OrderDag(counter) // And finally number the DAG Node here after all // the children have been numbered this->DAGOrder = *counter; // Increment the counter so the caller gets a higher number *counter = *counter + 1; // Mark as processed so will count again this->AlreadyCounted = TRUE; }

如果您知道编程中的树是什么，那么编程中的DAG是相似的，但它们允许一个节点拥有多个父节点。 当你想让一个节点不仅仅是一个父节点，而且还没有一个具有周期的普通图的结点问题的时候，这可能会很方便。 您仍然可以轻松导航DAG，但有多种方式可以回到根目录（因为可以有多个父项）。 一个单一的DAG通常可以有多根，但实际上可能会更好，只要坚持一根，就像一棵树。 如果您了解OOP中的单一inheritance和多重inheritance，那么您就知道树与DAG。 我已经在这里回答了 。

这个名字告诉你大部分你需要知道它的定义：这是一个graphics，每条边只在一个方向上stream动，一旦你爬下一条边，你的路就不会返回到你刚刚离开的顶点。

我不能说所有的用途（维基百科帮助那里），但对我来说，确定资源之间的依赖关系时，DAG是非常有用的。 例如，我的游戏引擎将所有加载的资源（材质，纹理，着色器，明文，parsing的JSON等）表示为一个DAG。 例：

一个材质是N GL程序，每个程序需要两个着色器，每个着色器需要一个明文着色器源代码。 通过将这些资源表示为DAG，我可以轻松地查询现有资源的图表以避免重复的负载。 假设您需要使用相同源代码的几种材质来使用顶点着色器。 重新加载源代码并为每个用途重新编译着色器是非常浪费的，因为只能为现有资源build立新的边界。 通过这种方式，你也可以使用图来确定是否有任何东西依赖于某个资源，如果不是，则删除它并释放它的内存，实际上这种情况几乎是自动发生的。

通过扩展，DAG对expression数据处理stream水线非常有用。 非循环本质意味着您可以安全地编写上下文处理代码，该代码可以沿着顶点的边缘指向下一个指针，而不会再次出现相同的顶点。 VVVV ， Max MSP或Autodesk Maya基于节点的接口等可视化编程语言都依赖于DAG。

一个有向无环图是有用的，当你想表示一个有向无环图！ 典型的例子是家谱或族谱。

Interesting Posts