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

Question

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

score 177 · Accepted Answer

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

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

acyclic = "non-circular" = 沿着边从一个节点移动到另一个节点，您将永远不会第二次遇到同一个节点。

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

score 92 · Accepted Answer

92

带有指向其他点的线的点

于 2012-12-14T11:46:49.293 回答

score 51 · Accepted Answer

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

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

如果有一个循环，那么您将永远无法完成课程：p

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

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

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

score 26 · Accepted Answer

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

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

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

在许多其他事情中。

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

score 14 · Accepted Answer

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

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

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

score 13 · Accepted Answer

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

它们的边缘显示方向。
他们没有周期。

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

score 11 · Accepted Answer

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

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

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

几种应用：

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

score 6 · Accepted Answer

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

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

所有 DAG 都有

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

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

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

score 4 · Accepted Answer

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

score 2 · Accepted Answer

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

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

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 时，为该节点分配当前的排序号并增加排序号，以便递归展开，以递增的顺序分配数字。

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

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

score 1 · Accepted Answer

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

score 1 · Accepted Answer

这个名字告诉你关于它的定义你需要知道的大部分内容：它是一个图，其中每条边只在一个方向上流动，一旦你沿着一条边爬行，你的路径将永远不会回到你刚刚离开的顶点。

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

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

通过扩展，DAG 可用于表达数据处理管道。非循环特性意味着您可以安全地编写上下文处理代码，该代码可以从顶点沿边向下跟踪指针，而无需再次遇到相同的顶点。VVVV、Max MSP或 Autodesk Maya 基于节点的界面等可视化编程语言都依赖于 DAG。

score -5 · Accepted Answer

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

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

13 回答 13

带有指向其他点的线的点

Related

Reference