																															 //DiGrafo.CPP
/*En este programa se implementan algoritmos básicos para manejo de un grafo
dirigido, por medio de la estructura de datos lista de listas (listas simplemente enlazadas). En los nodos de la lista principal se almacenan cada uno de los vertices del grafo. En los nodos de cada una de las sublistas(lista de
adyacencia) se almacenan las aristas del grafo. Se efectúan recorridos en profundidad, con ayuda de una Pila, y recorrido en anchura, con ayuda de una Cola. Tambi‚n se implementa el algoritmo de Dijkstra.  */
//--------------------------------------------------------------------
//Archivos a incluir:
#include <graphics.h>
#include <IOStream.h>
#include <IOManip.h>
#include <FStream.h>
#include <ConIO.h>
#include <StdIO.h>
#include <StdLib.H>
#include <DOS.h>
#include <String.H>
#include <CType.H>
#include <Math.H>

//--------------------------------------------------------------------
//Definiciones de constantes:
const unsigned long Infinito=4294967295/2;//Máximo unsigned long
//advertencia: Solo utilizar pesos de aristas hasta 4294967295/2
//esto debido a que tendremos que hacer comparaciones de
//infinito>infinito + peso  y no nos dar¡a el c lculo.
//Si el peso de las aristas tiene decimales, cambiar todos los unsigned int
//de este programa, al tipo numerico conveniente

const char NombreArch[20] = "DiGrafo.Dat";

const	int AltoIcono=20, AnchoIcono=150, MaxIco=3,
		Xi=1, Yi=1, DeltaX=AnchoIcono+2,
		PaletaXi=1, PaletaYi=460, AltoPaleta=20, LargoPaleta=40,
		MaxColores=16,
		EspacioGrafoXo=0, EspacioGrafoYo=AltoIcono+2,
		EspacioGrafoXf=639, EspacioGrafoYf=479-AltoPaleta,
		AnchoVertice=10; //del cuadrado que representa cada vertice
//--------------------------------------------------------------------
//Definiciones de tipos de datos registros(struct)
typedef struct VERTICE VERTICE;
typedef struct ARISTA ARISTA;
typedef struct INFOVERTICE INFOVERTICE;
typedef struct INFOARISTA INFOARISTA;

struct INFOARISTA{
	unsigned long PesoArista;
	char NombreDestino;  // Etiqueta del vértice de destino de la arista
};

struct ARISTA{
	INFOARISTA Info; // informacion de cada arista
	VERTICE *Ady;   //puntero desde el vértice de origen al vértice de destino
	ARISTA *Sig;    //puntero en la lista anlazada de aristas
};

struct INFOVERTICE{
	char NombreVertice;  // Etiqueta del vértice
	char Estado; //En los recorridos. 1:Preparado, 2:Espera, 3:Procesado
	int x, y; //Posicion del vértice en la pantalla
	unsigned long d; //En algoritmo de Dijkstra es distancia acumulada m¡nima
};

struct VERTICE{
	INFOVERTICE Info; //Informacion propia de cada nodo.
	ARISTA *Cab;//Apunta a cada sublista desde cada nodo de la lista principal
	VERTICE *Sig;//Apunta al siguiente vértice en la lista enlazada. El
//siguiente vertice no quiere decir que este adyacente en el
//grafo, esto solo ser‚ de casualidad. Para los adyacentes ver struct ARISTA
	VERTICE *Predecesor; //En algunos recorridos, sera el vertice anterior.
				//El padre si vemos el recorrido como un arbol.
				//en otros casos, no aun aqui, podria ser una lista de 
                     //los nodos que llegan a este(es decir aristas que llegan)
};
//-----------------------------------------------------------------------------
//Definicion de variables globales:
struct VERTICE *CAB=NULL;// variable global la cual apuntar  a la cabeza de la
	// lista simplemente enlazada que almacena los vértices(nodos) del grafo.
fstream BufferArchivo; //

int N=0;//Este ser  el número de vértices en el grafo.

