使用Boost图来搜索DAG图？

我需要通过DAG图进行搜索，但是我不希望在看到所有指向它的定向链接的其他节点之前超越节点。使用Boost图来搜索DAG图？

是否有一个现有算法来处理这种特殊情况，深度优先搜索和呼吸优先搜索不适用于此遍历顺序。

即：

A -> B 
B -> C 
C -> D 
A -> C

我不想永远到达d之前看过B和C.

来源

2009-10-07 Dan

唐不要把你的DAG图表带到ATM机上并使用你的PIN号码，否则你可能会得到艾滋病病毒。 – chaos 2009-10-07 16:01:19

所以我最近的想法是在整个图上做一个拓扑排序，每当添加或删除边时，存储要为每个节点遍历的直接子节点的顺序（这可能是一个棘手的算法写）。

然后我做了修改的广度优先搜索（如由混乱所建议的），并且在以下伪代码BFS，修改线：

for each vertex v in Adj[u]

为：

for each vertex v in OrderedAdj[u]

伪代码：

BFS(G, s) 
    for each vertex u in V[G] 
    color[u] := WHITE 
    d[u] := infinity 
    p[u] := u 
    end for 
    color[s] := GRAY 
    d[s] := 0 
    ENQUEUE(Q, s) 
    while (Q != Ø) 
    u := DEQUEUE(Q) 
    for each vertex v in Adj[u] 
     if (color[v] = WHITE) 
     color[v] := GRAY 
     d[v] := d[u] + 1 
     p[v] := u 
     ENQUEUE(Q, v) 
     else 
     if (color[v] = GRAY) 
      ... 
     else 
      ... 
    end for 
    color[u] := BLACK 
    end while 
    return (d, p)

我相信这是实现这一目标的最佳方式，但确实涉及到我写作o wf bfs遍历算法，并存储每个节点上的节点顺序（我希望避免的内存开销），并编写我自己的dfs访问者以查找顺序并将其存储在缓存阶段的节点中。

我很惊讶，没有执行该操作的现有方式，因为在我看来，导航的DAG图的相当常见的方法...

来源

2009-10-08 09:35:24 Dan

你不能做到这一点与普通的图形遍历算法，因为你要求该算法神奇地具有图形结构的知识，它不可能违背它自己的要求而不能遍历。您将不得不使用两遍方法首先构建向后树，告诉您哪些节点已从其他节点连接，然后执行修改的广度优先搜索，使用第一遍中的信息来适当延迟遍历。我怀疑某些图形结构可能会导致第二遍的死锁。

来源

2009-10-07 16:07:22 chaos

那么先做一个拓扑排序，然后在排序图上进行深度优先搜索？

会这样吗？

来源

2009-10-07 16:10:24 Dan

我认为这将不得不在排序图上进行广度优先搜索。 – divegeek 2009-10-07 17:35:35

任何DAG至少有一个叶节点。删除任何叶节点节点和所有传入弧会留下另一个DAG。递归地，这个较小的DAG还具有至少一个叶节点。通过以这种方式递归地移除所有节点，最终根节点成为叶节点。

如果您现在反转您删除节点的顺序，那么您将拥有具有所需属性的遍历顺序。通过最后访问叶节点，您可以保证先看到所有父节点。

来源

2009-10-08 08:39:36 MSalters

谢谢，这被称为拓扑排序，并且在Boost中就像这样实现:)现在，我将如何从这个有序的节点列表去搜索任何特定节点下游的节点（仍然使用这个顺序），最好不写我自己的遍历算法？ – Dan 2009-10-08 09:18:50

你的意思是，当特定节点不是根节点时？看起来很简单：对整个DAG进行拓扑排序，并抛出所有无法从您的特定节点到达的节点。剩下的节点是以特定节点为根的子图的遍历顺序。 – MSalters 2009-10-08 11:26:23

什么你要找的是卡恩（ 1962）拓扑排序算法。这不是目前在基于DFS的BGL中实现的拓扑排序算法，它访问所有顶点并以逆拓扑顺序输出结果，而是非常类似于BFS，并按照您在您的描述中描述的方式访问顶点第一段。你将不得不自己编写遍历，但算法很简单。

查看拓扑排序维基百科条目中列出的第一个算法：http://en.wikipedia.org/wiki/Topological_sorting。另请参阅Sedgewick“C语言中的算法”中的程序19.8。提示1：使用辅助数据结构来维护每个顶点的边的数量，但实际上并不执行“从图中删除边”部分。

提示2：有关工作GPLV3'ed例如，你可以看看卡恩的算法在我CoFlo控制流图的生成和分析项目的实施，特别是文件topological_visit_kahn.h这里：http://coflo.svn.sourceforge.net/viewvc/coflo/trunk/src/controlflowgraph/topological_visit_kahn.h?view=log

来源

2011-09-24 21:52:35

使用Boost图来搜索DAG图？

回答

相关问题