需要类似于DFS的图算法

Question

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

我找到了图算法的维基百科类别，但是这里有一小部分算法，我对他们中的大多数人都不熟悉。

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

Answer 1

在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)

Answer 2

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

获得顶排序的标准方法是进行标准的 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 的元素即可纠正该问题。

Answer 3

如果您正在寻找拓扑排序，您也可以这样做，给定一个邻接列表（或边列表(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 )

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

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

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

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

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

您可能会得到以下结果：

100, 201, 101, 202, 200

但如果您更改它，以便您始终希望首先选择编号较低的类，那么您可以轻松地将其更改为返回：

100, 101, 200, 201, 202