//------------------------------------------------------------------------------
//A continuación las funciones del programa
//------------------------------------------------------------------------------
VERTICE *InsertarVerticeEnGrafo (INFOVERTICE Item){//Inserta en la lista principal
	VERTICE *p, *q, *NuevoNodo;

	NuevoNodo = new(VERTICE);
	if ( NuevoNodo == NULL ) {
		cout << "No hay memoria suficiente";
		return(NULL);  // No insertado
	}

	p = NULL;
	q = CAB;
	while (q != NULL && Item.NombreVertice > q->Info.NombreVertice){
		p = q;
		q = q->Sig;
	}

	if (q && Item.NombreVertice == q->Info.NombreVertice) {
		delete(NuevoNodo);
		return (NULL);  //repetido,
	}
	NuevoNodo->Info = Item;
	NuevoNodo->Sig  = q;
	NuevoNodo->Cab  = NULL;

	if ( p == NULL)
		CAB = NuevoNodo;  //era el primero de la lista
	else
		p->Sig = NuevoNodo; //"caso general"

	return(NuevoNodo); // insertado
}
//------------------------------------------------------------------------------
int EliminarVerticeDelGrafo(VERTICE *p){
 VERTICE *q;

	if (p == CAB)
		CAB = p->Sig; //eliminado el primer VERTICE de la lista
	else {
		q = CAB;
		while (q->Sig != p)
			q = q->Sig;
			q->Sig = p->Sig;
	}
	delete(p);

	return 1;
}
//------------------------------------------------------------------------------
VERTICE* EncontrarVerticeDelGrafo(INFOVERTICE Item){
	VERTICE *p;

	p = CAB;
	while (p && Item.NombreVertice > p->Info.NombreVertice)
		p = p->Sig;

	if(p && Item.NombreVertice != p->Info.NombreVertice)  // No encontrado
		p= NULL;

	return p;
}
//------------------------------------------------------------------------------
void ListarVerticesDelGrafo(){

	if (!CAB)
		cout << "Lista vac¡a \a";
	else {
		VERTICE *p = CAB;
		int i=0;
		cout << "Orden en lista    Etiqueta\n";
		while ( p ){
			cout << setw(5) << ++i
			 << "            " << p->Info.NombreVertice << endl;
			p = p->Sig;
		}
	}
}
//------------------------------------------------------------------------------
void CapturarVertice(){
	INFOVERTICE Item;

	cout << "\n\Nombre de la etiqueta del v‚rtice: ";
		Item.NombreVertice = getche();

	if ( InsertarVerticeEnGrafo(Item) == 0 ){
		cout << "\n\nRepetido \a";
		getch();
	}
}
//------------------------------------------------------------------------------
void EliminarVertice(){
	INFOVERTICE Item;
	VERTICE *Vertice;

	if (CAB == NULL)
		cout << "Lista vac¡a \a";
	else{
		cout << "\n\nDigite etiqueta del v‚rtice: ";
		Item.NombreVertice	= getche();
		Vertice = EncontrarVerticeDelGrafo(Item);
		if (Vertice)
			if(!Vertice->Cab)  //Se elimina, solo si no tiene adyacentes
				EliminarVerticeDelGrafo(Vertice);
			else{
				cout<<"\n\nEste vertice tiene todavia aristas. ";
				getch();
			}
		else {
			cout <<"\n\nNo encontrado en grafo un vértice con el nombre: "
				 << Item.NombreVertice;
			getch();
		}
	}
}
//-----------------------------------------------------------------------------
void EncontrarVertice(){
	INFOVERTICE Item;
	VERTICE *Vertice;

	if (CAB == NULL)
		cout << "Lista vac¡a \a";
	else{
		cout << "\n\nDigite etiqueta del vértice a encontrar: ";
		Item.NombreVertice = getche();
		Vertice = EncontrarVerticeDelGrafo(Item);
		if (Vertice)
			cout << "\n\nEncontrado en grafo";
		else
			cout << "\n\nNo encontrado en grafo";
	}
	getch();
}

// ===========================================================================
// A CONTINUACION LAS FUNCIONES PARA MANEJAR CADA ARISTA(SubLista enlazada)
// ===========================================================================

