有向无圈图的差分
我正在寻找一种算法，它可以<编码>不同两个有向无环图（DAG）。也就是说，我想要一个算法，它在第一个DAG上产生删除和插入序列，以产生第二个DAG。
我不是百分之百确定，但我认为一个最长的公共子序列可以应用于DAG。我不太关心结果编辑序列的长度（只要它足够短），更关心算法的运行时间。
一个复杂的问题是，除了一个根节点之外，没有一个顶点被标记。根节点也是唯一一个内边为零的节点。图的边被标记，图中的“数据”由从根到叶的路径表示。这类似于trie，但使用有向图而不是树。实际上，我的图与有向无环字图数据结构非常相似。
共有1个答案
这可能有点太晚了，但只是为了好玩：您的两个DAG都可以表示为矩阵，行索引指示“从”顶点，列索引指示“到”顶点，对应的单元格标记有edge ID。您可以给顶点唯一和随机的ID。
下一部分有点棘手，因为只有边缘有从DAG1映射到DAG2的有意义的标签。假设有一组边E*，这些边是DAG1和DAG2的标记边的交点，您将需要执行一系列行移位（向上或向下移动）或列移位（向左或向右移动），以便E*中所有边在DAG1和DAG2中的位置相互映射。请注意，对于以矩阵表示的DAG，移动整行或整列的位置仍然使表示等效。
剩下的操作是根据映射的矩阵重命名顶点，比较两个矩阵，并确定所需的新边和新顶点（以及可以删除的边和顶点）。
-
假设图G是一个有向无圈图，其顶点数为'n'no。如果我从图中移除所有边并使其完全断开，这会是一个DAG吗？
-
在一个已执行DFS的无向图中（为了生成一个DFS树，从而将每条边分类为树边或后边），图中是否存在仅由后边组成的循环，即没有树边？
-
我有一个有圈的有向图。所有边都是加权的，权重可以是负值。可能会有负循环。
-
我正在编写一个使用电网格分析的程序。所以我有电路的节点[A,B,C,D]和连接节点[0,1,2,3,4,5,6,7,8]的分支。 如何在具有多条边的无向图中找到最短的循环？ 图形图像（4个节点，9条边/分支）： 周期： 我需要的循环数是：循环=分支-（节点-1)，在本例中我需要6个循环。 我将这些数据存储在这样的数组中： 我很乐意看到任何语言的算法。
-
请告诉我为什么这段代码不能分析无向图中是否有循环？代码如下。这是Spoj上的PT07Y问题。我正在做的是取一个节点并执行dfs。当执行dfs时，如果我访问同一个节点，那么我说有一个循环。从一个节点执行dfs后，我使访问的数组为假，并为下一个节点执行，直到我得到一个周期或所有节点都被访问。
-
我试着用谷歌搜索，但是没有任何有价值的东西弹出。 图表： 它是无方向的 表示为具有双边的有向图 可能包含具有负权重的边 我知道我可以使用Bellman Ford在有向情况下解决这个问题，但是对于无向边，它只返回单边（2个循环）作为其输出。我需要找到一个循环的大小 此外，该算法应该具有运行时复杂性O（V*E）和内存复杂性O（V）。