有人可以简单地向我解释什么是有向无环图吗？

Question

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

Answer 1

各种图形在编程中用于模拟各种不同的现实世界关系。例如，社交网络通常由图表示（在本例中为循环网络）。同样，网络拓扑、家谱、航线……

Answer 2

从源代码甚至三地址（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;
}

因此，您要做的就是在自己的代码中遍历树，例如源代码中的表达式树。例如，将现有节点称为 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;
  }
}

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

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

至于对 Dag 进行排序，您从左到右遍历每个 DagNode。换句话说，遵循 DagNodes 的左侧边缘，然后是右侧边缘。数字是反向分配的。换句话说，当您到达没有子节点的 DagNode 时，为该 Node 分配当前排序编号并递增排序编号，以便当递归展开时，编号会按递增顺序分配。

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

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

Answer 3

如果您知道编程中的树是什么，那么编程中的 DAG 是类似的，但它们允许一个节点有多个父节点。当您想让一个节点聚集在多个父节点下，但又不想遇到带有循环的一般图打结混乱的问题时，这会很方便。您仍然可以轻松导航 DAG，但有多种方法可以返回根（因为可能有多个父级）。单个 DAG 通常可以有多个根，但实际上最好只使用一个根，就像一棵树一样。如果您了解 OOP 中的单继承与多重继承，那么您就会了解树与 DAG。我已经在这里回答了这个问题。

Answer 4

这个名称告诉了您需要了解其定义的大部分内容：这是一个图，其中每条边仅朝一个方向流动，一旦您沿着一条边爬行，您的路径将永远不会返回您刚刚离开的顶点。

我无法谈论所有用途（维基百科对此有帮助），但对我来说，DAG 在确定资源之间的依赖关系时非常有用。例如，我的游戏引擎将所有加载的资源（材质、纹理、着色器、纯文本、解析的 json 等）表示为单个 DAG。示例：

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

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

Answer 5

当您想要表示...有向无环图时，有向无环图非常有用！典型的例子是家谱或家谱。

Answer 6

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

向 = 节点（边）之间的连接具有方向： A -> B 与 B 不同 ->非

循环=“非循环”=沿着边缘从一个节点移动到另一个节点，你永远不会第二次遇到同一个节点。

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

Answer 7

带有指向其他点的线的点

Answer 8

我看到很多答案表明 DAG（有向无环图）的含义，但没有关于其应用的答案。这是一个非常简单的图 -

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

如果存在循环，那么您将永远无法完成课程：p

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

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

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

Answer 9

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

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

• 确保以正确的顺序计算计算 (拓扑排序）
• 如果计算可以并行完成，但每个计算都有最大执行时间，那么您可以计算整个集合的最大执行时间

以及其他许多东西。

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

Answer 10

几个答案给出了图形使用的示例（例如网络建模），并且您问“这与编程有什么关系？”。

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

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

Answer 11

有向无环图 (DAG) 具有以下与其他图不同的属性：

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

好吧，我现在可以想到一种用途 - DAG（称为 Wait-For-Graphs - 更多技术细节）可以方便地检测死锁，因为它们说明了一组进程和资源（两者都是 DAG 中的节点）之间的依赖关系。当检测到循环时就会发生死锁。

Answer 12

我假设您已经了解基本的图形术语；否则你应该从图论的文章开始。

有向指的是边（连接）有方向。在图中，这些方向由箭头表示。相反的是无向图，其边不指定方向。

非循环意味着，如果您从任意节点 X 开始并遍历所有可能的边，则在不返回已使用的边的情况下无法返回到 X。

多种应用：

• 电子表格； DAG 文章对此进行了解释。
• 修订控制：如果您查看该页面中的图表，您会发现演变版本控制代码的一部分是定向的（在该图中它“向下”）并且是非循环的（它永远不会“向上”返回）。
• 家谱：它是有向的（你是你父母的孩子，而不是相反）和非循环的（你的祖先永远不可能是你的后代）。

Answer 13

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

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

所有 DAG 都有

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

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

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