Attraversamento una struttura ad albero generale partendo da un nodo arbitrario in C#

Question

Ho bisogno algoritmi di attraversamento per alberi arbitrarie sia in ordine attraversamento in profondità ed in ampiezza. La parte difficile è che ho bisogno di essere in grado di partire da un nodo arbitrario e continuare fino a quando non viene attraversato un altro nodo specifico.

Ora, posso utilizzare uno qualsiasi degli algoritmi ordinari e ignorare i nodi attraversati fino a raggiungere il nodo iniziale e continuare fino al nodo finale (che attualmente faccio) ma questo è brutto e inefficiente.

Qualsiasi suggerimento, per favore.

UPDATE: Ognuno dei miei nodi hanno un id ad essi associati. In alcuni casi, ho i riferimenti iniziali e finali del nodo con cui iniziare. In altri casi, mi vengono dati due Id, controllo se il nodo dato è il nodo di partenza o il nodo finale controllando i loro id. Io uso deep-first traversal per trovare il nodo di partenza. Sia il nodo iniziale che quello finale possono essere ovunque nella gerarchia. Spero che qualcuno possa inventare un'idea per il caso in cui ho già fornito riferimenti sia al nodo iniziale che al nodo finale. A proposito, i nodi dell'albero è in realtà scelti secondo un criterio di ordinamento, che parte da 0 per ciascuna delle sub-nodi di un nodo e v'è un nodo radice

Answer 1

Penso che quello che stai facendo sia il modo più efficace per farlo. Soprattutto se lavori con alberi arbitrari.

Si sono dati un albero arbitrario e hai bisogno di trovare il nodo per avviare l'attraversamento da. Poiché non esiste una gerarchia (ad esempio: non è un albero binario), dovrai eseguire la scansione dei nodi (potresti finire per scansionare più della metà dei nodi se il nodo dato è un nodo foglia o se il nodo non è nell'albero tu dovrà cercare l'intero albero) fino a trovare il nodo con cui iniziare. Una volta trovato il nodo, puoi iniziare DF Traversal o BF Traversal.

Non vedo alcuna ottimizzazione che si possa fare.

Answer 2

Anziché

Traverse(RootNode, StartNode, EndNode) 

Passo nodo di partenza come la radice

Traverse(StartNode, EndNode) 

Tuttavia, se si desidera restituire i nodi che non sono figli del nodo di partenza, si dovrà continuare a utilizzare il metodo corrente.

Answer 3

Se devi rispondere a molte query non correlate e devi fornire un percorso (anziché limitarti a dire che esiste o no), non puoi fare meglio di quello che hai ora AFAIK.

D'altra parte, se ci si aspetta un sacco di domande che coinvolgono un piccolo numero di nodi specifici (ad esempio quali sono i percorsi da A a B, C, D, E, F, e G?) Quindi è possibile prima di calcolare il minimum spanning tree da quel nodo (i) e rendi il tuo BFS più efficiente.