implementacion grafos dirigidos lista adyacencias

5/9/2018 Implementacion Grafos Dirigidos Lista Adyacencias - slidepdf.com

http://slidepdf.com/reader/full/implementacion-grafos-dirigidos-lista-adyacencias 1/14

IMPLEMENTACIÓN DEL TAD GRAFO COMO LISTAS SIMPLEMENTEENLAZADAS

Para implementar el TAD Grafo como listas simplemente enlazadas se

entiende que un grafo es un apuntador a una lista de vértices, cada vérticetiene un apuntador a un sus arcos y cada arco tiene un apuntador alsiguiente arco y un apuntador al vértice destino.Un ejemplo sería:

En este ejemplo, vemos que el grafo de arriba tiene 4 vértices:v1 con info T, v2 con info Z, v3 con info M y v4 con info F.

Y 3 arcos, uno de v1 a v3 con costo 60, uno de v1 a v4 con costo 20 y uno dev2 a v4 con costo 10.En la representación de listas enlazadas se observa que el grafo g es unapuntador a una estructura que contiene el entero 4 (orden del grafo) y unapuntador.El apuntador va hacia un vértice, el vértice tiene un número (4 el índice), unaletra (F el info del vértice) y dos apuntadores. El primer apuntador va hacia



abajo hacia otro vértice, es decir los vértices son una lista. El otro apuntadorva hacia el lado hacia un arco.El nodo tiene un número (10, el costo del arco), y dos apuntadores, unapuntador va hacia otra estructura similar (el siguiente arco que sale del

vértice) y un apuntador que va hacia un vértice (hacia Z) que en este casorepresenta el vértice destino del arco con costo 10.Y así se repite para todos los vértices y arcos.

Para implementar el grafo se necesitan tres (3) estructuras de datosfundamentales:

• El nodo que es arco• El nodo que es vértice• El nodo que es grafo.

En el caso del TipoG (tipo del info del vértice), para el proyecto también sedebe manejar una estructura de datos que contiene el nombre de la ciudad

(char *) y el número de soldados que hay en la ciudad (int).El arco debe tener el costo, un apuntador a otro arco y un apuntador a unvértice.El vértice debe tener el índice (número del vértice), el info de TipoG, unapuntador al siguiente vértice, un apuntador a su primer arco y la marca delvértice.El grafo tiene un entero (el orden del grafo) y un apuntador a un vértice.Las estructuras de datos propuestas podrían

typedef struct //el info de cada vertice tendra nombre y numero de soldados{ char *nombre;

int soldados;

} TipoG;

typedef struct NodoArco //los arcos tienen costo, un apuntador al siguiente{ int costo; //arco y un apuntador al nodo destino

struct NodoArco *sig;struct NodoVertice *dest;

}*pNodoArco;

typedef struct NodoVertice //los vertices tienen un indice, la info, una marca,{ int ind; // un apuntador al siguiente vertice y un apuntador a sus arcos.

TipoG info;int marca;struct NodoVertice *sig;

struct NodoArco *arcos;}*pNodoVertice;

typedef struct //un Grafo tiene el orden y el apuntador al primer vertice.{ int orden;

struct NodoVertice *grafo;}TGrafo, *Grafo;



En esta implementación las primitivas del TAD, macroalgoritmicamenteharían:inicGrafo(): Crearía una variable de tipo Grafo, le reservaría elespacio en memoria, le asignaría 0 al orden y NULL al grafo y retornaría la

variable.La implementación sería:Grafo inicGrafo()/*Crea y retorna un grafo vacio

{Pre: TRUE}{Post: Inic_Grafo=(0,0)} */

{ Grafo g=(Grafo)malloc(sizeof(TGrafo));g->orden=0;g->grafo=NULL;return g;

}

