Grafos

REPRESENTACION DE GRAFOS
Orlando Arboleda Molina
Escuela de Ingenier´ıa de Sistemas y Computaci´on de
La Universidad del Valle
8 de septiembre de 2008

Contenido
Representaci´on de grafos
Matrices de adyacencia
Matrices de incidencia

Representaci´on de grafos
Los grafos sin aristas m´ ultiples pueden ser representados de la
siguiente manera:
Listando todas las aristas de su grafo.

Usando listas de adyacencia (especifica v´ ertices que son
adyacentes).

Usando matrices.

Matrices de adyacencia
Suponga que G = (V,E) es un grafo simple donde | V |= n.
Suponga que los v´ ertices de G son listados arbitrariamente
como v1, v2, ...., vn. la matriz de adyacencia A (o AG) de G, con
respecto a su lista de v´ ertices es la matriz nxn talque:
aij = ½ 1 si {vi , vj} es una arista de G
0 en caso contrario
Nota: esta matriz es sim´ etrica.

Matrices de adyacencia (2)
Ejercicio: Dibujar el grafo representado por la siguiente matriz
de adyacencia. Donde los v´ ertices han sido ordenados como
a, b, c, d. 2664
0 1 1 1
1 0 1 0
1 1 0 0
1 0 0 0
3775

Matrices de incidencia
Suponga que G = (V,E) es un grafo no dirigido. Suponga que
los v´ ertices de G son listados arbitrariamente como
v1, v2, ...., vn y las aristas como e1, e2, ...., em, la matriz de
incidencia, con respecto a su lista de v´ertices y aristas, es la
matriz nxm talque:
mij = ½ 1 si la arista ej es incidente con vi
0 en caso contrario
Nota1: esta matriz no es sim´ etrica.
Nota2: tambi´en pueden ser utilizadas para representar aristas
multiples

Matrices de incidencia (2)
Ejercicio: Dibujar el grafo representado por la siguiente matriz
de incidencia. Donde los v´ ertices han sido ordenados como
v1, v2, v3, v4. 2664
0 1 1 0
1 0 1 1
0 1 0 0
0 0 0 1
3775

Codigo java grafos

BUSQUEDA ANCHURA
struct tcola *cola;

void visitar(int k) // listas de adyacencia
{
struct nodo *t;
encolar(&cola,k);
while (!vacia(cola))
{
desencolar(&cola,&k);
val[k]=++id;
for (t=a[k]; t!=z; t=t->sig)
{
if (val[t->v]==0)
{
encolar(&cola,t->v);
val[t->v]=-1;
}
}
}
}


BUSQUEDA DE PROFUNDIDAD

int id=0;
int val[V];

void buscar()
{
int k;
for (k=1; k<=V; k++)
val[k]=0;
for (k=1; k<=V; k++)
if (val[k]==0) visitar(k);
}

void visitar(int k) // matriz de adyacencia
{
int t;
val[k]=++id;
for (t=1; t<=V; t++)
if (a[k][t] && val[t]==0) visitar(t);
}

void visitar(int k) // listas de adyacencia
{
struct nodo *t;
val[k]=++id;
for (t=a[k]; t!=z; t=t->sig)
if (val[t->v]==0) visitar(t->v);
}


* Implementacion basada en una lista de nodos de los que cuelga */
/* la lista de arcos de salida. */



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;



LISTAS DE ADYACENCIA
struct nodo
{
int v;
int p;
nodo *sig;
};

int V,A; // vértices y aristas del grafo
struct nodo *a[maxV], *z;

void inicializar()
{
int i,x,y,peso;
char v1,v2;
struct nodo *t;
z=(struct nodo *)malloc(sizeof(struct nodo));
z->sig=z;
for (i=0; i a[i]=z;
for (i=0; i {
scanf("%c %c %d\n",&v1,&v2,&peso);
x=v1-'A'; y=v2-'A';

t=(struct nodo *)malloc(sizeof(struct nodo));
t->v=y; t->p=peso; t->sig=a[x]; a[x]=t;

t=(struct nodo *)malloc(sizeof(struct nodo));
t->v=x; t->p=peso; t->sig=a[y]; a[y]=t;
}
}