Quanto è preciso un ordine per una ricerca in profondità di un grafico?

Am I right that there are many possible answers to this question? And is my trace of the DPS correct?

Sì, non esiste un ordinamento "naturale" dei nodi di un grafico. Quindi non c'è nemmeno un ordinamento "naturale" nel risultato della DFS di un grafico.

Ovviamente, nell'esempio sopra, puoi ordinare i nodi in ordine alfabetico poiché hai etichette su di essi. Se si presume di avere un ordine dei nodi, è possibile creare un risultato deterministico di un DFS, ad esempio, sempre visitando prima i nodi inferiori.

Sì, il percorso esatto della ricerca dipende da quale punto di partenza si sceglie e - ogni volta che si colpisce un nodo con più bambini non visitati - quale ordine si sceglie di visitare i bambini. La maggior parte delle implementazioni di DFS sarà sempre scegli lo stesso ordine, ma quale ordine dipende dai dettagli dell'implementazione dell'algoritmo e rappresentazione grafica che normalmente non importa troppo. Infine, la tua traccia per quel grafico sembra una valida per me.

Si noti che è possibile che un grafo diretto abbia solo un punto di partenza valido (nel senso che nessun altro gli consentirebbe di visitare ogni nodo) e un percorso disponibile, ma questo è solo nel caso banale di una "linea retta" "grafico.

Come hai ipotizzato e come altri hanno confermato, non c'è una sola risposta ottimale alla domanda. Detto questo, puoi raggruppare tutte le possibili risposte in classi di equivalenza e poi sottolineare che alcune classi sono migliori di altre.

A causa delle specifiche del modo in cui hai formulato questo problema, le classi di equivalenza più naturali sono "risposte corrette" o "risposte errate", quindi non otteniamo qualcosa di molto interessante da questo. Ma considera una domanda molto simile che è "data un grafo (non orientato?), Qual è il suo primo ordine di larghezza, a partire da g?"

Un modello per tutte le risposte ottimali potrebbe apparire come [{g}, {j, k, h, d}, {f, i, o, c}, {a, m, n, e, p, b, d}]. Questo modello offre [g, j, k, h, d, f, i, o, c, a, m, n, e, p, b, d] come una possibile risposta, ma anche [g, d, h, per esempio, k, j, c, o, i, f, d, b, p, e, n, n, a].

Potresti quindi rispondere come [g, j, k, h, f, d, i, o, c, a, m, n, e, p, b, d] e dire che è "un livello" guasto". [g, j, k, d, f, h, i, o, c, a, m, n, e, p, b, d] è anche un livello fuori ordine, e quindi apparterrebbe allo stesso set di equivalenza .

Al contrario, una risposta come [g, j, k, f, h, d, i, o, c, a, m, n, e, p, b, d] sarebbe di due livelli fuori ordine, e quindi appartengono a un diverso set di equivalenza.

In alternativa, potresti creare un diagramma di Hasse di tutti gli ordini possibili, fornendo essenzialmente un ordinamento parziale sulle risposte che dicono alcune risposte sono "migliori" di altre.

Se il tuo grafico è spaziale, osserva gli algoritmi di riempimento Z e, in base al tuo intento, gli algoritmi di marcia per indirizzare il tuo albero verso un particolare obiettivo o regione di interesse.