Grafos Java Ejercicio

EJERCICIO SOBRE GRAFOS

Considere la siguiente descripción sobre Ciudades y la existencia de Vuelos directos entre ellas:
Las ciudades son:
Habana (HA),Matanzas (MA), StaClara (SC), Camagüey (CA), Holguín (HL), Guantánamo (GU)
Los vuelos directos son:
De la Habana a todas las ciudades y de ellas a la Habanaexcepto a Guantánamo a la cual no hay vuelos directos desde/hacia la Habana
Hay vuelo directo de Matanzas a StaClara, pero no de StaClara a Matanzas
Hay vuelo directode StaClara a Camagüey, pero no de Camagüey a StaClara
Hay vuelo directo de Camagüey a Matanzas, pero no de Matanzas a Camagüey
Hay vuelo directo de Holguín aGuantánamo y viceversa.

a) Construya (y dibuje) un grafo que represente dicha información
b) Construya un programa en Java que primero cree el grafo anterior yluego muestre un menú para realizar las siguientes opciones:
1. Mostrar todos los vuelos directos que hay entre las ciudades
2. Dada una ciudad C,mostrar todos los vuelos que parten de esa ciudad
3. Dada una ciudad C, mostrar todos los vuelos que llegan a esa ciudad
4. Dadas dos ciudades C1 y C2determinar si existe una ruta que permita llegar de C1 a C2






Algoritmo para encontrar un Camino de un Vértice a otro:

Algoritmo BuscarCamino( G, vi,vf, padres[] )
G: grafo
vi: vértice incial
vf: vértice final
padres[]: arreglo donde quedará el camino
Inicio:
1) Para todos los vértices v delGrafo G hacer
padres[v] = -1
finpara

2) Crear una cola e Insertar en ella el vértice inicial vi

3) mientras la cola no sea vacía hacer
3.a) v