insVertice(g,elem): Crea una variable de tipo vértice, le reserva elespacio en memoria, le asignaría el orden del grafo más 1 como índice, leasignaría elem como info, le asignaría al apuntador a los arcos NULL y alapuntador al siguiente vértice NULL. Luego, analiza si el orden del grafo escero, es decir si no tiene vértices y entonces inserta el nuevo vértice comoprimer vértice del grafo, si el grafo ya tiene vértices, entonces recorre losvértices hasta llegar al último y en esa posición inserta el nuevo vértice.La implementación sería:void insVertice(Grafo g, TipoG elem)/*Agrega un vertice al grafo con la informacion elem asociada* Dado un grafo G y un elemento elem, retorna un grafo

con el nuevo vertice en el conjunto V y le asocia, como infoel valor de elem. *{Pre: G=(V,A), V=Vinic, A=Ainic, vt PERTENECE A Vinic}{Post: Adic_Vertice=(V,A), V= Vinic U {vt}, A= Ainic,informacion(G,vt)=elem} */

{pNodoVertice v=(pNodoVertice)malloc(sizeof(struct NodoVertice));g->orden++; //aumento en 1 el ordenv->ind=g->orden; //creo como ind del vertice el ordenv->info=elem; //se debe crear una función para crear elv->sig=NULL; // info de un vértice.v->arcos=NULL;v->marca=0; //define el vértice como no marcadoif(g->orden==1) //si no hay vertices en el grafo, lo

g->grafo=v; // inserto de primeroelse{ pNodoVertice p=g->grafo; //recorro los vérticeswhile(p->sig!=NULL) // hasta el ultimo y lo inserto como

p=p->sig; // el ultimop->sig=v;

}}



insArco(g,w,z,c): Crea una variable de tipo arco, le reserva elespacio en memoria, le asignaría c como costo, revisa que el grafo tengavértices, los recorre buscando el vértice de partida del arco (w). cuando loencuentra, recorre sus arcos, revisando que no exista uno con vértice de

destino z. Si lo encuentra, simplemente reemplaza el costo existente del arcopor el nuevo costo c, sino, inserta en la última posición de la lista de arcos, elarco ya creado y busca entre los vértices el vértice z, para asignárselo comovértice de destino al arco.La implementación sería:void insArco(Grafo g, int w, int z, int c)/*Agrega al grafo el arco w->z con costo c* Dado un grafo G y un par de vertices v1 y v2 del grafo, retorna un

grafo con un nuevo arco entre dichos vertices y con un costoasociado c *

{Pre: G=(V, A), V=Vinic, A=Ainic, v1,v2 PERTENECEN A V,(v1,v2,z) NO PERTENECE A A para ningun z}{Post: Adic_arco=(V,A), V=Vinic, A=Ainic È {(v1,v2,z)}} */

{ pNodoArco a=(pNodoArco)malloc(sizeof(struct NodoArco));a->costo=c;a->sig=NULL;a->dest=NULL; //crea e inicializa el nuevo arco con costo cif(g->orden>0) //si el grafo tiene vertices{ pNodoArco p;

pNodoVertice q;pNodoVertice r;q=g->grafo;while(q->sig!=NULL&&q->ind!=w)

q=q->sig; //recorre los vertices hasta que//encuentre w

if(q->ind==w) //si encontro el vertice w

{ if(q->arcos==NULL) //si no hay arcos desde el{ r=g->grafo; // vertice wwhile(r->sig!=NULL&&r->ind!=z) //recorre los

r=r->sig; //vertices buscando el// vertice z

if(r->ind==z) //encontro el vertice z{ a->dest=r; //enlaza el arco con el

//vertice destino zq->arcos=a; //inserta el arco a como

//primer arco de w}else //sino, no existe z y libera el arco

free(a);}

else //si el vertice w ya tiene arcos{ p=q->arcos;

while(p->sig!=NULL&&p->dest->ind!=z)//hago el recorrido de todos los vertices con los que w tiene//arcos

p=p->sig; //y reviso si tiene alguno//con z

if(p->dest->ind==z) //si encontro un



//arco entre w y z{ p->costo=c; //cambia el costo

//anterior por el nuevo costo cfree(a); //libera a

}

else if(p->sig==NULL)//no encontro ningun arco{ r=g->grafo; // entre w y zwhile(r->sig!=NULL&&r->ind!=z)

//recorre los vertices buscando el vertice zr=r->sig;

if(r->ind==z) //encontro el vertice z{ a->dest=r; //enlaza el arco con el