ARISTA *InsertarArista (INFOARISTA Item, ARISTA *Cab, VERTICE *Destino){
	ARISTA *p, *q, *NuevoNodo;

	if ( (NuevoNodo = new ARISTA ) == NULL ){
		cout << "No hay memoria suficiente";
		return NULL;
	}
	//Se insertar n en orden ascendente por el peso de la arista
	p = NULL;
	q = Cab;
	while (q != NULL && Item.PesoArista > q->Info.PesoArista){
		p = q;
		q = q->Sig;
	}

	NuevoNodo->Info = Item;
	NuevoNodo->Sig  = q;
	NuevoNodo->Ady  = Destino;

	if ( p == NULL)
		Cab = NuevoNodo;  //era el primero de la lista
	else
		p->Sig = NuevoNodo; //"caso general"
	return(Cab);
}
//------------------------------------------------------------------------------
ARISTA *EliminarArista(ARISTA *p, ARISTA *Cab){
	ARISTA *q;

	if (p == Cab)
		Cab = p->Sig; //eliminado el primer nodo de la lista
	else {
		q = Cab;
		while (q->Sig != p)
			q = q->Sig;
			q->Sig = p->Sig;
	}
	delete(p);
	return Cab;
}
//------------------------------------------------------------------------------
ARISTA* EncontrarArista(ARISTA *Cab, VERTICE *Destino){
	ARISTA *p;

	p = Cab;
	while (p && Destino != p->Ady)
		p = p->Sig;

	return p;
}
//------------------------------------------------------------------------------
void ListarSubListaDeAristas(ARISTA *Cab){
	ARISTA *p;
	int Adyacentes=0;

	if (!Cab)
		cout << "No tiene aristas \a\n";
	else {
		p = Cab;
		cout << "No.   Peso   Etiqueta Destino\n";
		while ( p ){
			cout << setw(2) << ++Adyacentes << ":   "
			 << setiosflags(ios::left) << setw(10) << p->Info.PesoArista
				 << setw(15) << p->Ady->Info.NombreVertice << endl;
			p = p->Sig;
		}
	}
}
//------------------------------------------------------------------------------
ARISTA *CapturarSubLista(ARISTA *Cab){
	INFOARISTA ItemArista;
	INFOVERTICE ItemVertice;
	VERTICE *Destino;

	cout << "\n\Etiqueta vértice de destino: ";
	cin >> ItemVertice.NombreVertice;

	Destino= EncontrarVerticeDelGrafo(ItemVertice);
	if(Destino){
		cout << "\n\Peso de la arista a insertar: ";
		cin >> ItemArista.PesoArista;
		ItemArista.NombreDestino = ItemVertice.NombreVertice;
		Cab = InsertarArista(ItemArista, Cab, Destino );
		if ( !Cab  ){
			cout << "\n\nNo se pudo insertar: se lleno la memoria\a";
			getch();
		}
	}
	else{
		cout << "\n\aEste destino no existe en el grafo\a";
		getch();
	}
	return Cab;
}
//------------------------------------------------------------------------------
ARISTA *BorrarSubLista(ARISTA *Cab){
	INFOVERTICE Item;
	ARISTA *A;
	VERTICE *Destino;

	if (Cab == NULL)
		cout << "Lista vac¡a \a";
	else {
		cout << "\n\nDigite etiqueta del nombre del  vértice de destino: ";
		Item.NombreVertice = getche();
		Destino= EncontrarVerticeDelGrafo(Item);
		if(Destino){ // Se encontro el destino, veamos si forma arista:
			A = EncontrarArista(Cab, Destino);
			if (A)
				Cab = EliminarArista(A, Cab);
			else {
				cout << "\n\nNo encontrada esta arista";
				getch();
			}
		}
		else{
			cout << "\n\nNo encontrado en grafo el vértice " << Item.NombreVertice;
			getch();
		}
	}
	return Cab;
}
//------------------------------------------------------------------------------
void EncuentraSubLista(ARISTA *Cab){
	INFOVERTICE Item;
	ARISTA 	*p;
	VERTICE *Destino;

	if (Cab == NULL)
		cout << "Lista vac¡a \a";
	else{
		cout << "\n\nDigite Nombre de vértice de destino: ";
		Item.NombreVertice = getch();
		Destino= EncontrarVerticeDelGrafo(Item);
		if(Destino){
			p = EncontrarArista(Cab, Destino);
			if (p)
				cout << "\n\nEncontrada esta arista y tiene el peso "
						 << p->Info.PesoArista;
			else
				cout << "\n\nNo encontrada arista al vertice  "
					<< Item.NombreVertice;
		}
		else
			cout  <<"\n\nNo existe vertice de destino" <<Item.NombreVertice;
	}
	getch();
}
//------------------------------------------------------------------------------
void MenuSubListaDeAristas(){
	char op;
	INFOVERTICE Item;
	VERTICE *q;

	if(CAB){
		clrscr();
		cout << "Nombre del vértice de origen: ";
		Item.NombreVertice = getche();
		q = CAB;
		while (q && Item.NombreVertice != q->Info.NombreVertice)
				q = q->Sig;

		if (!q){
			cout << "No se encuentra ningun vértice de etiqueta: " << Item.NombreVertice;
			getch();
		}
		else
			do{
				clrscr();
				cout << "Estas son las aristas del vértice: "
						 << q->Info.NombreVertice << endl;
				ListarSubListaDeAristas(q->Cab);
				cout<< "\nMENU ARISTAS: Insertar Borrar Encontrar ESC";
				op = toupper(getch());
				switch (op){
					case 'I': q->Cab=CapturarSubLista(q->Cab); break;
					case 'B': q->Cab=BorrarSubLista(q->Cab);   break;
					case 'E': EncuentraSubLista(q->Cab);       break;
				}
			} while (op != 27);
	}
	else{
		cout << "No hay vértices en el grafo\a";
		getch();
	}
}
//===========================================================================
void GrabarSubListas(VERTICE *V){  // funcion recursiva
	ARISTA *A;
	int n;

	if ( V ) {
		A = V->Cab;
		n = 0;
		while(A) { //Cuenta # nodos en sublista enlazada de aristas
			n++;
			A=A->Sig;
		}
		BufferArchivo.write((char *)&n, sizeof(n)); 
			//Graba en disco #nodos(aristas)

		A = V->Cab;
		while(A) {
			BufferArchivo.write((char *)&A->Info, sizeof(A->Info));
			A=A->Sig;
		}
		GrabarSubListas(V->Sig);
	}
}
//------------------------------------------------------------------------------
void GrabarGrafo(){
	int NumeroVertices=0;

	BufferArchivo.open(NombreArch, ios::out|ios::binary|ios::trunc);
	if (!BufferArchivo)
		cout << "Error en la apertura del archivo \a";
	else{
		VERTICE *V;

		V = CAB;   //Se cuentan y luego graban el número de vértices
		while(V){
			NumeroVertices++;
			V = V->Sig;
		}
		BufferArchivo.write((char *)&NumeroVertices,sizeof(NumeroVertices));

		V = CAB;   //Se graban a continuacion la info de todos los vértices
		while(V){
			BufferArchivo.write((char *)&V->Info, sizeof(V->Info));
			V = V->Sig;
		}

		GrabarSubListas(CAB);//graba, recursivamente
		BufferArchivo.close();
	}
}
//------------------------------------------------------------------------------
void CargarLISTA_y_SubListas(){
	INFOVERTICE Vertice; //registro que lee con info de cada vertice
	VERTICE *V, *Destino;
	int n; //número de nodos en cada sublista, lo lee desde disco cada vez
	int NumeroVertices=0;
	INFOARISTA Arista; //registro que lee con info de cada arista

	CAB = NULL;  //Esta variable se mantiene global
	BufferArchivo.open(NombreArch,ios::in|ios::binary);
	if (!BufferArchivo){
		cout << "No se puede abrir el archivo \a\n";
	}
	else {
		BufferArchivo.read((char *)&NumeroVertices, sizeof(NumeroVertices));

		int i=0;//a continuacion lee desde disco, todos los vertices y los
						//inserta en lista enlazada principal
		while(i < NumeroVertices){
			BufferArchivo.read( (char *)&Vertice, sizeof(Vertice) );
			InsertarVerticeEnGrafo(Vertice);
			i++;
		}
	//A continuacion se recorre la lista enlazada de vértices, ya en RAM y
	//simultaneamente se leen de disco, para cada vertice, el número de
	//aristas y  luego cada una de ellas(insertandolas en el lugar corrrepondiente)
		V = CAB;
		while(V){
			BufferArchivo.read( (char *)&n, sizeof(n) );
			//en la instrucción anterior se graba el # nodos(aristas) en cada sublista
			V->Cab=NULL;//ya estaba en nulo, no es necesario
			for(i=0; i<n; i++){
				BufferArchivo.read( (char *)&Arista, sizeof(Arista));
				//buscar su  enlace adyacente  NombreDestino
				Destino = CAB;
				while(Destino && Destino->Info.NombreVertice != Arista.NombreDestino)
					Destino = Destino->Sig;

				if(Destino)
					V->Cab = InsertarArista(Arista, V->Cab, Destino);
				else
					return;//ERROR:dado como se grabo en disco, es de
									//esperar nunca ocurrir.Entonces sobra
		}
			V = V->Sig;
		}
		BufferArchivo.close();
	}
}
//------------------------------------------------------------------------------
void ListarGrafoComoTexto(){

	if (!CAB)
		cout << "Lista vac¡a \a\n";
	else {
		VERTICE *V = CAB;
		ARISTA *A;

		cout << "ORIGEN     DESTINO   DISTANCIA ARISTA\n";
		while ( V ){
			if (V->Cab){
				A = V->Cab;
				while ( A ){
					cout 	<< V->Info.NombreVertice
						<< "          " << A->Ady->Info.NombreVertice
						<< "          " << setw(10) << A->Info.PesoArista << endl;
					A = A->Sig;
				}
			}
			else
				cout << setw(2) << V->Info.NombreVertice << endl;

			V = V->Sig;
		}
	}
}
//------------------------------------------------------------------------------
//ALGORITMO DE RECORRIDO EN PROFUNDIDAD UTILIZANDO UNA PILA
//------------------------------------------------------------------------------
struct Pila{
	VERTICE *V;
	Pila *Sig;
} *Cima = NULL;
//------------------------------------------------------------------------------
void InsertarEnPila(VERTICE *V){
	Pila *Nuevo;

	Nuevo = new Pila;
	Nuevo->V = V;
	Nuevo->Sig = Cima;
	Cima = Nuevo;
}
//------------------------------------------------------------------------------
VERTICE *SacarDePila(){
	VERTICE *EnCima;
	Pila  *p;

	EnCima = Cima->V;
	p = Cima;
	Cima = Cima->Sig;
	delete(p);
	return EnCima;
}
//------------------------------------------------------------------------------
void RecorridoEnProfundidad(){ //Al utilizar una Pila. Los nodos adyacentes
//estan siendo procesados de mayor arista primero a menor. Ya que la sublista
//esta clasificada en orden ascendente. Primero el menor, pero al colocarlos
//en Pila quedan al contrario. Es decir que esta prefiriendo el mayor.
//Para que tome el menor habria que modificar esta funcion y que lo haga
//recursivamente, la insercion en la Pila
	INFOVERTICE Item;
	VERTICE *Origen, *p, *N;
	ARISTA *A;
	if(CAB){
		cout << "\nDigite la etiqueta del vértice de origen: ";
		cin >>Item.NombreVertice;
		Origen = EncontrarVerticeDelGrafo(Item);
		if(!Origen)
			cout << "\nVértice no existe en el Grafo\a";
		else{
			p = CAB;
			while(p){
				p->Info.Estado = 1;
				p = p->Sig;
			}
			InsertarEnPila(Origen);
			Origen->Info.Estado = 2;
			cout << endl;
			while(Cima){ //Mientras que la cola no est‚ vac¡a
				N = SacarDePila();
				cout << N->Info.NombreVertice << "  ";
				N->Info.Estado = 3;
				A = N->Cab;
				while(A){
					if(A->Ady->Info.Estado == 1){
						InsertarEnPila(A->Ady);
						A->Ady->Info.Estado = 2;
					}
					A = A->Sig;
				}
			}
		}
		getch();
	}
}
//-----------------------------------------------------------------------------
//ALGORITMO DE RECORRIDO EN ANCHURA UTILIZANDO UNA COLA
//-----------------------------------------------------------------------------
struct Cola{
	VERTICE *V;
	Cola *Sig;
} *Frente = NULL, *Final=NULL, *Q=NULL, *q=NULL;

