Skip to main content
título editado
Enlace
A. Cedano
  • 95.2k
  • 31
  • 145
  • 257

Como ¿Cómo puedo implementar un metodométodo que permita obtener el camino del vértice inicial a otro vértice del grafo?

Origen Enlace
Johan Cancino
  • 117
  • 1
  • 2
  • 8

Como puedo implementar un metodo permita obtener el camino del vértice inicial a otro vértice del grafo?

Hola tengo el siguiente codigo:

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 camino(self, u, v):
    
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 del vertice A a " + key + " es: "+ str(self.vertices[key].distancia))
        print()



#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')

En este caso quisiera implementar un metodo que me indique cual es el recorrido del vertice inicial, en este caso 'A' hacia otro que se indique. Alguien es tan amable de orientarme en este programa.