11

我正在寻找一种算法来“反转”（反转？从里到外？）一个 DAG：

       A*      # I can't ascii-art the arrows, so just
      / \      # pretend the slashes are all pointing
     B   C     # "down" (south-east or south-west)
    /   / \    # e.g. 
   G   E   D   # A -> (B -> G, C -> (E -> F, D -> F))
        \ /
         F

我使用的表示是不可变的，真正的 DAG（没有“父”指针）。我想以某种方式遍历图形，同时构建具有等效节点的“镜像”图形，但节点之间的关系方向倒置。

         F*
        / \
   G*  E   D   # F -> (E -> C -> A, D -> C -> A), G -> B -> A
    \   \ /    # 
     B   C     # Again, arrows point "down"
      \ /      # 
       A       #

所以输入是一组“根”（这里是{A}）。输出应该是结果图中的一组“根”：{G, F}。（根是指没有传入引用的节点。叶子是没有传出引用的节点。）

输入的根变成输出的叶子，反之亦然。变换应该是自身的逆。

（出于好奇，我想向我用来表示 XML 以进行结构查询的库添加一个功能，通过它我可以将第一棵树中的每个节点映射到第二棵树中的“镜像”（然后返回再次）为我的查询规则提供更多的导航灵活性。）

4

5 回答 5

9

遍历图，构建一组反向边和一个叶节点列表。

使用叶子（现在是根）节点对反向边执行拓扑排序。

根据从排序列表末尾开始的反向边构造反向图。由于节点是以反向拓扑顺序构造的，因此可以保证在构造节点之前已经构造了给定节点的子节点，因此可以创建不可变的表示。

如果您使用结构作为中间表示来跟踪与节点关联的两个方向上的所有链接，则这是 O(N)，如果您使用排序来查找节点的所有链接，则为 O(NlnN)。对于小型图或不受堆栈溢出影响的语言，您可以懒惰地构造图，而不是显式地执行拓扑排序。因此，这在一定程度上取决于您要实现的所有内容，这将有多大不同。 

A -> (B -> G, C -> (E -> F, D -> F))

original roots: [ A ]
original links: [ AB, BG, AC, CE, EF, CD, DF ] 
reversed links: [ BA, GB, CA, EC, FE, DC, FD ]
reversed roots: [ G, F ]
reversed links: [ BA, CA, DC, EC, FE, FD, GB ] (in order of source)
topologically sorted: [ G, B, F, E, D, C, A ]
construction order : A, C->A, D->C, E->C, F->(D,E), B->A, G->B
于 2009-02-28T15:11:14.027 回答
2

只需在您已经去过的地方进行深度优先搜索标记，每次遍历箭头时，将反向添加到结果 DAG 中。添加叶子作为根。

于 2009-02-27T14:46:28.353 回答
2

我的直观建议是对图执行深度优先遍历，并同时构建镜像图。

在遍历每个节点时，在镜像图中创建一个新节点，并在新图中在它与其前身之间创建一条边。

如果您在任何时候到达没有子节点的节点，请将其标记为根。

于 2009-02-27T14:47:35.403 回答
1

我通过一个简单的图遍历解决了这个问题。请记住，拓扑排序仅对有向无环图有用。

我使用了邻接列表，但您可以使用邻接矩阵做类似的事情。

在 Python 中，它看起来像这样：

# Basic Graph Structure
g = {}
g[vertex] = [v1, v2, v3] # Each vertex contains a lists of its edges

要找到 v 的所有边，然后遍历列表 g[v]，这将为您提供所有 (v, u) 边。

要构建反转图，请创建一个新字典并构建它，如下所示：

    reversed = {}
    for v in g:
        for e in g[v]:
            if e not in reversed:
                reversed[e] = []
            reversed[e].append(v)

这对于大型图形来说非常占用内存（使您的内存使用量翻倍），但这是一种非常简单的使用它们的方法并且非常快。可能有更聪明的解决方案，包括构建一个生成器和使用某种 dfs 算法，但我没有考虑太多。

于 2012-04-12T19:39:23.863 回答
-1

深度优先搜索可能能够生成您所追求的：注意您通过树的路径，并且每次遍历时将反向添加到生成的 DAG（叶子是根）。

于 2009-02-27T14:44:32.400 回答