Advertisement
pmanriquez93

TAD Grafo

Jul 4th, 2014
552
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 6.79 KB | None | 0 0
  1. /* CABECERA */
  2.  
  3. #ifndef GRAFO_H
  4. #define GRAFO_H
  5.  
  6. typedef int TElemento;
  7.  
  8. typedef struct nodoArista{
  9.     TElemento elem;
  10.     int peso;
  11.     struct nodoArista* ptrSig;
  12. }TNodoArista;
  13.  
  14. typedef struct nodoVertice{
  15.     TElemento elem;    
  16.     TNodoArista *inicio;
  17.     struct nodoVertice* ptrSig;
  18. }TNodoVertice;
  19.  
  20. typedef struct{
  21.     TNodoVertice *inicio;    
  22. }TGrafo;
  23.  
  24. void crearGrafo(TGrafo*);
  25.  
  26. void insertarArista(TGrafo*,TElemento,TElemento,int);
  27. void insertarVertice(TGrafo*,TElemento);
  28.  
  29. int existeArista(TGrafo*,TElemento,TElemento);
  30. int existeVertice(TGrafo*,TElemento);
  31.  
  32. void eliminarArista(TGrafo*,TElemento,TElemento);
  33. void eliminarVertice(TGrafo*,TElemento);
  34.  
  35. void imprimirGrafo(TGrafo*);
  36.  
  37. int numVertices(TGrafo*);
  38.  
  39. #endif  /* GRAFO_H */
  40.  
  41.  
  42.  
  43.  
  44.  
  45. /* IMPLEMENTACION */
  46.  
  47. #include <stdio.h>
  48. #include <stdlib.h>
  49. #include "grafo.h"
  50.  
  51. void crearGrafo(TGrafo*grafo){
  52.     grafo->inicio = NULL;    
  53. }
  54.  
  55. void insertarVertice(TGrafo*grafo,TElemento v){
  56.     if (!existeVertice(grafo,v)){
  57.         TNodoVertice *ptrNuevoVertice;
  58.         ptrNuevoVertice = (TNodoVertice*)malloc(sizeof(TNodoVertice));
  59.         ptrNuevoVertice->elem = v;
  60.         ptrNuevoVertice->inicio = NULL;
  61.        
  62.         ptrNuevoVertice->ptrSig = grafo->inicio;
  63.         grafo->inicio = ptrNuevoVertice;
  64.     }      
  65. }
  66.  
  67. void insertarArista(TGrafo*grafo,TElemento v1,TElemento v2,int peso){
  68.     if (!existeArista(grafo,v1,v2)){
  69.         insertarVertice(grafo,v1);
  70.         insertarVertice(grafo,v2);
  71.  
  72.         TNodoVertice* ptrRecVertice;
  73.         ptrRecVertice = grafo->inicio;
  74.         while(ptrRecVertice && ptrRecVertice->elem != v1)        
  75.             ptrRecVertice = ptrRecVertice->ptrSig;
  76.        
  77.         TNodoArista* ptrNuevaArista;
  78.         ptrNuevaArista = (TNodoArista*)malloc(sizeof(TNodoArista));
  79.         ptrNuevaArista->elem = v2;
  80.         ptrNuevaArista->peso = peso;
  81.        
  82.         ptrNuevaArista->ptrSig = ptrRecVertice->inicio;
  83.         ptrRecVertice->inicio = ptrNuevaArista;
  84.     }
  85. }
  86.  
  87. int existeArista(TGrafo*grafo,TElemento v1,TElemento v2){
  88.     if (existeVertice(grafo,v1)==0)
  89.         return 0;
  90.     else{
  91.         if(existeVertice(grafo,v2)==0)
  92.             return 0;
  93.         else{
  94.             TNodoVertice *ptrRecVertice;
  95.             ptrRecVertice = grafo->inicio;
  96.             while(ptrRecVertice && ptrRecVertice->elem != v1)
  97.                 ptrRecVertice = ptrRecVertice->ptrSig;
  98.             TNodoArista* ptrRecArista;
  99.             ptrRecArista = ptrRecVertice->inicio;
  100.             while(ptrRecArista){
  101.                 if (ptrRecArista->elem == v2)
  102.                     return 1;
  103.                 ptrRecArista = ptrRecArista->ptrSig;
  104.             }
  105.             return 0;
  106.         }
  107.     }
  108. }
  109.  
  110. int existeVertice(TGrafo*grafo,TElemento v){
  111.     TNodoVertice *ptrRecVertice;
  112.     ptrRecVertice = grafo->inicio;
  113.    
  114.     while(ptrRecVertice && ptrRecVertice->elem != v)
  115.         ptrRecVertice = ptrRecVertice->ptrSig;
  116.    
  117.     if (ptrRecVertice == NULL)
  118.         return 0;
  119.     else
  120.         return 1;
  121. }
  122.  
  123. void eliminarArista(TGrafo*grafo,TElemento v1,TElemento v2){
  124.     TNodoVertice * ptrRecVertice;
  125.     if (existeArista(grafo,v1,v2)){        
  126.         ptrRecVertice = grafo->inicio;
  127.         while(ptrRecVertice && ptrRecVertice->elem != v1)
  128.             ptrRecVertice = ptrRecVertice->ptrSig;
  129.    
  130.         TNodoArista *ptrRecArista, *ptrAnt, *ptrEliminar;
  131.         ptrRecArista = ptrRecVertice->inicio;
  132.         ptrAnt = NULL;
  133.         while(ptrRecArista && ptrRecArista->elem != v2){
  134.             ptrAnt = ptrRecArista;        
  135.             ptrRecArista = ptrRecArista->ptrSig;
  136.         }
  137.         if (ptrAnt == NULL){
  138.             ptrEliminar = ptrRecVertice->inicio;
  139.             ptrRecVertice->inicio = ptrRecVertice->inicio->ptrSig;
  140.         }else{
  141.             ptrEliminar = ptrRecArista;
  142.             ptrAnt->ptrSig = ptrRecArista->ptrSig;
  143.         }
  144.         free(ptrEliminar);
  145.     }
  146. }
  147.  
  148. void eliminarVertice(TGrafo*grafo,TElemento v){
  149.     if (existeVertice(grafo,v)){
  150.         TNodoVertice *ptrRecVertice, *ptrAntVertice, *ptrEliminar;
  151.         ptrRecVertice = grafo->inicio;
  152.         ptrAntVertice = NULL;
  153.        
  154.         while(ptrRecVertice && ptrRecVertice->elem != v){
  155.             ptrAntVertice = ptrRecVertice;
  156.             ptrRecVertice = ptrRecVertice->ptrSig;
  157.         }
  158.        
  159.         TNodoArista *ptrRecArista,*ptrEliminarArista;
  160.         ptrRecArista = ptrRecVertice->inicio;
  161.         while(ptrRecArista){
  162.             ptrEliminarArista = ptrRecVertice->inicio;
  163.             ptrRecArista = ptrRecArista->ptrSig;
  164.             free(ptrEliminarArista);
  165.         }
  166.        
  167.         if (ptrAntVertice == NULL){
  168.             ptrEliminar = grafo->inicio;
  169.             grafo->inicio = grafo->inicio->ptrSig;
  170.         }
  171.         else{
  172.             ptrEliminar = ptrRecVertice;
  173.             ptrAntVertice->ptrSig = ptrRecVertice->ptrSig;
  174.         }
  175.         free(ptrEliminar);
  176.        
  177.         ptrRecVertice = grafo->inicio;
  178.         while(ptrRecVertice){
  179.             ptrRecArista = ptrRecVertice->inicio;
  180.             while(ptrRecArista){
  181.                 if (ptrRecArista->elem == v)
  182.                     eliminarArista(grafo,ptrRecVertice->elem,v);
  183.                 ptrRecArista = ptrRecArista->ptrSig;
  184.             }
  185.             ptrRecVertice = ptrRecVertice->ptrSig;
  186.         }
  187.     }
  188. }
  189.  
  190. void imprimirGrafo(TGrafo*grafo){
  191.     TNodoVertice *ptrRecVertice;
  192.     TNodoArista *ptrRecArista;
  193.     ptrRecVertice = grafo->inicio;
  194.     while(ptrRecVertice){
  195.         printf("V: %2d\n       A:",ptrRecVertice->elem);
  196.         ptrRecArista = ptrRecVertice->inicio;
  197.         while(ptrRecArista){
  198.             printf("% 2d w:%d",ptrRecArista->elem,ptrRecArista->peso);
  199.             ptrRecArista = ptrRecArista->ptrSig;
  200.         }
  201.         printf("  NULL\n");
  202.         ptrRecVertice = ptrRecVertice->ptrSig;
  203.     }
  204. }
  205.  
  206. int numVertices(TGrafo*grafo){
  207.     TNodoVertice *ptrRecVertice;
  208.     ptrRecVertice = grafo->inicio;
  209.     int cont = 0;
  210.    
  211.     while(ptrRecVertice){
  212.         cont++;        
  213.         ptrRecVertice = ptrRecVertice->ptrSig;
  214.     }
  215.     return cont;    
  216. }
  217.  
  218.  
  219.  
  220.  
  221.  
  222. /* MAIN */
  223.  
  224. #include <stdio.h>
  225. #include <stdlib.h>
  226. #include "grafo.h"
  227.  
  228. int main(int argc, char** argv) {
  229.    
  230.     TGrafo grafo;
  231.    
  232.     crearGrafo(&grafo);
  233.    
  234.     insertarVertice(&grafo,5);
  235.     insertarVertice(&grafo,4);
  236.     insertarVertice(&grafo,3);
  237.     insertarVertice(&grafo,2);
  238.     insertarVertice(&grafo,1);
  239.    
  240.     insertarArista(&grafo,5,1,2);
  241.     insertarArista(&grafo,4,1,1);
  242.     insertarArista(&grafo,4,2,1);
  243.     insertarArista(&grafo,4,3,1);
  244.     insertarArista(&grafo,4,5,1);
  245.    
  246.     insertarArista(&grafo,11,1,6);
  247.     insertarArista(&grafo,10,13,1);
  248.  
  249.     imprimirGrafo(&grafo);
  250.  
  251.     eliminarVertice(&grafo,4);
  252.     eliminarArista(&grafo,5,1);
  253.     imprimirGrafo(&grafo);
  254.    
  255.     return (EXIT_SUCCESS);
  256. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement