7.6. Implementación¶
Utilizando diccionarios, es fácil implementar la lista de adyacencia en Python. En nuestra implementación del tipo abstracto de datos Grafo, crearemos dos clases (ver el Programa 1 y el Programa 2), Grafo, que contiene la lista maestra de vértices, y Vertice, que representará cada vértice en el grafo.
Cada Vertice utiliza un diccionario para realizar un seguimiento de los vértices a los que está conectado, y la ponderación de cada arista. Este diccionario se llama conectadoA. El programa mostrado a continuación corresponde al código de la clase Vertice. El constructor simplemente inicializa el id, que normalmente será una cadena, y el diccionario conectadoA. El método agregarVecino se utiliza para agregar una conexión desde este vértice a otro. El método obtenerConexiones devuelve todos los vértices de la lista de adyacencia, representados por la variable conectadoA. El método obtenerPonderacion devuelve la ponderación de la arista de este vértice al vértice pasado como parámetro.
Programa 1
class Vertice:
def __init__(self,clave):
self.id = clave
self.conectadoA = {}
def agregarVecino(self,vecino,ponderacion=0):
self.conectadoA[vecino] = ponderacion
def __str__(self):
return str(self.id) + ' conectadoA: ' + str([x.id for x in self.conectadoA])
def obtenerConexiones(self):
return self.conectadoA.keys()
def obtenerId(self):
return self.id
def obtenerPonderacion(self,vecino):
return self.conectadoA[vecino]
La clase Grafo, mostrada en el siguiente programa, contiene un diccionario que asigna nombres de vértices a objetos vértice. En la Figura 4 este objeto diccionario está representado por el recuadro sombreado de gris. Grafo también proporciona métodos para agregar vértices a un grafo y conectar un vértice a otro. El método obtenerVertices devuelve los nombres de todos los vértices del grafo. Además, hemos implementado el método __iter__ para facilitar la iteración sobre todos los objetos vértice de un grafo en particular. Juntos, los dos métodos permiten iterar sobre los vértices de un grafo por nombre, o por los objetos mismos.
Programa 2
class Grafo:
def __init__(self):
self.listaVertices = {}
self.numVertices = 0
def agregarVertice(self,clave):
self.numVertices = self.numVertices + 1
nuevoVertice = Vertice(clave)
self.listaVertices[clave] = nuevoVertice
return nuevoVertice
def obtenerVertice(self,n):
if n in self.listaVertices:
return self.listaVertices[n]
else:
return None
def __contains__(self,n):
return n in self.listaVertices
def agregarArista(self,de,a,costo=0):
if de not in self.listaVertices:
nv = self.agregarVertice(de)
if a not in self.listaVertices:
nv = self.agregarVertice(a)
self.listaVertices[de].agregarVecino(self.listaVertices[a], costo)
def obtenerVertices(self):
return self.listaVertices.keys()
def __iter__(self):
return iter(self.listaVertices.values())
Utilizando las clases Grafo y Vertice que acabamos de definir, la siguiente sesión de Python crea el grafo de la Figura 2. Primero creamos seis vértices numerados de 0 a 5. Luego mostramos el diccionario de vértices. Observe que para cada clave de 0 a 5 hemos creado una instancia de Vertice. A continuación, agregamos las aristas que conectan los vértices entre sí. Finalmente, un ciclo anidado verifica que cada arista en el grafo esté almacenada correctamente. Compruebe la salida de la lista de aristas al final de esta sesión comparándola con la Figura 2.
>>> g = Grafo()
>>> for i in range(6):
... g.agregarVertice(i)
>>> g.listaVertices
{0: <__main__.Vertice object>,
1: <__main__.Vertice object>,
2: <__main__.Vertice object>,
3: <__main__.Vertice object>,
4: <__main__.Vertice object>,
5: <__main__.Vertice object>}
>>> g.agregarArista(0,1,5)
>>> g.agregarArista(0,5,2)
>>> g.agregarArista(1,2,4)
>>> g.agregarArista(2,3,9)
>>> g.agregarArista(3,4,7)
>>> g.agregarArista(3,5,3)
>>> g.agregarArista(4,0,1)
>>> g.agregarArista(5,4,8)
>>> g.agregarArista(5,2,1)
>>> for v in g:
... for w in v.obtenerConexiones():
... print("( %s , %s )" % (v.obtenerId(), w.obtenerId()))
...
( 0 , 1 )
( 0 , 5 )
( 1 , 2 )
( 2 , 3 )
( 3 , 5 )
( 3 , 4 )
( 4 , 0 )
( 5 , 2 )
( 5 , 4 )