我正在寻找一种可以diff两个有向无环图（DAG）的算法。也就是说，我想要一种算法，它在第一个 DAG 上产生一系列删除和插入以产生第二个 DAG。
我不是百分百肯定，但我认为最长的公共子序列可以应用于 DAG。我不太关心生成的编辑序列的长度（只要它足够短），而更关心算法的运行时间。
一个复杂的问题是，除了单个根节点之外，我的所有顶点都没有被标记。根节点也是唯一具有零入边的节点。图的边缘被标记，图中的“数据”由从根到叶的路径表示。这类似于 atrie但使用有向图而不是树。directed acyclic word graph实际上，我的图表与数据结构非常相似。
这是一个例子。
DAG1
DAG2
要获得 DAG 2，您只需将一个顶点从根添加到另一个带有标签“b”的顶点。从那个顶点到 DAG 1 中的最终“ac”顶点有一条边，还有一条到标签为“d”的新顶点的边。从最后一个顶点到 DAG 1 中的“ac”顶点还有另一条边。我会以 DAG 形式发布一个指向差异的链接，但我不能发布两个以上的链接。
谢谢，希望这足够清晰。
这可能有点太晚了，但只是为了好玩：你的两个 DAG 都可以表示为矩阵，行索引表示“从”顶点，列索引表示“到”顶点，相应的单元格用边缘标记ID。您可以为顶点提供唯一且随机的 id。
下一部分有点棘手，因为只有您的边具有从 DAG1 映射到 DAG2 的有意义的标签。假设您有一组边 E*，它们是 DAG1 和 DAG2 标记边的交集，您将需要执行一系列行移位（向上或向下移动）或列移位（向左或向右移动）所以所有位置DAG1 和 DAG2 中 E* 中的边相互映射。请注意，对于以 Matrix 表示的 DAG，整行或整列的移动位置仍然使表示等效。
剩下的操作是根据映射的矩阵重命名顶点，比较两个矩阵，并识别所需的新边和新顶点（以及可以删除的边和顶点。
您的特定数据表示如何显示边c和x在您的 DAG 2 示例中终止于同一顶点？
如果我们假设 Wikipedia 对“有向图”、“顶点”和“边”的一般定义，则不存在“未标记顶点”之类的东西，因为根据定义，如果不标记它们，就无法描述边那里。
照原样，在我看来，您的问题无法回答。请提供 (1) 提供给算法的输入的简单示例 - 将每个图描述为顶点和边的集合的数据结构 - 以及以类似方式的预期输出，以及 (2) 一种一致的方式来区分是否存在第一个 DAG 中的边或顶点等价于第二个 DAG 中的一个，这意味着图的这方面没有区别。
也许您的问题实际上主要是关于如何确定输入中每个 DAG 中顶点的标签以及如何最好地关联它们。或者，或者，也许标签只是描述每个图的方便，问题实际上是寻求最小的变化集来描述一个图的结构到另一个的转换。
也就是说，图的传统数学定义中的边和顶点是原子的。如果我们假设任何特定顶点或边的相同标签表示完全相同的顶点或边，则每个顶点或边在任何一个图中都存在或不存在，这使得差异的概念有些无意义，或者构建起来微不足道在这两个图中。
这种简单的算法基本上只会枚举两个 DAG 中的每个顶点和边，并将适当的操作添加到差异中，仅从以下操作中进行选择：
add vertex v
remove vertex v
add edge e
remove edge e
switch direction for edge e