void InsertarEnColas(VERTICE *V){
	Cola *Nuevo;

	Nuevo = new Cola;
	Nuevo->V = V;
	Nuevo->Sig = NULL;
	Nuevo->V->Info.d = Infinito; //Se necesitan en Alg. Dijkstra
	Nuevo->V->Predecesor = NULL; // en otro caso no importa
	if(!Q){ //De esta cola no se retiran los elementos
		Q = q = Nuevo;
		Nuevo->V->Info.d = 0; //Lo necesita Alg. Dijkstra. Es nodo fuente
	}
	else{
		q->Sig = Nuevo;
		q = Nuevo;
	}
	if(!Frente){
		Frente = Final = Nuevo;
	}
	else{
		Final->Sig = Nuevo;
		Final = Nuevo;
	}
}
//-----------------------------------------------------------------------------
VERTICE *AtenderFrenteDeCola(char EsDijkstra){
	VERTICE *AlFrente;
	Cola  *p;

	AlFrente = Frente->V;
	if(EsDijkstra=='N')
		p = Frente;
	Frente = Frente->Sig;
	if(EsDijkstra=='N')    //Si es 'S' no se deben borrar los valores en cola
		delete(p); //frente avanzar  hasta terminar, pero Q apunta al inicio
	return AlFrente;
}
//-----------------------------------------------------------------------------
int RecorridoEnAnchura(char EsDijkstra){
	INFOVERTICE Item;
	VERTICE *Origen, *p, *N;
	ARISTA *A;

	Frente = NULL, Final=NULL, Q=NULL, q=NULL;
	if(CAB){
		cout << "\nDigite la etiqueta del vértice de origen: ";
		Item.NombreVertice = getche();
		Origen = EncontrarVerticeDelGrafo(Item);
		if(!Origen){
			cout << "\nVértice no Existe en el Grafo\a";
			return 0;
		}
		else{
			p = CAB;
			while(p){
				p->Info.Estado = 1;
				p = p->Sig;
			}

			InsertarEnColas(Origen);
			Origen->Info.Estado = 2;
			cout << endl;
			while(Frente){ //Mientras que la cola no est‚ vac¡a.
				if(EsDijkstra=='S')
					N = AtenderFrenteDeCola('S');
				else{
					N = AtenderFrenteDeCola('N');
					cout << N->Info.NombreVertice << "  ";
				}
				N->Info.Estado = 3;
				A = N->Cab;
				while(A){
					if(A->Ady->Info.Estado == 1){
						InsertarEnColas(A->Ady);
						A->Ady->Info.Estado = 2;
					}
					A = A->Sig;
				}
			}
		}
		return 1;
	}
	return 0;
}
//-----------------------------------------------------------------------------
//ALGORITMO DE DIJKSTRA para el cálculo de trayectorias mínimas entre un
//vértice de origen y todos los demás a los cuales se pueda llegar.
//-----------------------------------------------------------------------------
void AlgoritmoDeDijkstra(){
	Cola *S;//Cola de prioridad ordenada por recorrido en anchura del grafo
			//desde el nodo fuente, hasta todos los que se pueda llegar
			//por medio de los adyacentes.
	VERTICE *U;
	ARISTA *A;

	if(RecorridoEnAnchura('S')){
		S = Q;
		while(Q){
			U = Q->V; //Se procede a atender el primer nodo de la cola
			Q = Q->Sig;

			A = U->Cab;
			while(A){ //Recorre aristas del vértice U, "relajando"
				if(A->Ady->Info.d > U->Info.d + A->Info.PesoArista){
					A->Ady->Info.d = U->Info.d + A->Info.PesoArista;
					A->Ady->Predecesor = U;
				}
				A = A->Sig;
			}
		}
		//listado del conjunto S a continuacion
		clrscr(); cout << "Vertice Predecesor Distancias m s cortas\n";
		while(S){
			cout << S->V->Info.NombreVertice << "         "
				 << S->V->Predecesor->Info.NombreVertice << " "
				 << setw(8) << S->V->Info.d << endl;
			Q=S;
			S = S->Sig;
			delete(Q);
		}
	}
}
//-----------------------------------------------------------------------------
//FIN ALGORITMO DE DIJKSTRA.
//-----------------------------------------------------------------------------

/************************************************************************** */
void main(){
	char op;

	//unlink(NombreArch);    //Habilite si quiere borrar NombreArch
	CargarLISTA_y_SubListas();

	do{
		clrscr();
		ListarGrafoComoTexto();
		cout<<"Vertices Borrar Encontrar Aristas Profundidad aNchura Dijkstra ESC";
		switch ( op = getch() ){
			case 'v': ;	case 'V': CapturarVertice();
														break;
			case 'b': ;	case 'B': EliminarVertice();
														break;
			case 'e': ;	case 'E': EncontrarVertice();
														break;
			case 'a': ;	case 'A': MenuSubListaDeAristas();
														break;
			case 'p': ;	case 'P': RecorridoEnProfundidad();
														break;
			case 'n': ;	case 'N': RecorridoEnAnchura('S');
														getch();
														break;
			case 'd': ;	case 'D': AlgoritmoDeDijkstra();
														getch();
														break;
		}
	} while (op != 27);
	GrabarGrafo();
}
