1

我很好奇是否有一个特定的图算法通过选择一个起始节点然后通过 DFS 来遍历一个未加权的无环有向图。如果遇到具有未搜索前任的节点，则它应该回溯传入路径，直到已经探索了所有要开始的路径。

我找到了一个用于图形算法的维基百科类别，但这里有一小部分算法，我对其中的大多数都不熟悉。

编辑：示例：给定图 {AB, EB, BC, BD}，遍历为：{A,B,E,B,C,D} 或唯一顺序为 {A,B,E,C,D}。请注意，与 BFS 或 DFS 不同，此算法不需要在第一个起始节点的所有路径都用尽的情况下从新的起始节点重新开始。

4

3 回答 3

2

您正在寻找的是拓扑排序。据我所知，没有任何预先计算，没有简单的方法可以按照拓扑排序顺序遍历图形。

获得 topsort 的标准方法是做一个标准的 DFS，然后按照访问时间的顺序存储访问过的节点。最后，反转这些节点，瞧，你按照你想要的顺序拥有它们。

伪代码：

list topsort

procedure dfs(vertex u)
  mark u as visited
  for each edge (u, v)
    if v not visited
      dfs(v)
  add u to the back of topsort

然后该列表topsort将包含您想要的相反顺序的顶点。只需反转 topsort 的元素即可纠正该问题。

于 2010-02-24T00:44:40.687 回答
2

在 DFS 中，您通常根据从 u 开始的边来选择要在 u 之后访问的顶点。您想首先根据以 u 结尾的边进行选择。为此，您可以有一个转置图信息，并尝试先从那里获取顶点。

它会是这样的：

procedure dfs(vertex u)
  mark u as visited
  for each edge (v, u) //found in transpose graph
    if v not visited
      dfs(v)
  for each edge (u, w)
    if v not visited
      dfs(w)
于 2010-02-24T01:04:31.973 回答
2

如果您正在寻找topological sort，您也可以这样做，给定一个邻接列表（或(u,v)您可以及时预处理的边列表O(E)）：

list top_sort( graph in adjacency list )
     parent = new list
     queue = new queue
     for each u in nodes
         parent(u) = number of parents
         if ( parent(u) is 0 ) // nothing points to node i
             queue.enqueue( u )

     while ( queue is not empty )
         u = queue.pop
         add u to visited
         for each edge ( u, v )
             decrement parent(v) // children all have one less parent
             if ( parent(v) is 0 )
                 queue.enqueue( v )

给定一个adjacency list（或边缘列表(u,v)），这是O( V + E )因为每个边缘被触摸两次 - 一次递增，一次递减，O(1)每次都及时。对于普通队列，每个顶点最多也将被队列处理两次——这也可以在O(1)标准队列中完成。

请注意，这与 DFS（至少是直接实现）的不同之处在于它处理森林。

另一个有趣的注意事项是，如果你queue用某种priority_queue强加的结构/排序代替，你实际上可以返回按某种顺序排序的结果。

例如，对于一个规范的类依赖图（如果你选择了 Y 类，你只能选择 X 类）：

100:
101: 100
200: 100 101
201: 
202: 201

结果，您可能会得到：

100, 201, 101, 202, 200

但是如果你改变它以便你总是想先上编号较低的课程，你可以很容易地把它改成返回：

100, 101, 200, 201, 202
于 2010-02-24T02:17:43.307 回答