//vertice destino zp->sig=a; //inserta el arco a//como ultimo arco de w

}else //si no existe z y libera el arco

free(a);}

else}

}else //si no encontro el vertice w

free(a); //libera el arco a}else //si el grafo no tiene vertices (orden=0),

//no puede crear ningun arcofree(a); //libera el arco a

}

ElimVertice(g,w): Para eliminar un vértice se deben eliminar los arcosque parten o llega a el y luego eliminar el vértice. Si el grafo no tiene vérticesentonces no se elimina nada, en caso contrario, se hace un recorrido en losvértices del grafo (g->grafo) buscando el vértice con índice igual a w. cuandolo encuentra, debe recorrer la lista de arcos (vértice->arcos), eliminando losnodos que existan en esa lista, hasta que la lista quede vacía, en este casose han eliminado los arcos que salen del vértice. Para eliminar los arcos quellegan al vértice, es necesario recorrer todos los vértices, recorriendo a suvez sus arcos buscando si el destino de cada arco es el vértice w (p->dest->ind==w), en caso afirmativo, se debe eliminar dicho arco.Al final, se elimina el vértice w.

ElimArco(g,w,z): Para eliminar un arco, se averigua si el grafo tienevértices, en ese caso, se busca el vértice inicial (w) del arco en un recorridoque se debe iniciar en g->grafo. Cuando lo encuentra, averigua si el vértice wtiene arcos (p->arcos!=NULL), y en ese caso, inicia un recorrido en los arcosbuscando un arco que tenga como vértice de destino a z (q->dest->ind==z).cuando lo encuentra debe eliminar dicho arco.



CostoArco(g,w,z): Se verifica que el grafo tenga vértices, y se inicia unrecorrido en los vértices (g->grafo) buscando el vértice con índice w (p->ind==w). Cuando se encuentra, se inicia un recorrido en los arcos de w (p->arcos) buscando un arco cuyo vértice de destino sea z (q->dest->ind==z).

Cuando lo encuentra, retorna el costo (q->costo) que debe ser un enteronegativo, si no encuentra el vértice de destino z, entonces significa que elarco no existe y debe devolver el valor NULO. (NULO en la implementaciónserá -1).La implementación sería:int costoArco(Grafo g, int w, int z)/* Retorna el costo del arco entre w y z, si no existe retorna NULO

{Pre: G=(V,A), V={v1,..,vi,..,vn}, n>0, Ei,j 1<=i,j<=n /vi=w^vj=z}

{Post: (E(w,z,c)PERTENECE A, costoArco=c) v(-E(w,z,c) PERTENECE A, costoArco=NULO)}

*/{ pNodoVertice p;

pNodoArco q;

if(g->orden>0){ p=g->grafo;

while(p->sig!=NULL&&p->ind!=w) //se recorren losp=p->sig; // vertices buscando el vertice w

if(p->ind==w) //si encontro el vertice w{ if(p->arcos!=NULL) //si dicho vertice tiene

{ q=p->arcos; // arcoswhile(q->sig!=NULL&&q->dest->ind!=z)

//se recorren los arcos buscando el que tenga vertice de destino zq=q->sig;

if(q->dest->ind==z)

return q->costo;else //si no encuentra el z, no, existereturn NULO; // arco y retorna NULO

} //si el vertice w no tiene arcos retorna NULOelse

return NULO;} //si no encuentra el vertice w retorna NULOelse

return NULO;} //si no hay vertices, return NULOelse

return NULO;}

Lista sucesores(g,w): Primero se revisa si el grafo tiene vértices y enese caso inicia un recorrido en los vértices (g->grafo) buscando el vértice w(p->ind==w) cuando lo encuentra, recorremos la lista de arcos (q->arcos) ycon cada arco, anexamos el índice del vértice de destino (r->dest->ind) a lalista de respuesta. Finalmente se retorna la lista.



TipoG infoVertice(g,w): Primero se revisa si el grafo tiene vértices yen ese caso, inicia un recorrido en los vértices (g->grafo) buscando el vérticew (p->ind==w). Cuando lo encuentra, retorna el info del vértice (q->info). Elresultado es de TipoG, para el caso del proyecto TipoG es un struct, así que

