necesitará un algoritmo gráfico similar a la DFS

Question

Estoy ansioso por ver si existe un algoritmo específico que atraviesa el gráfico acíclico grafo dirigido no ponderado por la elección de un nodo de inicio y luego proceder a través de DFS. Si se encuentra un nodo que tiene predecesores unsearched entonces espalda debe realizar un seguimiento de las trayectorias entrantes hasta que todos los caminos comienzan a se han explorado.

He encontrado un href="http://en.wikipedia.org/wiki/Category:Graph_algorithms" rel="nofollow noreferrer"> categoría pero hay un pequeño mar de algoritmos aquí y no estoy familiarizado con la mayoría de ellos.

EDIT: ejemplo: dado el gráfico {AB, EB, BC, BD}, traverse como: {A, B, E, B, C, D} u orden único como {A, B, E, C, D}. Nota a diferencia de este algoritmo BFS o DFS no tiene que empezar de nuevo en un nuevo nodo de inicio si se han agotado todos los caminos del primer nodo de inicio.

Answer 1

En DFS, por lo general, elegir el vértice a ser visitado después de u basan en los bordes a partir de u. ¿Quieres elegir sobre la base primero en los bordes que terminan en u. Para hacer esto, usted podría tener una transposición gráfica información, y tratar de conseguir el vértice de allí primero.

Sería algo así:

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

Lo que se busca es la clasificación topológica. Por lo que yo soy consciente de que no hay manera fácil de recorrer un gráfico en su orden topológico ordenada sin ningún precomputation.

La manera estándar para obtener el topsort es hacer un DFS estándar, y luego almacenar los nodos visitados en función de su tiempo de visita. Por último, revertir esos nodos y listo, que ellos tienen en el orden que desee.

Pseudocódigo:

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

La lista topsort entonces contendrá los vértices en el orden inverso al que desea. Sólo revertir los elementos de topsort para corregir eso.

Answer 3

Si usted está buscando topological sort, también se puede hacer esto, le dio una lista de adyacencia href="http://en.wikipedia.org/wiki/Adjacency_list" rel="nofollow (o una lista de bordes (u,v) que se puede preprocesar en el tiempo 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 )

Dado un adjacency list (o una lista de bordes (u,v)), esto es O( V + E ), desde cada borde se toca dos veces - una vez a la subasta, una vez al valor de reducción, en el tiempo O(1) cada uno. Con una cola normal, cada vertice también será procesada por la cola a lo sumo dos veces -. Que se puede hacer también en O(1) con una cola estándar

Tenga en cuenta que esto difiere de la DFS (al menos una aplicación recta hacia arriba) en la que se encarga de los bosques.

Otra nota interesante es que si se sustituye con un queue priority_queue imponer algún tipo de estructura / pedido, en realidad se puede devolver los resultados ordenados en algún orden.

Por ejemplo, para un gráfico de la dependencia clase canónica (sólo se puede tomar la clase X si se toma la clase Y):

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

es probable que obtener, como resultado:

100, 201, 101, 202, 200

pero si cambia de modo que uno siempre quiere tomar clases de menor número en primer lugar, se puede cambiar fácilmente para volver:

100, 101, 200, 201, 202