有人能简单地解释一下什么是有向无环图吗？

有人能简单地解释一下什么是有向无环图吗？我看过维基百科，但它并没有真正让我看到它在编程中的用途。

68716 次浏览
小开

graph = structure consisting of nodes, that are connected to each other with edges

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

Acycles = “ non-Circle”= 通过沿着边从一个节点移动到另一个节点，您将永远不会再次遇到同一个节点。

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

小开

当你想代表一个有向无环图的时候有向无环图是很有用的！典型的例子是家谱或家谱。

小开

有向无环图(DAG)具有以下特性，这些特性区别于其他图:

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

Well, I can think of one use right now - DAG (known as 等待图表 - more 技术细节) are handy in detecting deadlocks as they illustrate the dependencies amongst a set of processes and resources (both are nodes in the DAG). Deadlock would happen when a cycle is detected.

小开

在编程中，各种各样的图被用来建模各种不同的现实世界关系。例如，一个社交网络通常由一个图表示(在这种情况下是循环的)。同样，网络拓扑，家族树，航线，..。

小开

Example uses of a directed acyclic graph in programming include more or less anything that represents connectivity and causality.

例如，假设您有一个在运行时可配置的计算管道。例如，假设计算 A、 B、 C、 D、 E、 F 和 G 相互依赖: A 依赖于 C，C 依赖于 E 和 F，B 依赖于 D 和 E，D 依赖于 F。这可以表示为 DAG。一旦你在内存中有 DAG，你可以写算法:

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

among many other things.

在应用程序编程领域之外，任何像样的自动构建工具(make、 ant、 scons 等)都将使用 DAGs 来确保程序组件的正确构建顺序。

小开

有几个答案给出了使用图表的例子(例如网络建模) ，你问过“这和编程有什么关系?”.

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

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

小开

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

Directed 指的是边(连接)有方向这一事实。在图中，箭头显示了这些方向。相反的是无向图，它的边不指定方向。

无环 意味着，如果从任意节点 X 开始并遍历所有可能的边，那么如果不返回已经使用的边，就不能返回到 X。

Several applications:

  • 电子表格; 这在 DAG文章中有解释。
  • 修订控制 : 如果你看一下那个页面中的图表，你会发现修订控制代码的演化是有方向的(在这个图表中是“向下”的)和非循环的(它永远不会回到“向上”的)。
  • Family tree: it's directed (you are your parents' child, not the other way around) and acyclic (your ancestors can never be your descendant).
小开
最佳答案

带有指向其他点的线的点

小开

从源代码甚至三个地址(TAC)代码的角度来看，您可以很容易地在这个页面上看到问题..。

Http://cgm.cs.mcgill.ca/~hagha/topic30/topic30.html#exptree

如果你转到表达式树部分，然后向下翻一页，它会显示树的“拓扑排序”，以及如何计算表达式的算法。

所以在这种情况下，你可以使用 DAG 来计算表达式，这很方便，因为计算是正常解释的，使用这样的 DAG 计算器将使简单的解释器在主体上更快，因为它不会推送和弹出到堆栈，也因为它消除了常见的子表达式。

用非古埃及语(即英语)计算 DAG 的基本算法如下:

1)让你的 DAG 对象像这样

您需要一个活动列表，该列表包含所有当前活动 DAG 节点和 DAG 子表达式。DAG 子表达式是 DAG 节点，或者也可以称之为内部节点。我所说的活动 DAG 节点是指，如果你赋值给一个变量 X，那么它就变成活动的。然后使用 X 的公共子表达式使用该实例。如果再次分配 X，那么创建一个 NEW DAG NODE 并将其添加到活动列表中，旧的 X 将被删除，因此使用 X 的下一个子表达式将引用新实例，因此不会与仅使用相同变量名的子表达式发生冲突。

一旦你赋值给一个变量 X，那么在赋值点活动的所有 DAG 子表达式节点都会变成非活动的，因为新的赋值使得使用旧值的子表达式的意义无效。

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;
}

因此，您要做的就是在自己的代码中遍历树，例如，在源代码中遍历表达式树。例如，调用现有节点 XNodes。

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

This is very simple pseudo code. Not intended for compilation.

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;
}
}

这是一种看待问题的方式。树的基本遍历，只是添加和引用 Dag 节点。例如，dag 的根就是树的根返回的 DagNode。

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

至于对 DagNode 进行排序，您将从左到右遍历每个 DagNode。也就是说，沿着 DagNodes 的左手边，然后右手边。这些数字是反过来分配的。换句话说，当您到达一个没有子节点的 DagNode 时，为该节点分配当前的排序号并递增排序号，这样当递归解除时，数字将按递增顺序被分配。

此示例只处理具有零个或两个子节点的树。显然，有些树的节点有两个以上的子节点，因此逻辑仍然是相同的。不要计算左和右，而是从左到右计算等等。.

// 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;
}
小开

如果您知道编程中的树是什么，那么编程中的 DAGs 是类似的，但是它们允许一个节点具有多个父节点。当您希望让一个节点集中在多个单一父节点之下，但又不希望出现具有圈的一般图的打结混乱问题时，这种方法非常方便。您仍然可以轻松地导航 DAG，但是有多种方法可以返回根目录(因为可以有多个父目录)。一个 DAG 通常可以有多个根，但在实践中可能更好的方法是只使用一个根，比如一棵树。如果你了解面向对象程序设计中的单多重继承对抗，那么你就了解了树对抗 DAG。我已经回答了这个 给你。

小开

我看到很多答案指出了 DAG (有向无环图)的含义，但是没有答案。这里有一个非常简单的-

先决条件图 -在工程课程中，每个学生都要面对一项任务，即选择符合先决条件等要求的科目。现在很明显，你不能在没有必要的算法课程的情况下选修人工智能课程。因此 B 依赖于 A，或者用更好的术语 A 有一个指向 B 的边。因此，为了到达节点 B，您必须访问节点 A。很快我们就会明白，在把所有具备必要条件的科目加入到一个图表中之后，它将变成一个有向无环图。

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

大学里允许学生注册课程的软件系统可以将学科建模为节点，以确保学生在注册当前课程之前已经学习了必修课程。

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

另一个实时示例-> Real Time example of how DAG's can be used in version system

小开

这个名字告诉了你大部分你需要知道的关于它的定义: 它是一个图形，每个边只向一个方向流动，一旦你沿着一个边爬下去，你的路径将永远不会返回你刚刚离开的顶点。

我不能说明所有的用途(Wikipedia 在这方面有所帮助) ，但对我来说，DAGs 在确定资源之间的依赖关系时非常有用。例如，我的游戏引擎将所有加载的资源(材质、纹理、着色器、明文、解析后的 json 等)表示为一个 DAG。例如:

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

通过扩展，DAG 对于表示数据处理管道非常有用。非循环性质意味着您可以安全地编写上下文处理代码，这些代码可以沿着顶点的边沿跟踪指针，而无需再遇到相同的顶点。像 VVVV、 Max MSP或 Autodesk Maya 的基于节点的接口这样的可视化编程语言都依赖于 DAGs。

小开

DAG 是一个图，其中所有事情都沿着同一个方向流动，没有节点可以引用回自己。

想想祖先树，它们实际上是 DAGs。

所有 DAGs 都有

  • 节点(存储数据的位置)
  • 指向边缘(指向同一方向)
  • An ancestral node (a node without parents)
  • 叶(没有子节点的节点)

DAGs are different from trees. In a tree-like structure, there must a unique path between every two nodes. In DAGs, a node can have two parent nodes.

这是 关于 DAGs 的好文章希望能有帮助。


提交答案