Encuentra todos los caminos en un grafo no dirigido y acíclico.

Answer

1. 

   davy.ai

   July 25, 2023 at 1:33 am

   Tu código se acerca bastante a lo que necesitas para encontrar todos los caminos a través del grafo, pero hay algunos problemas que impiden que funcione correctamente. Aquí te dejo algunas sugerencias para ayudarte a depurarlo:

   1. Verifica tu caso base: Lo primero que hace tu función Traverse es comprobar si start es igual a traverseEnd, que es el vértice llamado end. Si es así, agregas el camino actual a la lista paths y borras _path. Sin embargo, esta comprobación solo debe hacerse cuando hayas llegado al final de un camino, no al principio de la función. Debes mover esta comprobación al final de la función, después de haber procesado recursivamente todos los vecinos de start.

   2. Realiza un seguimiento correcto de los vértices visitados: Tu código omite correctamente los vértices con nombres en minúsculas si ya han sido visitados. Sin embargo, estás utilizando un HashSet para realizar un seguimiento de los vértices visitados, lo cual no tiene en cuenta la ruta específica que estás recorriendo actualmente. Debes modificar tu código de seguimiento para utilizar un conjunto separado de vértices visitados para cada camino, de modo que puedas visitar el mismo vértice varias veces siempre y cuando no esté en el mismo camino.

   3. Visita cada vecino solo una vez: Dado que este es un grafo no dirigido, debes asegurarte de no visitar el mismo vecino dos veces seguidas. De lo contrario, puedes caer en un bucle infinito. Puedes hacer esto comprobando si la arista anterior en _path termina en el vecino actual antes de agregar una nueva arista a _path.

   Aquí tienes una versión actualizada de tu código que debería funcionar correctamente:

   private HashSet<><edge>> paths = new();
   private List<edge> _path = new();
   private void Traverse(Vertex start, HashSet<vertex> visited)
   {
       visited.Add(start);
   
       var traverseEnd = GetVertexByName("end");
       if (start == traverseEnd)
       {
           paths.Add(_path.ToList());
           return;
       }
   
       var neighbors = _adjacencyList[start];
       foreach (var end in neighbors)
       {
           if (!visited.Contains(end))
           {
               if (_path.LastOrDefault()?.End != end)  // No retrocedas sobre el mismo vecino
               {
                   _path.Add(new Edge(start, end));
                   Traverse(end, new HashSet<vertex>(visited));  // Crea un nuevo conjunto para cada llamada
                   _path.RemoveAt(_path.Count - 1);
               }
           }
       }
   }
   
   // Llámalo con el vértice de inicio y un conjunto de vértices visitados vacío
   Traverse(GetVertexByName("start"), new HashSet<vertex>());
   

   Esta versión de Traverse toma un parámetro adicional visited, que es un conjunto de vértices visitados previamente en la ruta actual. Para cada vecino de start, primero verifica si ya ha sido visitado en la ruta actual, luego verifica si es igual al vecino anterior (si lo hay) antes de agregar una nueva arista a _path. También crea un nuevo conjunto visited para cada llamada recursiva, para que cada camino tenga su propio conjunto de vértices visitados. Finalmente, elimina la última arista de _path después de que se complete la llamada recursiva para retroceder y probar otros vecinos.

   ¡Espero que esto te ayude! Hazme saber si tienes alguna otra pregunta.

Comments are closed.