El tipo abstracto de datos de los grafos
1. El tipo abstracto de datos de los grafos
Un grafo es una estructura que consta de un conjunto de vértices y un conjunto de aristas que conectan los vértices entre sí. Cada vértice representa una entidad o un elemento, y cada arista representa una relación o conexión entre dos vértices.
Por ejemplo,
12 1 -------- 2 | \78 /| | \ 32/ | | \ / | 34| 5 |55 | / \ | | /44 \ | | / 93\| 3 -------- 4 61
representa un grafo no dirigido, lo que significa que las aristas tienen una dirección específica. Cada arista tiene un peso asociado, que puede representar una medida o una valoración de la relación entre los vértices que conecta.
El grafo consta de cinco vértices numerados del 1 al 5. Las aristas especificadas en la lista indican las conexiones entre los vértices y sus respectivos pesos. Por ejemplo, la arista (1,2,12) indica que existe una conexión entre el vértice 1 y el vértice 2 con un peso de 12.
En el grafo representado, se pueden observar las conexiones entre los vértices de la siguiente manera:
- El vértice 1 está conectado con el vértice 2 (peso 12), el vértice 3 (peso 34) y el vértice 5 (peso 78).
- El vértice 2 está conectado con el vértice 4 (peso 55) y el vértice 5 (peso 32).
- El vértice 3 está conectado con el vértice 4 (peso 61) y el vértice 5 (peso 44).
- El vértice 4 está conectado con el vértice 5 (peso 93).
Las operaciones del tipo abstracto de datos (TAD) de los grafos son
creaGrafo :: (Ix v, Num p, Ord v, Ord p) => Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p creaGrafo' :: (Ix v, Num p, Ord v, Ord p) => Orientacion -> (v,v) -> [(v,v)] -> Grafo v p dirigido :: (Ix v,Num p) => (Grafo v p) -> Bool adyacentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v] nodos :: (Ix v,Num p) => (Grafo v p) -> [v] aristas :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)] aristaEn :: (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool peso :: (Ix v,Num p) => v -> v -> (Grafo v p) -> p
tales que
+ creaGrafo o cs as es un grafo (dirigido o no, según el de o), con el par de cotas cs y listas de aristas as (cada arista es un trío formado por los dos vértices y su peso).
+ creaGrafo' es la versión de creaGrafo para los grafos sin pesos.
+ dirigido g se verifica si g es dirigido.
+ nodos g es la lista de todos los nodos del grafo g.
+ aristas g es la lista de las aristas del grafo g.
+ adyacentes g v es la lista de los vértices adyacentes al nodo v en el grafo g.
+ aristaEn g a se verifica si a es una arista del grafo g.
+ peso v1 v2 g es el peso de la arista que une los vértices v1 y v2 en el grafo g.
Usando el TAD de los grafos, el grafo anterior se puede definir por
creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)]
con los siguientes argumentos:
- ND: Es un parámetro de tipo Orientacion que indica si el es dirigido o no. En este caso, se utiliza ND, lo que significa "no dirigido". Por lo tanto, el grafo creado será no dirigido, lo que implica que las aristas no tienen una dirección específica.
- (1,5): Es el par de cotas que define los vértices del grafo. En este caso, el grafo tiene vértices numerados desde 1 hasta 5.
- [(1,2,12),(1,3,34),(1,5,78),(2,4,55),(2,5,32),(3,4,61),(3,5,44),(4,5,93)]: Es una lista de aristas, donde cada arista está representada por un trío de valores. Cada trío contiene los dos vértices que están conectados por la arista y el peso de dicha arista.
Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos las siguientes: + mediante lista de adyacencia, + mediante vector de adyacencia y + mediante matriz de adyacencia.
Hay que elegir la que se desee utilizar, descomentándola y comentando las otras.