serve un algoritmo grafico simile a DFS

Question

Sono curioso di sapere se esiste un algoritmo grafico specifico che attraversa un grafo orientato aciclico non ponderata scegliendo un nodo di partenza e poi di procedere tramite DFS. Se viene riscontrato un nodo che ha predecessori unsearched allora dovrebbe sostenere traccia i percorsi in entrata fino a quando tutti i percorsi per iniziare sono stati esplorati.

Ho trovato un wikipedia categoria per gli algoritmi grafico ma c'è un piccolo mare di algoritmi qui e io non sono familiarità con la maggior parte di loro.

EDIT: Esempio: dato il grafico {AB, EB, BC, BD}, traverse come: {A, B, E, B, C, D} o {ordine unico come A, B, E, C, D}. Nota questo algoritmo a differenza BFS o DFS non ha bisogno di ricominciare a un nuovo nodo di partenza, se tutti i percorsi del primo nodo di partenza sono esauriti.

Answer 1

In DFS, di solito si sceglie il vertice da visitare dopo u in base ai margini a partire da u. Si desidera scegliere in base prima sui bordi che terminano a u. Per fare questo, si potrebbe avere un trasporre grafico informazioni, e cercare di ottenere il vertice da lì prima.

Sarebbe qualcosa di simile:

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

Quello che state cercando è il tipo topologico. Per quanto io sappia non c'è un modo semplice per attraversare un grafico nel suo ordine topologico ordinato senza alcun precomputation.

Il metodo standard per ottenere il topsort è quello di fare uno standard DFS, e quindi memorizzare i nodi visitati in ordine di loro orari di visita. Infine, invertire quei nodi e voilà, li avete nell'ordine desiderato.

Pseudocodice:

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 conterrà quindi i vertici in ordine inverso che si desidera. Basta invertire gli elementi di topsort per correggere questo.

Answer 3

Se siete alla ricerca di topological sort, si può anche fare questo, dato un (o un elenco di bordi (u,v) quale è possibile pre-elaborare in tempo 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 )

Dato un adjacency list (o una lista di bordi (u,v)), questo è O( V + E ), dal momento che ogni bordo viene toccato due volte - una volta per incrementare, una volta per decrementare, in tempo O(1) ciascuna. Con una coda normale, ogni vertice sarà anche elaborato dalla coda al massimo due volte - che può essere fatto anche in O(1) con una coda standard

.

Si noti che questo è diverso dal DFS (almeno un'implementazione straight-up) in cui il programma gestisce le foreste.

Un'altra nota interessante è che se si queue sostituto con un priority_queue imponendo una sorta di struttura / ordinamento, si può effettivamente restituire i risultati ordinati in un certo ordine.

Ad esempio, per un grafico di classe canonica dipendenza (si può solo prendere la classe X se si ha classe Y):

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

si sarebbe probabilmente ottenere, come risultato:

100, 201, 101, 202, 200

, ma se si cambia in modo che si vuole sempre prendere lezioni di basso numerate prima, si può facilmente cambiare per tornare:

100, 101, 200, 201, 202