Grafos

Prácticas de Laboratorio Cerrado

Laboratorio de Programación

Implementación en Java de Grafos Dirigidos

Un grafo es un conjunto de nodos unidos por un conjunto de líneas o flechas. Existen grafos dirigidos y grafos no dirigidos. En los grafos dirigidos, los nodos están unidos mediante flechas que indican una dirección. En los grafos no dirigidos los nodos están unidos mediante enlacesque no indican dirección. En esta práctica implementaremos en Java un grafo dirigido. En la figura 1 vemos un ejemplo de grafo dirigido.
Figura 1: Ejemplo de grafo dirigido

1 Especificación Informal de un Grafo Dirigido

Grafo = TDA con operaciones crea, insertaNodo, insertaEnlace, esVacio, contieneNodo, contieneEnlace, borraNodo, borraEnlace, listaNodos, listaEnlaces,estableceMarca, recuperaMarca, recuperaPeso, nNodos, recorridoProfundidad

DESCRIPCIÓN:
Los valores del TDA Grafo son grafos dirigidos de elementos del tipo Elemento. Los grafos son mutables: insertaNodo, insertaEnlace, borraNodo y borraEnlace añaden y eliminan nodos y enlaces respectivamente y estableceMarca cambia la marca asignada a un nodo.

OPERACIONES:

crea() devuelve (G:Grafo)- efecto: Devuelve el grafo vacío G.

insertaNodo(G:Grafo, E:Elemento)
- efecto: si no existe un elemento igual a E en un nodo del grafo G, entonces inserta un nuevo nodo en el grafo G con el elemento E.

insertaEnlace(G:Grafo, E1:Elemento, E2:Elemento, Peso:real)
- efecto: si existen dos nodos en el grafo G con los elementos E1 y E2 y no existe un enlace en el grafo G desdeel nodo con elemento E1 al nodo con elemento E2, entonces crea un nuevo enlace desde el nodo con elemento E1 al nodo con elemento E2 y le asigna un peso igual a Peso.

esVacio(G:Grafo) devuelve (booleano)
- efecto: devuelve cierto si G es el grafo vacío, y falso en caso contrario.

contiene(G:Grafo, E:Elemento) devuelve (booleano)
- efecto: devuelve cierto si el grafo G contieneun nodo con el elemento E, y falso en caso contrario.

borraNodo(G:Grafo, E:Elemento)
- efecto: si el grafo G contiene un nodo con el elemento E, entonces elimina dicho nodo del grafo G.

borraEnlace(G:Grafo, E1:Elemento, E2:Elemento)
- efecto: si existe en el grafo G un enlace que une el nodo con elemento E1 al nodo con elemento E2, entonces elimina dicho enlace del grafo G.listaNodos(G:Grafo) devuelve (Lista)
- efecto: devuelve una lista con los nodos del grafo G.

listaEnlaces(G:Grafo, E:Elemento) devuelve (Lista)
- efecto: devuelve una lista con los nodos a los cuales llega un enlace desde el nodo con elemento E del grafo G.

estableceMarca(G:Grafo, E:Elemento, Marca:entero)
- efecto: si el grafo G contiene un nodo con el elemento E, asignaa dicho nodo el valor de marca Marca.

recuperaMarca(G:Grafo, E:Elemento) devuelve (entero)
- efecto: si el grafo G contiene un nodo con el elemento E , devuelve el valor de marca asignado a dicho nodo.

recuperaPeso(G:Grafo, E1:Elemento, E2:Elemento) devuelve (real)
- efecto: si existe en el grafo G un enlace que une el nodo con elemento E1 al nodo con elemento E2, entoncesdevuelve el peso asignado a dicho enlace.

nNodos(G:Grafo) devuelve (entero)
- efecto: devuelve el número de nodos del grafo G.

recorridoProfundidad(G:Grafo) devuelve (Lista)
- efecto: devuelve una lista con los nodos del grafo G recorridos en profundidad.

2 Técnicas de implementación de un Grafo Dirigido

Existen básicamente dos formas de implementar un grafo. La primera esmediante una matriz que represente los enlaces entre los diferentes nodos. Si existen n nodos, tendremos una matriz de dimensión n x n donde el elemento ij de la matriz indica si entre el nodo i y el nodo j existe un enlace y su peso. Por ejemplo, para el grafo de la figura 1, la matriz asociada sería la siguiente:

| |A |B |C |D |E...