La pregunta es un poco amplia ya que existen varios algoritmos y multiples implementaciones posibles de cada uno para obtener el camino entre dos nodos de un grafo. Es más, en tu ejemplo al menos hay parejas de nodos que tienen más de un camino entre ellos como A-G o A-H.
Teniendo esto en cuenta hay dos algoritmos muy utilizados para este fin, la búsqueda en profundidad(DFS-Depth First Search) y la búsqueda en anchura(BFS-Breadth First Search). En los links (a Wikipedia) tienes explicado por encima y el pseudocódigo de ambos algoritmos.
Te voy a dejar una implementación de cada uno de ellos que he usado yo alguna vez adaptados a tu código:
import collections
class Vertice:
def __init__(self, n):
self.nombre = n
self.vecinos = list()
self.distancia = 9999
self.color = 'white'
self.pred = -1
def agregarVecino(self, v):
if v not in self.vecinos:
self.vecinos.append(v)
self.vecinos.sort()
class Grafo:
def __init__(self):
self.vertices = dict()
def agregarVertices(self, vertices):
for v in vertices:
n = Vertice(v)
self.agregarVertice(n)
def agregarAristas(self, aristas):
for arista in aristas:
self.agregarArista(arista[0], arista[1])
def agregarVertice(self, vertice):
if isinstance(vertice, Vertice) and vertice.nombre not in self.vertices:
self.vertices[vertice.nombre] = vertice
return True
else:
return False
def agregarArista(self, u, v):
if u in self.vertices and v in self.vertices:
for key, value in self.vertices.items():
if key == u:
value.agregarVecino(v)
if key == v:
value.agregarVecino(u)
return True
else:
return False
def bfs(self, vert):
vert = self.vertices[vert]
vert.distancia = 0
vert.color = 'gray'
vert.pred = -1
q = list()
q.append(vert.nombre)
while len(q) > 0:
u = q.pop()
node_u = self.vertices[u]
for v in node_u.vecinos:
node_v = self.vertices[v]
if node_v.color == 'white':
node_v.color = 'gray'
node_v.distancia = node_u.distancia + 1
node_v.pred = node_u.nombre
q.append(v)
self.vertices[u].color = 'black'
def imprimeGrafo (self):
for key in sorted(list(self.vertices.keys())):
print ("Vertice " + key + " sus vecinos son "+ str(self.vertices[key].vecinos) )
print("La distancia de A a " + key + " es: "+ str(self.vertices[key].distancia))
print()
def dfs_paths(self, vertice_inicial, vertice_final, camino=None):
if camino == None:
camino = [vertice_inicial]
if vertice_inicial == vertice_final:
yield camino
for vertice in (v for v in self.vertices[vertice_inicial].vecinos if v not in set(camino)):
yield from self.dfs_paths(vertice, vertice_final, camino + [vertice])
def bfs_paths(self, vertice_inicial, vertice_final):
cola = collections.deque()
cola.append((vertice_inicial, [vertice_inicial]))
while cola:
(v, camino) = cola.pop()
for vertice in set(self.vertices[v].vecinos) - set(camino):
if vertice == vertice_final:
yield camino + [vertice]
else:
cola.append((vertice, camino + [vertice]))
#Creamos un grafo como en tu ejemplo al que llamamos g1:
vertices = [chr(i) for i in range(ord('A'), ord('K'))]
edges = ['AB','AE','BF','CG','DE','DH','EH','FG','FI','FJ','GJ']
g1 = Grafo()
g1.agregarVertices(vertices)
g1.agregarAristas(edges)
g1.bfs('A')
print('Caminos no cíclicos posibles desde "A" a "H" usando busqueda en profundidad:')
caminos = g1.dfs_paths('A','H')
print(list(caminos))
print('\nCaminos no cíclicos posibles desde "A" a "H" usando busqueda en en anchura:')
caminos = g1.bfs_paths('A','H')
print(list(caminos))
Ambas funciones usan recursividad, permiten calcular todos los caminos no cíclicos (no se puede visitar un nodo dos veces en un mismo camino) entre dos nodos cualquiera. Ambas funciones retornan generadores, en este caso los paso a listas para que se vean todos los caminos. Para la implementación de BFS se usa una cola mediante collections.deque()
de la biblioteca estándar dado que es mucho más eficiente que usar una lista para las operaciones que se realizan. Ten en cuenta que BFS
retorna el camino más corto en primer lugar. El código es válido para Python 3.x y obtenemos la siguiente salida:
Caminos no cíclicos posibles desde "A" a "H" usando busqueda en profundidad:
[['A', 'E', 'D', 'H'], ['A', 'E', 'H']]
Caminos no cíclicos posibles desde "A" a "H" usando busqueda en en anchura:
[['A', 'E', 'H'], ['A', 'E', 'D', 'H']]
Hay dos caminos posibles entre el nodo A
y el nodo H
, cada camino aparece representado como una lista con los nodos que lo forman.
Una recomendación es que, si no necesitas por alguna razón muy concreta y justificada tener los vecinos de cada nodo ordenados, uses un conjunto (set
) y no una lista para guardarlos en tu clase Vértices
(self.vecinos = set()
). Para ello tendrias que modificar algunos métodos como agregarVecino
pero es infinitamente más eficiente ya que la búsqueda en un conjunto es mucho más rápida que en una lista al implementarse mediante hash-table. Si vas a implementar grafos pequeños a lo mejor no importa mucho pero en nada que sean algo extensos y dada la complejidad que tienen los algoritmos la eficiencia llega a ser fundamental si no se quiere que una búsqueda dure horas....