需要类似于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中的边缘后，通常会选择要访问的顶点。你要选择首先基于在ü结束的边缘。要做到这一点，你可以有一个转图的信息，并试图让从那里顶点第一

这将是这样的：

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

你所寻找的是拓扑分类。据我所知有没有简单的方法来遍历其拓扑有序的图形没有任何预先计算。

获得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的元件，以矫正该

Answer 3

如果你正在寻找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，实际上你可以返回结果在某些顺序进行排序。

例如，对于经典类别依赖图（只能采取类X如果你把类Y）：

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

你可能会得到的，其结果是：

100, 201, 101, 202, 200

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

100, 101, 200, 201, 202