Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* CABECERA */
- #ifndef GRAFO_H
- #define GRAFO_H
- typedef int TElemento;
- typedef struct nodoArista{
- TElemento elem;
- int peso;
- struct nodoArista* ptrSig;
- }TNodoArista;
- typedef struct nodoVertice{
- TElemento elem;
- TNodoArista *inicio;
- struct nodoVertice* ptrSig;
- }TNodoVertice;
- typedef struct{
- TNodoVertice *inicio;
- }TGrafo;
- void crearGrafo(TGrafo*);
- void insertarArista(TGrafo*,TElemento,TElemento,int);
- void insertarVertice(TGrafo*,TElemento);
- int existeArista(TGrafo*,TElemento,TElemento);
- int existeVertice(TGrafo*,TElemento);
- void eliminarArista(TGrafo*,TElemento,TElemento);
- void eliminarVertice(TGrafo*,TElemento);
- void imprimirGrafo(TGrafo*);
- int numVertices(TGrafo*);
- #endif /* GRAFO_H */
- /* IMPLEMENTACION */
- #include <stdio.h>
- #include <stdlib.h>
- #include "grafo.h"
- void crearGrafo(TGrafo*grafo){
- grafo->inicio = NULL;
- }
- void insertarVertice(TGrafo*grafo,TElemento v){
- if (!existeVertice(grafo,v)){
- TNodoVertice *ptrNuevoVertice;
- ptrNuevoVertice = (TNodoVertice*)malloc(sizeof(TNodoVertice));
- ptrNuevoVertice->elem = v;
- ptrNuevoVertice->inicio = NULL;
- ptrNuevoVertice->ptrSig = grafo->inicio;
- grafo->inicio = ptrNuevoVertice;
- }
- }
- void insertarArista(TGrafo*grafo,TElemento v1,TElemento v2,int peso){
- if (!existeArista(grafo,v1,v2)){
- insertarVertice(grafo,v1);
- insertarVertice(grafo,v2);
- TNodoVertice* ptrRecVertice;
- ptrRecVertice = grafo->inicio;
- while(ptrRecVertice && ptrRecVertice->elem != v1)
- ptrRecVertice = ptrRecVertice->ptrSig;
- TNodoArista* ptrNuevaArista;
- ptrNuevaArista = (TNodoArista*)malloc(sizeof(TNodoArista));
- ptrNuevaArista->elem = v2;
- ptrNuevaArista->peso = peso;
- ptrNuevaArista->ptrSig = ptrRecVertice->inicio;
- ptrRecVertice->inicio = ptrNuevaArista;
- }
- }
- int existeArista(TGrafo*grafo,TElemento v1,TElemento v2){
- if (existeVertice(grafo,v1)==0)
- return 0;
- else{
- if(existeVertice(grafo,v2)==0)
- return 0;
- else{
- TNodoVertice *ptrRecVertice;
- ptrRecVertice = grafo->inicio;
- while(ptrRecVertice && ptrRecVertice->elem != v1)
- ptrRecVertice = ptrRecVertice->ptrSig;
- TNodoArista* ptrRecArista;
- ptrRecArista = ptrRecVertice->inicio;
- while(ptrRecArista){
- if (ptrRecArista->elem == v2)
- return 1;
- ptrRecArista = ptrRecArista->ptrSig;
- }
- return 0;
- }
- }
- }
- int existeVertice(TGrafo*grafo,TElemento v){
- TNodoVertice *ptrRecVertice;
- ptrRecVertice = grafo->inicio;
- while(ptrRecVertice && ptrRecVertice->elem != v)
- ptrRecVertice = ptrRecVertice->ptrSig;
- if (ptrRecVertice == NULL)
- return 0;
- else
- return 1;
- }
- void eliminarArista(TGrafo*grafo,TElemento v1,TElemento v2){
- TNodoVertice * ptrRecVertice;
- if (existeArista(grafo,v1,v2)){
- ptrRecVertice = grafo->inicio;
- while(ptrRecVertice && ptrRecVertice->elem != v1)
- ptrRecVertice = ptrRecVertice->ptrSig;
- TNodoArista *ptrRecArista, *ptrAnt, *ptrEliminar;
- ptrRecArista = ptrRecVertice->inicio;
- ptrAnt = NULL;
- while(ptrRecArista && ptrRecArista->elem != v2){
- ptrAnt = ptrRecArista;
- ptrRecArista = ptrRecArista->ptrSig;
- }
- if (ptrAnt == NULL){
- ptrEliminar = ptrRecVertice->inicio;
- ptrRecVertice->inicio = ptrRecVertice->inicio->ptrSig;
- }else{
- ptrEliminar = ptrRecArista;
- ptrAnt->ptrSig = ptrRecArista->ptrSig;
- }
- free(ptrEliminar);
- }
- }
- void eliminarVertice(TGrafo*grafo,TElemento v){
- if (existeVertice(grafo,v)){
- TNodoVertice *ptrRecVertice, *ptrAntVertice, *ptrEliminar;
- ptrRecVertice = grafo->inicio;
- ptrAntVertice = NULL;
- while(ptrRecVertice && ptrRecVertice->elem != v){
- ptrAntVertice = ptrRecVertice;
- ptrRecVertice = ptrRecVertice->ptrSig;
- }
- TNodoArista *ptrRecArista,*ptrEliminarArista;
- ptrRecArista = ptrRecVertice->inicio;
- while(ptrRecArista){
- ptrEliminarArista = ptrRecVertice->inicio;
- ptrRecArista = ptrRecArista->ptrSig;
- free(ptrEliminarArista);
- }
- if (ptrAntVertice == NULL){
- ptrEliminar = grafo->inicio;
- grafo->inicio = grafo->inicio->ptrSig;
- }
- else{
- ptrEliminar = ptrRecVertice;
- ptrAntVertice->ptrSig = ptrRecVertice->ptrSig;
- }
- free(ptrEliminar);
- ptrRecVertice = grafo->inicio;
- while(ptrRecVertice){
- ptrRecArista = ptrRecVertice->inicio;
- while(ptrRecArista){
- if (ptrRecArista->elem == v)
- eliminarArista(grafo,ptrRecVertice->elem,v);
- ptrRecArista = ptrRecArista->ptrSig;
- }
- ptrRecVertice = ptrRecVertice->ptrSig;
- }
- }
- }
- void imprimirGrafo(TGrafo*grafo){
- TNodoVertice *ptrRecVertice;
- TNodoArista *ptrRecArista;
- ptrRecVertice = grafo->inicio;
- while(ptrRecVertice){
- printf("V: %2d\n A:",ptrRecVertice->elem);
- ptrRecArista = ptrRecVertice->inicio;
- while(ptrRecArista){
- printf("% 2d w:%d",ptrRecArista->elem,ptrRecArista->peso);
- ptrRecArista = ptrRecArista->ptrSig;
- }
- printf(" NULL\n");
- ptrRecVertice = ptrRecVertice->ptrSig;
- }
- }
- int numVertices(TGrafo*grafo){
- TNodoVertice *ptrRecVertice;
- ptrRecVertice = grafo->inicio;
- int cont = 0;
- while(ptrRecVertice){
- cont++;
- ptrRecVertice = ptrRecVertice->ptrSig;
- }
- return cont;
- }
- /* MAIN */
- #include <stdio.h>
- #include <stdlib.h>
- #include "grafo.h"
- int main(int argc, char** argv) {
- TGrafo grafo;
- crearGrafo(&grafo);
- insertarVertice(&grafo,5);
- insertarVertice(&grafo,4);
- insertarVertice(&grafo,3);
- insertarVertice(&grafo,2);
- insertarVertice(&grafo,1);
- insertarArista(&grafo,5,1,2);
- insertarArista(&grafo,4,1,1);
- insertarArista(&grafo,4,2,1);
- insertarArista(&grafo,4,3,1);
- insertarArista(&grafo,4,5,1);
- insertarArista(&grafo,11,1,6);
- insertarArista(&grafo,10,13,1);
- imprimirGrafo(&grafo);
- eliminarVertice(&grafo,4);
- eliminarArista(&grafo,5,1);
- imprimirGrafo(&grafo);
- return (EXIT_SUCCESS);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement