Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Name: Representacion enlazada de un grafo
- Author: Joel Fernandez
- Date: 01/12/12 23:43
- Web: http://codebotic.blogspot.com
- Description: programa que muestra un grafo en su forma enlazada
- */
- #include<iostream.h>
- #include<conio.h>
- struct nodo{
- char nombre;//nombre del vertice o nodo
- struct nodo *sgte;
- struct arista *ady;//puntero hacia la primera arista del nodo
- };
- struct arista{
- struct nodo *destino;//puntero al nodo de llegada
- struct arista *sgte;
- };
- typedef struct nodo *Tnodo;// Tipo Nodo
- typedef struct arista *Tarista; //Tipo Arista
- Tnodo p;//puntero cabeza
- void menu();
- void insertar_nodo();
- void agrega_arista(Tnodo &, Tnodo &, Tarista &);
- void insertar_arista();
- void vaciar_aristas(Tnodo &);
- void eliminar_nodo();
- void eliminar_arista();
- void mostrar_grafo();
- void mostrar_aristas();
- /* Funcion Principal
- ---------------------------------------------------------------------*/
- int main(void)
- { p=NULL;
- int op; // opcion del menu
- system("color 0b");
- do
- {
- menu();
- cin>>op;
- switch(op)
- {
- case 1:
- insertar_nodo();
- break;
- case 2: insertar_arista();
- break;
- case 3: eliminar_nodo();
- break;
- case 4: eliminar_arista();
- break;
- case 5: mostrar_grafo();
- break;
- case 6: mostrar_aristas();
- break;
- default: cout<<"OPCION NO VALIDA...!!!";
- break;
- }
- cout<<endl<<endl;
- system("pause"); system("cls");
- }while(op!=7);
- getch();
- return 0;
- }
- /* Menu
- ---------------------------------------------------------------------*/
- void menu()
- {
- cout<<"\n\tREPRESENTACION DE GRAFOS DIRIGIDOS\n\n";
- cout<<" 1. INSERTAR UN NODO "<<endl;
- cout<<" 2. INSERTAR UNA ARISTA "<<endl;
- cout<<" 3. ELIMINAR UN NODO "<<endl;
- cout<<" 4. ELIMINAR UNA ARISTA "<<endl;
- cout<<" 5. MOSTRAR GRAFO "<<endl;
- cout<<" 6. MOSTRAR ARISTAS DE UN NODO "<<endl;
- cout<<" 7. SALIR "<<endl;
- cout<<"\n INGRESE OPCION: ";
- }
- /* INSERTAR NODO AL GRAFO
- ---------------------------------------------------------------------*/
- void insertar_nodo()
- {
- Tnodo t,nuevo=new struct nodo;
- cout<<"INGRESE VARIABLE:";
- cin>>nuevo->nombre;
- nuevo->sgte = NULL;
- nuevo->ady=NULL;
- if(p==NULL)
- {
- p = nuevo;
- cout<<"PRIMER NODO...!!!";
- }
- else
- {
- t = p;
- while(t->sgte!=NULL)
- {
- t = t->sgte;
- }
- t->sgte = nuevo;
- cout<<"NODO INGRESADO...!!!";
- }
- }
- /* AGREGAR ARISTA
- funcion que utilizada para agregar la arista a dos nodos
- ---------------------------------------------------------------------*/
- void agrega_arista(Tnodo &aux, Tnodo &aux2, Tarista &nuevo)
- {
- Tarista q;
- if(aux->ady==NULL)
- { aux->ady=nuevo;
- nuevo->destino=aux2;
- cout<<"PRIMERA ARISTA....!";
- }
- else
- { q=aux->ady;
- while(q->sgte!=NULL)
- q=q->sgte;
- nuevo->destino=aux2;
- q->sgte=nuevo;
- cout<<"ARISTA AGREGADA...!!!!";
- }
- }
- /* INSERTAR ARISTA
- funcion que busca las posiciones de memoria de los nodos
- y hace llamado a agregar_arista para insertar la arista
- ---------------------------------------------------------------------*/
- void insertar_arista()
- { char ini, fin;
- Tarista nuevo=new struct arista;
- Tnodo aux, aux2;
- if(p==NULL)
- {
- cout<<"GRAFO VACIO...!!!!";
- return;
- }
- nuevo->sgte=NULL;
- cout<<"INGRESE NODO DE INICIO:";
- cin>>ini;
- cout<<"INGRESE NODO FINAL:";
- cin>>fin;
- aux=p;
- aux2=p;
- while(aux2!=NULL)
- {
- if(aux2->nombre==fin)
- {
- break;
- }
- aux2=aux2->sgte;
- }
- while(aux!=NULL)
- {
- if(aux->nombre==ini)
- {
- agrega_arista(aux,aux2, nuevo);
- return;
- }
- aux = aux->sgte;
- }
- }
- /* FUNCION PARA BORRAR TODAS LAS ARISTAS DE UN NODO
- esta funcion es utilizada al borrar un nodo pues si tiene aristas
- es nesesario borrarlas tambien y dejar libre la memoria
- ---------------------------------------------------------------------*/
- void vaciar_aristas(Tnodo &aux)
- {
- Tarista q,r;
- q=aux->ady;
- while(q->sgte!=NULL)
- {
- r=q;
- q=q->sgte;
- delete(r);
- }
- }
- /* ELIMINAR NODO
- funcion utilizada para eliminar un nodo del grafo
- pero para eso tambien tiene que eliminar sus aristas por lo cual
- llama a la funcion vaciar_aristas para borrarlas
- ---------------------------------------------------------------------*/
- void eliminar_nodo()
- { char var;
- Tnodo aux,ant;
- aux=p;
- cout<<"ELIMINAR UN NODO\n";
- if(p==NULL)
- {
- cout<<"GRAFO VACIO...!!!!";
- return;
- }
- cout<<"INGRESE NOMBRE DE VARIABLE:";
- cin>>var;
- while(aux!=NULL)
- {
- if(aux->nombre==var)
- {
- if(aux->ady!=NULL)
- vaciar_aristas(aux);
- if(aux==p)
- {
- p=p->sgte;
- delete(aux);
- cout<<"NODO ELIMINADO...!!!!";
- return;
- }
- else
- {
- ant->sgte = aux->sgte;
- delete(aux);
- cout<<"NODO ELIMINADO...!!!!";
- return;
- }
- }
- else
- {
- ant=aux;
- aux=aux->sgte;
- }
- }
- }
- /* ELIMINAR ARISTA
- funcion utilizada para eliminar una arista
- ---------------------------------------------------------------------*/
- void eliminar_arista()
- {
- char ini, fin;
- Tnodo aux, aux2;
- Tarista q,r;
- cout<<"\n ELIMINAR ARISTA\n";
- cout<<"INGRESE NODO DE INICIO:";
- cin>>ini;
- cout<<"INGRESE NODO FINAL:";
- cin>>fin;
- aux=p;
- aux2=p;
- while(aux2!=NULL)
- {
- if(aux2->nombre==fin)
- {
- break;
- }
- else
- aux2=aux2->sgte;
- }
- while(aux!=NULL)
- {
- if(aux->nombre==ini)
- {
- q=aux->ady;
- while(q!=NULL)
- {
- if(q->destino==aux2)
- {
- if(q==aux->ady)
- aux->ady=aux->ady->sgte;
- else
- r->sgte=q->sgte;
- delete(q);
- cout<<"ARISTA "<<aux->nombre<<"----->"<<aux2->nombre<<" ELIMINADA.....!!!!";
- return;
- }
- }
- r=q;
- q=q->sgte;
- }
- aux = aux->sgte;
- }
- }
- /* MOSTRAR GRAFO
- funcion que imprime un grafo en su forma enlazada
- ---------------------------------------------------------------------*/
- void mostrar_grafo()
- { Tnodo ptr;
- Tarista ar;
- ptr=p;
- cout<<"NODO|LISTA DE ADYACENCIA\n";
- while(ptr!=NULL)
- { cout<<" "<<ptr->nombre<<"|";
- if(ptr->ady!=NULL)
- {
- ar=ptr->ady;
- while(ar!=NULL)
- { cout<<" "<<ar->destino->nombre;
- ar=ar->sgte;
- }
- }
- ptr=ptr->sgte;
- cout<<endl;
- }
- }
- /* MOSTRAR ARISTAS
- funcion que muestra todas las aristas de un nodo seleccionado
- ---------------------------------------------------------------------*/
- void mostrar_aristas()
- {
- Tnodo aux;
- Tarista ar;
- char var;
- cout<<"MOSTRAR ARISTAS DE NODO\n";
- cout<<"INGRESE NODO:";
- cin>>var;
- aux=p;
- while(aux!=NULL)
- {
- if(aux->nombre==var)
- {
- if(aux->ady==NULL)
- { cout<<"EL NODO NO TIENE ARISTAS...!!!!";
- return;
- }
- else
- {
- cout<<"NODO|LISTA DE ADYACENCIA\n";
- cout<<" "<<aux->nombre<<"|";
- ar=aux->ady;
- while(ar!=NULL)
- {
- cout<<ar->destino->nombre<<" ";
- ar=ar->sgte;
- }
- cout<<endl;
- return;
- }
- }
- else
- aux=aux->sgte;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement