Figura 1PRÁCTICA Nº 9
(del 29 de Mayo al 9 de Junio de 2000)Grafos: Utilización del recorrrido bfs (recorrido en anchura) para la búsqueda de caminos de recorrido mínimo
Supongamos que tenemos una un sistema de comunicaciones con unos ciertos puntos de enlace y unas relaciones entre estos puntos de enlace. En esta práctica vamos a realizar un módulo del sistema que va a encargarse de establecer rutas de enlace mínimas entre diferentes puntos de enlace o nodos.
Los datos de los puntos de enlace están guardados en el fichero 'Nodos.dat' y las relaciones o arcos existentes entre los nodos se encuentran guardadas en el fichero 'Relacion.dat'
0.- Objetivos
El objetivo de esta práctica es la utilización del recorrido BFS sobre grafos para determinar rutas de enlace ‘mínimas’, refiriéndonos con mínimas a rutas que atraviesen el menor número de nodos posibles.
1.- Representación de una Red Utilizando Grafos
Una red de comunicaciones se puede representar mediante la utilización de un grafo no dirigido, que será conexo, en el que cada nodo represente a una estación de enlace, y las aristas los enlaces entre estaciones.
Por ejemplo, dado el siguiente grafo:
Figura 1
Es conexo, porque desde cualquier nodo se puede acceder a cualquier otro nodo de la red.
El camino minimo entre los nodos 5 y 8 será: (5,13), (13,6), (6,8) que sólo tiene que atravesar 3 arcos. Cualquier otro camino entre los nodos 5 y 8 atravesaría mayor número de arcos.
2.- Realización de la práctica
En esta práctica se trata de leer la información contenida en los ficheros 'Nodos.dat' y 'Relacion.dat' y guardarla en memoria en forma de matriz de adyacencia.
A partir de la matriz de adyacencia y utilizando el recorrido BFS del grafo determinaremos caminos de recorrido mínimo entre dos ciudades previamente introducidas por teclado.
Dados el punto de origen y destino dentro del grafo, estableceremos el recorrido en anchura del grafo, modificándolo ligeramente, para que se detenga en cuanto llegue al nodo destino y muestre por pantalla la longitud del camino recorrido y los nodos atravesados.
Formato de ficheros
Nodos.dat
En el fichero nodos.dat se guarda la información de cada una de las estaciones planetarias (nombre del planeta, código y coordenadas espaciales) en cada una de las lineas del fichero. Por ejemplo:
La Coruna$1$10$4
Nombre del nodo: La Coruna / Código: 1 / Coordenadas: (10, 4)
Relacion.dat
En el fichero relacion.dat se encuentran las relaciones entre los distintos nodos en forma de 'matriz', de manera que en cada fila, 'i' están las relaciones del nodo 'i' (con código ‘i’) con los nodos 'j' de cada columna representados por un uno si existe la relación y un cero si no la hay. Por ejemplo, si tuviesemos 4 nodos, el siguiente fichero de relaciones, representaría las relaciones existentes en el grafo de la figura 2.
0;1;1;0
1;0;1;0
1;1;0;1
0;0;1;0
3.- Tarea Opcional
a.- Representar el grafo mediante listas de adyacencia.
b.- Implementar una unidad gráfica para la representación del grafo en pantalla.
4.- Entrega de Programas
Se entregará un programa en Pascal llamado "grafos.pas" (y opcionalmente la unidad gráfica "dib_gr.pas".)
El plazo improrrogable de entrega de programas termina el día 9 de Junio a las 12:00, en la secretaria del departamento. Indicar en el disquette el grupo de laboratorio, y el nombre de los integrantes del grupo.
Nota Muy Importante
Antes de poder empezar a realizar cualquiera de las prácticas es necesario presentar al profesor un pequeño esquema de las tareas que va a realizar la práctica, explicando brevemente y en lenguaje natural como van a solucionarse los problemas que se plantean.
ENTREGA DE PROGRAMAS:
Antes del 9 de Junio a las 12:00 en la secretaria del departamento.