The problem is in the way you control if you have already gone through a vertex: put the property visitado of the vertex to true .
What you should check is if the current route has already passed this vertex but, when checking the property visitado , what you do is check if any of the routes has passed through that vertex.
To check if the vertex has been traversed by the current route you could see if it exists in the string path .
In this example I use a regular expression to see if it is already included in the current route:
static void DFS(vertice origen, vertice destino, grafo graf, string path)
{
path = (path == String.Empty ? path : $"{path},") + origen.nombre;
if (origen.nombre == destino.nombre)
{
Console.WriteLine(path);
}
else
{
for (int con = 0; con < origen.adyacencias.Length; con++)
{
var visitado = Regex.IsMatch(path, $@"\b{graf.vertices[con].nombre}\b");
if (origen.adyacencias[con] > 0 && !visitado)
{
DFS(graf.vertices[con], destino, graf, path);
}
}
}
}
For the example of Kappa origin - Zeta destination, I get:
Here the complete code of the console application to perform tests:
using System;
using System.Text.RegularExpressions;
namespace ConsoleApp_C
{
class Program
{
static void Main(string[] args)
{
var grafo = CrearGrafo();
Console.WriteLine("Introduzca Origen");
var origen = Console.ReadKey();
int nodoOrigen = Int32.Parse(origen.KeyChar.ToString());
Console.WriteLine("\nIntroduzca Destino");
var destino = Console.ReadKey();
int nodoDestino = Int32.Parse(destino.KeyChar.ToString());
string path = "";
Console.WriteLine();
DFS(grafo.vertices[nodoOrigen], grafo.vertices[nodoDestino], grafo, path);
Console.ReadKey();
}
static grafo CrearGrafo()
{
var result = new grafo
{
vertices =
{
[0] = new vertice
{
nombre = "Alfa",
adyacencias = { [1] = 20000, [2] = 76000 }
},
[1] = new vertice
{
nombre = "Delta",
adyacencias = { [0] = 20000, [3] = 10000 }
},
[2] = new vertice
{
nombre = "Beta",
adyacencias = { [0] = 76000, [4] = 360000, [5] = 240000 }
},
[3] = new vertice
{
nombre = "Gamma",
adyacencias = { [1] = 10000, [6] = 360000, [7] = 120000 }
},
[4] = new vertice
{
nombre = "Iota",
adyacencias = { [2] = 360000, [8] = 120000 }
},
[5] = new vertice
{
nombre = "Epsilon",
adyacencias = { [2] = 240000, [9] = 60000 }
},
[6] = new vertice
{
nombre = "Kappa",
adyacencias = { [3] = 360000, [7] = 180000 }
},
[7] = new vertice
{
nombre = "Theta",
adyacencias = { [3] = 120000, [6] = 180000 }
},
[8] = new vertice
{
nombre = "Zeta",
adyacencias = { [4] = 120000, [9] = 30000 }
},
[9] = new vertice
{
nombre = "Eta",
adyacencias = { [5] = 60000, [8] = 30000 }
}
}
};
return result;
}
static void DFS(vertice origen, vertice destino, grafo graf, string path)
{
path = (path == String.Empty ? path : $"{path},") + origen.nombre;
if (origen.nombre == destino.nombre)
{
Console.WriteLine(path);
}
else
{
for (int con = 0; con < origen.adyacencias.Length; con++)
{
var visitado = Regex.IsMatch(path, $@"\b{graf.vertices[con].nombre}\b");
if (origen.adyacencias[con] > 0 && !visitado)
{
DFS(graf.vertices[con], destino, graf, path);
}
}
}
}
// CLASES GRAFO Y VERTICE
class grafo
{
public vertice[] vertices = new vertice[10];
}
class vertice
{
public string nombre = "";
public string diametro = "";
public string promedio = "";
public bool visitado = false;
public float[] adyacencias = new float[10];
}
}
}
It must be borne in mind that the values to be entered are the indexes of the origin and destination vertices. For example, to test with the Kappa-Zeta route, the values to be entered would be 6 (vertex index Kappa) and 8 (vertex index Zeta)
I would also propose a different way of maintaining the information of the graph: keeping two different collections, one with the vertices and the other with the connections between them.
Here is the code of a console application using this option:
using System;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApp_C
{
class Program
{
static void Main(string[] args)
{
var grafo = new Grafo(new[]
{"Alfa", "Beta", "Gamma", "Delta", "Epsilon", "Theta", "Eta", "Zeta", "Iota", "Kappa"});
grafo.CrearConexion("Alfa", "Delta", 20000);
grafo.CrearConexion("Alfa", "Beta", 76000);
grafo.CrearConexion("Delta", "Gamma", 10000);
grafo.CrearConexion("Beta", "Iota", 360000);
grafo.CrearConexion("Beta", "Epsilon", 240000);
grafo.CrearConexion("Gamma", "Kappa", 360000);
grafo.CrearConexion("Gamma", "Theta", 120000);
grafo.CrearConexion("Iota", "Zeta", 120000);
grafo.CrearConexion("Epsilon", "Eta", 60000);
grafo.CrearConexion("Kappa", "Theta", 180000);
grafo.CrearConexion("Zeta", "Eta", 30000);
var rutas = grafo.ObtenerTodasLasRutas("Kappa", "Zeta");
foreach (var ruta in rutas)
{
Console.WriteLine(String.Join(",", ruta));
}
Console.ReadKey();
}
class Grafo
{
private readonly List<Conexion> _conexiones;
private readonly IEnumerable<string> _vertices;
public Grafo(IEnumerable<string> vertices)
{
_vertices = vertices;
_conexiones = new List<Conexion>();
}
public void CrearConexion(string nodo1, string nodo2, int distancia)
{
if (!_vertices.Contains(nodo1)) throw new ArgumentOutOfRangeException(nameof(nodo1), $"El nodo {nodo1} no existe");
if (!_vertices.Contains(nodo2)) throw new ArgumentOutOfRangeException(nameof(nodo2), $"El nodo {nodo2} no existe");
if (nodo1 == nodo2) throw new ArgumentException("No se puede crear una conexión al mismo nodo");
if (_conexiones.Any(c => c.Nodo1 == nodo1 && c.Nodo2 == nodo2 || c.Nodo1 == nodo2 && c.Nodo2 == nodo1))
throw new ArgumentException($"La conexión entre {nodo1} y {nodo2} ya existe");
if (distancia <= 0) throw new ArgumentOutOfRangeException(nameof(distancia));
_conexiones.Add(new Conexion(nodo1, nodo2, distancia));
}
public IEnumerable<List<string>> ObtenerTodasLasRutas(string origen, string destino)
{
if (!_vertices.Contains(origen)) throw new ArgumentOutOfRangeException(nameof(origen), $"El nodo {origen} no existe");
if (!_vertices.Contains(destino)) throw new ArgumentOutOfRangeException(nameof(destino), $"El nodo {destino} no existe");
var ruta = new List<string> {origen};
return CrearTodasLasRutas(ruta, destino);
}
private IEnumerable<List<string>> CrearTodasLasRutas(List<string> ruta, string destino)
{
var result = new List<List<string>>();
var actual = ruta.Last();
if (actual == destino)
{
result.Add(ruta);
}
else
{
var nodosSiguientes = _conexiones
.Where(c => c.Nodo1 == actual || c.Nodo2 == actual)
.Select(c => c.Nodo1 == actual ? c.Nodo2 : c.Nodo1)
.Distinct()
.Where(n => !ruta.Contains(n));
foreach (var siguiente in nodosSiguientes)
{
var rutaSiguiente = new List<string>(ruta) {siguiente};
result.AddRange(CrearTodasLasRutas(rutaSiguiente, destino));
}
}
return result;
}
}
public struct Conexion
{
public Conexion(string nodo1, string nodo2, int distancia)
{
Nodo1 = nodo1;
Nodo2 = nodo2;
Distancia = distancia;
}
public string Nodo1 { get; }
public string Nodo2 { get; }
public int Distancia { get; }
}
}
}
