¿Cómo encontrar la ruta más larga en un árbol no binario y devolverla en un vector?

Answer

1. 

   davy.ai

   May 27, 2023 at 2:26 pm

   Encontrar el camino más largo en una estructura de árbol no binario

   Para encontrar el camino más largo en una estructura de árbol no binario y guardarlo en un vector, podemos usar un algoritmo recursivo de búsqueda en profundidad (DFS). Este es el algoritmo general que puedes seguir:

   1. Comenzamos con cualquier nodo en el árbol y lo marcamos como visitado.
   2. Para cada uno de sus nodos hijos que no han sido visitados, llamamos recursivamente al algoritmo hasta que lleguemos a un nodo hoja.
   3. Una vez que llegamos a un nodo hoja, regresamos un vector que contiene solo el id de ese nodo.
   4. Cuando la llamada recursiva regresa desde un nodo hijo, comparamos las longitudes de los vectores devueltos por cada nodo hijo y elegimos el más largo.
   5. Agregamos el id del nodo actual al vector elegido y lo devolvemos.

   Para hacer un seguimiento de los nodos visitados, podemos agregar una bandera de visitado a la estructura Node o usar un conjunto no ordenado separado de nodos visitados.

   Aquí está el código C++ que implementa el algoritmo:

   “`c++
   std::vector longestPath(Node& node, std::unordered_set& visited) {
   visited.insert(node.id); // marcar nodo como visitado
   std::vector longest; // inicializar vector vacío

   for (Node* child : node.children) {
       if (!visited.count(child->id)) {
           std::vector<std::string> path = longestPath(*child, visited);
           if (path.size() > longest.size()) {
               longest = path;
           }
       }
   }
   
   longest.push_back(node.id); // agregar el nodo actual al camino más largo
   return longest;
   

   }

   
   Para usar esta función, simplemente puedes llamarla con el nodo raíz de tu árbol y un conjunto de visitados vacío, como esto:
   
   ```c++
   std::unordered_set<std::string> visited;
   std::vector<std::string> longest = longestPath(rootNode, visited);
   

   Nota que este código asume que tu estructura Node tiene un campo id único que puede ser usado para comparación y búsqueda en el conjunto de visitados y mapa no ordenado. Si tu estructura Node no tiene este campo, quizá necesites modificar el código en consecuencia.

   Espero que esto te ayude a resolver tu problema. ¡Buena suerte con tu programación!

Comments are closed.