7.3. El tipo abstracto de datos grafo¶

El tipo abstracto de datos (TAD) grafo está definido como sigue:

Grafo() crea un grafo nuevo y vacío.
agregarVertice(vert) agrega una instancia de Vertice al grafo.
agregarArista(deVertice, aVertice) agrega al grafo una nueva arista dirigida que conecta dos vértices.
agregarArista(deVertice, aVertice, ponderacion) agrega al grafo una nueva arista ponderada y dirigida que conecta dos vértices.
obtenerVertice(claveVert) encuentra el vértice en el grafo con nombre claveVert.
obtenerVertices() devuelve la lista de todos los vértices en el grafo.
in devuelve True para una instrucción de la forma vertice in grafo, si el vértice dado está en el grafo, False de lo contrario.

A partir de la definición formal de un grafo, hay varias maneras de implementar el TAD grafo en Python. Veremos que hay concesiones mutuas en el uso de diferentes representaciones para implementar el TAD descrito anteriormente. Hay dos implementaciones bien conocidas de un grafo, la matriz de adyacencia y la lista de adyacencia. Explicaremos ambas opciones y luego implementaremos una como una clase en Python.