se debe tener cuidado si se retorna el nombre o los soldados.La implementación sería:TipoG infoVertice(Grafo g, int w)/* Retorna la informacion asociada con el vertice w en el grafo g

Para obtener el nombre de la ciudad char *, o el numero desoldados int

{Pre: G=(V,A), vert PERTENECE A V}{Post: Info_Grafo=info(w)}

*/{ pNodoVertice p;


while(p->sig!=NULL&&p->ind!=w) //se recorren los//vertices buscando el vertice origen w

p=p->sig;if(p->ind==w) //si encontro el vertice w

return p->info;}

}

Int ordenGrafo(g): simplemente retorna g->orden.La implementación sería:int ordenGrafo(Grafo g)/* Retorna el orden del grafo

{Pre: TRUE}{Post: g=(V,A) ^ ordenGrafo = |V|}

*/{ return g->orden;}

void marcarVertice(g,w): Revisa si El grafo tiene vértice (g->orden>0)en ese caso, Recorre desde g->grafo hasta que encuentre el vértice w (p->ind==w), entonces se activa la marca del vértice (p->marca=1).La implementación sería:void marcarVertice(Grafo g, int w)/* Marca el vértice w como ya visitado en el grafo g

{Pre: G=(V,A), vert PERTENECE A V}{Post: w PERTENECE a los V’}

*/{ pNodoVertice p;pNodoArco q,r;if(g->orden>0){ p=g->grafo;





p->marca=1;}

}

void desmarcarVertice(g,w): Revisa si el grafo tiene vértices (g-

>orden>0), en ese caso, recorre desde g->grafo hasta que encuentre elvértice w (p->ind==w), entonces se desactiva la marca del vértice (p->marca=0).La implementación sería:void desmarcarVertice(Grafo g, int w)/* Desmarca el vértice w en el grafo g

{Pre: G=(V,A), vert PUEDE PERTENECER A V’}{Post: w PERTENECE a los V y no a los V’}

*/{ pNodoVertice p;


while(p->sig!=NULL&&p->ind!=w) //se recorren los//vertices buscando el vertice origen wp=p->sig;

if(p->ind==w) //si encontro el vertice wp->marca=0;

}}

boolean marcadoVertice(g,w): Indica si el vértice está marcado,primero se revisa si el grafo tiene vértices, en ese caso, se recorren losvértices desde g->grafo hasta que encuentre el vértice w (p->ind==w), si elvértice w tiene la marca en 1, retorna Verdadero, sino retorna Falso.

La implementación sería:boolean marcadoVertice(Grafo g, int w)/* Indica si el vértice w está marcado o noen el grafo g

{Pre: G=(V,A)}{Post: w PERTENECE a los V’ ^marcadoVertice=TRUE o

marcadoVertice=FALSE}*/{ pNodoVertice p;




return p->marca;}

Return FALSE;}



void desmarcarGrafo(g): Si el grafo tiene vértices (g->orden>0), serecorren los vértices desde g->grafo, con cada vértice, se cambia la marca a0 (p->marca=0).La implementación sería:

void desmarcarGrafo(Grafo g)/* Desmarca todos los vértices del grafo{Pre: G=(V,A)}{Post: V’=0 }

*/{ pNodoVertice p;


while(p!=NULL) //se recorren los vertices{ p->marca=0;

p=p->sig;}

}}



Un ejemplo de un programa con grafos implementado se puede ver en lasimágenes a continuación

Primero se crea el grafo (se reserva el espacio, con inicGrafo).

Luego se procede a crear los vértices que se requieran, por cada vértice sepregunta el info, es decir, el nombre de la ciudad y el número de soldadosque hay en ella.



Se muestran las ciudades (vértices) creadas.



Luego se procede a crear los arcos, es decir, las rutas de trenes entrediversas ciudades.

Se muestran las rutas de trenes (arcos) creados.



Luego se puede proceder a hacer otras operaciones, como por ejemplo verlos sucesores de un vértice.



O eliminar arcos

O eliminar vértices

implementacion grafos dirigidos lista adyacencias

Documents