1

我需要搜索 DAG 图，但我不想在看到所有其他节点都指向它的定向链接之前越过一个节点。

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

IE：

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

我不想在看到 B 和 C 之前到达 D。

4

5 回答 5

2

您正在寻找的是 Kahn (1962) 的拓扑排序算法。这不是目前在 BGL 中实现的拓扑排序算法，它是基于 DFS 的，访问所有顶点，并以相反的拓扑顺序输出结果，而是与 BFS 非常相似，并且完全按照您在您的描述中描述的方式访问顶点第一段。您必须自己编写遍历，但算法很简单。

请参阅拓扑排序维基百科条目中列出的第一个算法：http ://en.wikipedia.org/wiki/Topological_sorting 。另请参阅 Sedgewick 的“C 语言算法”中的程序 19.8。

提示 1：使用辅助数据结构来维护每个顶点的边数，实际上不要执行“从图形中删除边”部分。

提示 2：对于一个有效的 GPLV3 示例，您可以在我的 CoFlo 控制流图生成和分析项目中查看 Kahn 算法的实现，特别是这里的文件 topological_visit_kahn.h：http://coflo.svn.sourceforge .net/viewvc/coflo/trunk/src/controlflowgraph/topological_visit_kahn.h?view=log

于 2011-09-24T21:52:35.730 回答
1

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

然后我进行修改后的广度优先搜索（如 chaos 所建议的那样），并在以下 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)

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

我很惊讶没有现有的方法可以做到这一点，因为在我看来这是一种相当常见的导航 dag 图的方法......

于 2009-10-08T09:35:24.603 回答
0

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

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

于 2009-10-08T08:39:36.387 回答
0

您不能使用普通的图遍历算法来做到这一点，因为您需要算法神奇地了解图结构，而如果不违反其自身的要求，它就无法遍历这些知识。您必须使用两遍方法，首先构建反向树，告诉您哪些节点与其他节点有连接，然后进行修改后的广度优先搜索，该搜索使用来自第一遍的信息来适当地延迟遍历。而且我怀疑某些图形结构可能会使第二遍陷入僵局。

于 2009-10-07T16:07:22.263 回答
0

先进行拓扑排序，然后在排序图上进行深度优先搜索怎么样？

那行得通吗？

于 2009-10-07T16:10:24.737 回答