| Implentaciones de los métodos de Grafo |
| Autor [masterhk] |
Calificacion |
 |
|
|
Implentaciones de los métodos de Grafo, y otras informaciones de interés a cerca de su implementación Grafos.
:) masterhk |
GRAFO
Estructuras Internas.
Esta representación tiene tres estructuras diferenciadas:
· Estructura correspondiente a un vértice.
o nodo: Código interno que permite numerar los nodos de 1 a n.
o etiq: Puntero a caracter en el que se encuentra la información que posee ese vértice, es decir su etiqueta.
o ady: Es un puntero a una lista que contiene las aristas que tienen como origen ese vértice.
o inc: Es un puntero a una lista que contiene las aristas que tienen como destino ese vértice (solo para grafos dirigidos).
o sig: Es un puntero que apunta al vértice que ocupa la posición siguiente dentro de la lista de vértices.
· Estructura básica del grafo.
En realidad se usa la misma estructura que para los nodos pero poniendo los campos etiq, ady y sig a NULL. Los dos campos restantes contienen:
o nodo: Contiene el número de nodos del grafo.
o sig: Es un puntero que apunta al vértice que ocupa la primera posición dentro de la lista de vértices.
Estructura correspondiente a una arista (grafo dirigido).
o origen: Es un puntero al vértice que es el origen de esa arista.
o destino: Es un puntero al vértice que es el destino de esa arista.(Nosotros hemos sustituido el puntero por la etiqueta del nodo destino para mayor claridad del dibujo).
o valor: Este campo contiene el peso de la arista que será un numero entero.
o sig: Puntero que apunta a la siguiente arista dentro de la lista de aristas adyacentes o incidentes.
Estructuras Internas del TDA Grafo.
/* Implementación basada en una lista de nodos de los que cuelga */
/* la lista de arcos de salida. */
#include
#include
#include
#define TE 5
#define Nulo NULL
typedef char *tetq;
typedef float tvalor;
typedef struct arco {
struct nodo *origen;
struct nodo *destino;
tvalor valor;
struct arco *sig;
} *tarco;
typedef struct nodo {
int nodo;
tetq etiq;
tarco ady;
tarco inc;
struct nodo *sig;
} *tnodo;
typedef tnodo tgrafo;
LISTA DE PRIMITIVAS.
Lista de primitivas para los grafos dirigidos:
· Crear: Función que se encarga de crear un grafo vacio.
· Etiqueta: Función que devuelve la etiqueta asociada a un nodo en un grafo.
· Label: Función que devuelve la Label de un nodo en el grafo.
· LocalizaLabel: Esta función recibe el entero l (el label asociado a un nodo que se supone pertenece al grafo y nos devuelve el nodo asociado con esa label.
· ExisteArco: Función que devuelve 1 si existe un arco entre el nodo o y el nodo d en el grafo g, si no existe dicho arco devuelve 0.
· PrimerArco: Devuelve el primer arco que sale del nodo n en el grafo g, si no existe dicho primer arco devuelve Nulo.
· SiguienteArco: Función que devuelve el arco siguiente al arco a en el nodo n si no existe dicho arco devuelve Nulo.
· PrimerArcoInv: Devuelve el primer arco que entra en el nodo n en el grafo g. Si no existe dicho arco devuelve Nulo.
· SiguienteArcoInv: Devuelve el siguiente arco tras a que entra en el nodo n, si no existe dicho arco devuelve Nulo.
· PrimerNodo: Devuelve el primer nodo del grafo G, si no existe devuelve nulo.
· SiguienteNodo: Devuelve el nodo siguiente en orden al nodo n en el grafo g. Si no existe devuelve nulo.
· NodoOrigen: Devuelve el nodo origen del arco a.
· NodoDestino: Devuelve el nodo destino del arco a.
· presentarGrafo: Escribe el grafo g en pantalla.
· NumeroNodos: Devuelve el numero de nodos de un grafo g.
· grafoVacio: Devuelve Nulo si el grafo esta vacio.
· EtiqArco: Función que devuelve la etiqueta asociada a un arco, es decir el peso del arco.
· InsertarNodo: Función que inserta un nodo nuevo en un grafo.
· InsertarArco: Función que se encarga de insertar un arco entre el nodo org y el dest en el grafo g, asociado al arco le podemos dar un valor.
· BorrarArco: Función que borra el arco existente entre los nodos org y dest.
· DesconectarNodo: Función que devuelve el grafo que se obtiene al eliminar un nodo de un grafo G. Todos los arcos que entran o salen del nodo a eliminar también desaparecen.
· Destruir: Función que destruye el grafo g liberando la memoria que ocupa.
· CopiarGrafo: Función que hace una copia del grafo g.
IMPLEMENTACIÓN DE LAS PRIMITIVAS.
tgrafo Crear(void)
{
tnodo aux;
aux = (tnodo)malloc(sizeof(struct nodo));
if (aux == NULL) {
error(\"Error en Crear.\");
} else {
aux->nodo = 0;
aux->etiq = NULL;
aux->ady = NULL;
aux->inc = NULL;
aux->sig = NULL;
return aux;
}
}
tetiq Etiqueta(tnodo n, tgrafo g)
{
return(n->etiq);
}
int Label(tnodo n, tgrafo g)
{
return(n->nodo);
}
tnodo LocalizaLabel(int l, tgrafo g)
{
tnodo n;
int enc=0;
for (n=g->sig; n!=NULL && !enc; ) {
if (n->nodo == l)
enc = 1;
else
n = n->sig;
}
return n;
}
int ExisteArco(tnodo o, tnodo d, tgrafo g)
{
tarco a;
a=o->ady;
while (a!=NULL) {
if ((a->origen==o) && (a->destino==d))
return 1;
else
a = a->sig;
}
return 0;
}
tarco PrimerArco(tnodo n, tgrafo g)
{
return(n->ady);
}
tarco SiguienteArco(tnodo n, tarco a, tgrafo g)
{
return(a->sig);
}
tarco PrimerArcoInv(tnodo n, tgrafo g)
{
return(n->inc);
}
tarco SiguienteArcoInv(tnodo n, tarco a, tgrafo g)
{
return(a->sig);
}
tnodo PrimerNodo(tgrafo g)
{
return(g->sig);
}
tnodo SiguienteNodo(tnodo n, tgrafo g)
{
return(n->sig);
}
tnodo NodoOrigen(tarco a, tgrafo g)
{
return(a->origen);
}
tnodo NodoDestino(tarco a, tgrafo g)
{
return(a->destino);
}
void PresentarGrafo(tgrafo g)
{
tnodo n;
tarco a;
n=PrimerNodo(g);
while (n!=Nulo) {
a=PrimerArco(n,g);
while (a!=Nulo) {
printf(\"%s -> %s \",a->origen->etiq,a->destino->etiq);
printf(\" (%f)\\n\",a->valor);
a=SiguienteArco(n,a,g);
}
n=SiguienteNodo(n,g);
}
}
int NumeroNodos(tgrafo g)
{
return(g->nodo);
}
int GrafoVacio(tgrafo g)
{
return(g->sig == NULL);
}
float EtiqArco(tnodo o, tnodo d, tgrafo g)
{
tarco a;
a=o->ady;
while (a!=NULL) {
if ((a->origen == o) && (a->destino == d))
return (a->valor);
else
a = a->sig;
}
return 0;
}
void InsertarNodo(tetq dato, tgrafo g)
{
tnodo aux,p;
aux = (tnodo)malloc(sizeof(struct nodo));
if (aux == NULL)
error(\"Error Memoria Insuficiente.\");
else {
p=g;
while(p->sig != NULL)
p = p->sig;
aux->etiq = (char *)malloc(sizeof (char)*TE);"+
if (aux->etiq == NULL)
error(\"Error Memoria Insuficiente.\");
aux->nodo = p->nodo+1;
strcpy(aux->etiq,dato);+
aux->ady = NULL;
aux->inc = NULL;
aux->sig = NULL;
p->sig = aux;
g->nodo++;
}
}
void InsertarArco (tnodo org,tnodo dest,tvalor valor,tgrafo g)
{
tarco aux;
tarco aux_inv;
aux = (tarco)malloc(sizeof(struct arco));
aux_inv= (tarco)malloc(sizeof(struct arco));
if ((aux==NULL) || (aux_inv==NULL))
error("Memoria Insuficiente.");
else {
aux->origen = org;
aux->destino = dest;
aux->valor = valor;
aux-> sig= org->ady;
org->ady = aux;
aux_inv->origen = org;
aux_inv->destino = dest;
aux_inv-> valor= valor;
aux_inv-> sig= dest->inc;
des_inc-> = aux_inv;
}
}
void BorrarArco(tnodo org, tnodo dest, tgrafo g)
{
tarco a,ant;
int enc=0;
if (org->ady==NULL) return;
else if (org->ady->destino==dest) {
a = org->ady;
org->ady = a->sig;
free(a);
}
else {
ant = org->ady;
a = ant->sig;
while (!enc && (a!=NULL)) {
if (a->destino==dest) enc=1;
else {
a = a->sig;
ant = ant->sig;
}
}
if (a==NULL) return;
else {
ant->sig = a->sig;
free(a);
}
}
enc=0;
if (dest->inc==NULL) return;
else if (dest->inc->origen==org) {
a = dest->inc;
dest->inc = a->sig;
free(a);
}
else {
ant = dest->inc;
a = ant->sig;
while (!enc && (a!=NULL)) {
if (a->origen == org) enc=1;
else {
a = a->sig;
ant = ant->sig;
}
}
if (a==NULL) return;
else {
ant->sig = a->sig;
free(a);
}
}
}
void Destruir(tgrafo G)
{
tnodo n;
tarco a_aux;
while (g->sig != NULL) {
n = g->sig;
while (n->ady != NULL) {
a_aux = n->ady;
n->ady = a_aux->sig;
free(a_aux);
}
while (n->inc != NULL) {
a_aux = n->inc;
n->inc = a_aux->sig;
free(a_aux);
}
g->sig = n->sig;
free(n->etiq);
free(n);
}
free(g);
}
tgrafo DesconectarNodo(tnodo a_eliminar,tgeafo g)
{
tgrafo g_nd;
tnodo n;
tnodo org;dst;
tnodo o,d;
tarco a;
g_nd = Crear();
for (n=PrimerNodo(g); n!=NULL; n=SiguienteNodo(n,g))
InsertarNodo(Etiqueta(n,g),g_nd);
for (n=PrimerNodo(g); n!=NULL; n=SiguienteNodo(n,g))
for (a=PrimerArco(n,g); a!=NULL; a=SiguienteArco(n,a,g)) {
org = NodoOrigen(a,g);
dst = NodoDestino(a,g);
if ((org!=a_eliminar) && dst!=a_eliminar)) {
o = LocalizaLabel(Label(org,g), g_nd);
d = LocalizaLabel(Label(dst,g), g_nd);
InsertarArco(o,d,g_nd);
}
}
return g_nd;
}
tgrafo CopiarGrafo(tgrafo g)
{
tgrafo g_nd;
tnodo n;
tnodo org;dst;
tnodo o,d;
tarco a;
int lb;
g_nd = Crear();
for (n=PrimerNodo(g); n!=NULL; n=SiguienteNodo(n,g))
InsertarNodo(Etiqueta(n,g),g_nd);
for (n=PrimerNodo(g); n!=NULL; n=SiguienteNodo(n,g))
for (a=PrimerArco(n,g); a!=NULL; a=SiguienteArco(n,a,g)) {
org = NodoOrigen(a,g);
dst = NodoDestino(a,g);
o = LocalizaLabel(Label(org,g), g_nd);
d = LocalizaLabel(Label(dst,g), g_nd);
InsertarArco(o,d,g_nd);
}
}
return g_nd;
}
|
|
| |
| Terminos de Uso |
|
1 - Copiar o Descargarse este contenido implica aceptar los terminos aqui detallados.
2 - Usted puede utilizar este contenido en sus propios programas y puede compilarlo en un programa y modificarlo a su gusto.
3 - Usted NO PUEDE redistribuir este contenido tal como se presenta aqui sin el permiso del autor original del mismo.
4 - Usted seguirá cualquier restricción adicional del copyright que el autor pudo haber puesto en la descripción del contenido.
|
|
|
|
|
