Atravesando una estructura de árbol general comenzando desde un nodo arbitrario en C#

Question

Necesito algoritmos de recorrido de árbol para árboles arbitrarios en orden de profundidad tanto primero como primero en anchura. La parte difícil es que necesito poder comenzar desde un nodo arbitrario y continuar hasta que se atraviese otro nodo específico.

Ahora, puedo usar cualquiera de los algoritmos comunes e ignorar los nodos atravesados ​​hasta que toco el nodo de inicio y continúo hasta el nodo final (que actualmente hago) pero esto es feo e ineficiente.

Cualquier sugerencia, por favor.

ACTUALIZACIÓN: Cada uno de mis nodos tiene una identificación asociada. En algunos casos, tengo referencias de nodo de inicio y final para comenzar. En otros casos, me dan dos Ids, compruebo si el nodo dado es el nodo de inicio o el nodo final al inspeccionar sus identificadores. Utilizo un recorrido transversal en profundidad para encontrar el nodo de inicio. Los nodos de inicio y fin pueden estar en cualquier parte de la jerarquía. Espero que alguien pueda tener una idea para el caso en el que ya tengo referencias tanto para el nodo de inicio como para el nodo final. Por cierto, los nodos en el árbol es en realidad ordenados según un orden de clasificación, que se inicia a partir de 0 para cada uno de los sub-nodos de un nodo y hay un nodo de raíz

Answer 1

Creo que lo que está haciendo es la manera más eficiente de hacerlo. Especialmente si estás trabajando con árboles arbitrarios.

Se le asigna un árbol arbitrario y necesita encontrar el nodo desde el que iniciar el recorrido. Como no hay una jerarquía (es decir, no es un árbol binario), tendrá que escanear los nodos (es posible que termine escaneando más de la mitad de los nodos si el nodo dado es un nodo hoja o si el nodo no está en el árbol que tendrá que buscar todo el árbol) hasta que encuentre el nodo para comenzar. Una vez que encuentre el nodo, puede iniciar su cruce de DF o BF Traversal.

No veo ninguna optimización que pueda hacer.

Answer 2

En lugar de

Traverse(RootNode, StartNode, EndNode) 

Pass el nodo de inicio como la raíz

Traverse(StartNode, EndNode) 

sin embargo, si desea volver nodos que no son hijos de su nodo de inicio, que tendrá que seguir usando el método actual.

Answer 3

Si va a tener que responder muchas consultas no relacionadas, y necesita proporcionar una ruta (en lugar de solo decir que existe o no), entonces no puede hacer nada mejor que lo que ahora tiene AFAIK.

Por otro lado, si espera muchas consultas que involucren un pequeño número de nodos específicos (por ejemplo, ¿cuáles son las rutas de A a B, C, D, E, F y G?), Primero puede calcular el minimum spanning tree de ese nodo (s) y hacer su BFS más eficiente.