有人能用简单的术语向我解释什么是有向无环图吗?

线条指向其他点的点

图=由节点组成的结构,这些节点通过边缘相互连接

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

acyclic=“non-circular”=沿着边从一个节点移动到另一个节点,您将永远不会再次遇到同一个节点。

有向无环图的一个好例子是树。然而,请注意,并非所有有向无环图都是树。

我看到很多答案表明了DAG(有向无环图)的含义,但在其应用程序中没有答案。这是一个很简单的-

先决条件图 -在工程学课程中,每个学生都面临着选择符合先决条件等要求的科目的任务。很明显,如果没有关于算法的必修课,你就不能上人工智能的课。因此,B依赖于A,或者更好地说,A有一个指向B的边。所以为了到达B节点,你必须访问A节点。很快就会清楚,在将所有具有其先决条件的主题添加到一个图中之后,它将变成一个有向无环图。

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

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

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

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

有向非循环图在编程中的示例使用或多或少包括表示连接性和因果关系的任何内容。

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

• 确保按正确的顺序计算( topological sort )
• 如果可以并行进行计算,但每个计算都有一个最大执行时间,则可以计算整个集合的最大执行时间。

还有很多其他的事情。

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

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

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

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

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

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

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

我希望这有帮助。

干杯

我假设您已经知道基本的图形术语;否则您应该从 graph theory .

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

无环的 也就是说,如果从任意节点X开始并遍历所有可能的边,那么在返回到X之前,必须返回到已经使用过的边。

几种应用:

• 电子表格;这在 DAG 文章。
• Revision control :如果您查看了该页中的图表,您将看到修订控制代码的演变是定向的(在该图中它变为“向下”)和非循环的(它从不变为“向上”)。
• 家谱:它是定向的(你是你父母的孩子,而不是相反的方向)和非循环的(你的祖先永远不会是你的后代)。

各种各样的图都被用在编程中来模拟各种不同的现实世界关系。例如,社交网络通常由一个图表表示(在本例中是循环的)。同样,网络拓扑结构、家族树、航线……

DAG是一个图形,其中所有内容都朝着相同的方向流动,没有节点可以引用回自身。

想想祖先的树木,它们实际上是匕首。

DAGs都有

• 节点(存储数据的位置)
• 有向边(指同一方向)
• 祖先节点(没有父节点的节点)
• 叶(没有子节点的节点)

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

这里有一个 good article about DAGs . 希望有帮助。

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

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

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

因此,在这种情况下,您可以使用DAG来计算表达式,这很方便,因为通常对计算进行解释,并且使用这样的DAG评估器将使简单的Intrepter在主体上更快,因为它不会推送和弹出到堆栈中,而且还因为它正在消除常见的子表达式。

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

1)使你的DAG对象如此

您需要一个活动列表,该列表包含所有当前的活动DAG节点和DAG子表达式。DAG子表达式是DAG节点,也可以将其称为内部节点。我所说的动态DAG节点是指,如果你给一个变量x赋值,它就变成了动态的。然后使用x的公共子表达式使用该实例。如果X再次被分配,那么将创建一个新的DAG节点并将其添加到活动列表中,并删除旧的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中了。

这是非常简单的伪代码。不用于编译。

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。

显然,示例过程可以分成更小的部分,或者用虚拟函数作为子类。

至于对DAG的排序,您将从左到右遍历每个DAG节点。换言之,沿着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;
}

如果您知道在编程中有哪些树,那么在编程中DAG是相似的,但它们允许一个节点有多个父节点。当您想让一个节点聚集在不止一个父节点下,但又不存在一个带有循环的一般图形的混乱的问题时,这是很方便的。您仍然可以轻松地导航DAG,但有多种方法可以返回到根目录(因为可以有多个父目录)。一般来说,一个DAG可以有多个根,但在实践中,最好只使用一个根,就像一棵树。如果您了解OOP中的单继承与多继承,那么您就知道树与DAG。我已经回答了这个问题 here .

这个名字告诉你你需要知道它的定义:它是一个图形,每个边只朝一个方向流动,一旦你沿着一条边爬下去,你的路径就永远不会返回到你刚离开的顶点。

我不能说所有的用途(维基百科有帮助),但对我来说,DAG在确定资源之间的依赖性时非常有用。例如,我的游戏引擎将所有加载的资源(材质、纹理、着色、纯文本、解析的JSON等)表示为单个DAG。例子:

材质是n gl程序,每个程序需要两个明暗器,每个明暗器需要一个纯文本明暗器源。通过将这些资源表示为DAG,我可以轻松地查询图表中的现有资源,以避免重复加载。假设您希望多个材质使用具有相同源代码的顶点明暗器。当您只需为现有资源建立新的边缘时,重新加载源并重新编译着色器以供每次使用是浪费的。通过这种方式,您还可以使用图表来确定是否有任何内容完全依赖于某个资源,如果不依赖于某个资源,则删除该资源并释放其内存,事实上,这种情况几乎是自动发生的。

通过扩展,DAG可用于表示数据处理管道。非循环性意味着您可以安全地编写上下文处理代码,这些代码可以沿着顶点的边缘向下跟踪指针,而无需重新创建相同的顶点。可视化编程语言 VVVV , Max MSP 或者,基于节点的AutodeskMaya接口都依赖DAG。

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