Los
grafos son artefactos matemáticos que permiten expresar de una forma
visualmente muy sencilla y efectiva las relaciones que se dan entre
elementos de muy diversa índole. Un grafo simple está formado por
dos conjuntos:
Un
conjunto V de puntos llamados vértices o nodos.
Un conjunto de pares de
vértices que se llaman aristas o arcos y que indican qué nodos
están relacionados.
Un
grafo G es un par (V,E) donde:
V
={v1,…,vn} es un conjunto de vértices
E
= {e1,…,em} es un conjunto de aristas,
con
cada ek {vi, vj}, con vi,
vj V, vi ≠ vj
Los
vértices se representan como puntos y las aristas como líneas entre
vértices
Ejemplo:
G
= (V,E)
V
= {a,b,c,d }
E
= {{a,b}, {b,c}, {a,c}, {a,d}, {d,b} }
Algunos conceptos basicos:
*Dos
vértices se dicen adyacentes si existe una arista que los
une.
*Los
vértices que forman una arista son los extremos de la
arista.
*Si
v es un extremo de una arista a , se dice que a
es incidente con v
*El
grado de un vértice v , gr(v) es el número de
aristas incidentes en v. Si hace falta indicar el grafo en
el que está v escribiremos gr(G,v).
Representación
de grafos
Una característica especial en los grafos es que podemos
representarlos utilizando dos estructuras de datos distintas. En
particular, los tiempos de ejecución variarán en función del
número de vértices y el de aristas, por lo que la utilización de
una representación u otra dependerá en gran medida de si el grafo
es denso o disperso.
Representación por matriz de adyacencia
Es la forma más común de representación y la más directa.
Consiste en una tabla de tamaño V x V, en que la que a[i][j] tendrá
como valor 1 si existe una arista del nodo i al nodo j. En caso
contrario, el valor será 0. Cuando se trata de grafos ponderados en
lugar de 1 el valor que tomará será el peso de la arista. Si el
grafo es no dirigido hay que asegurarse de que se marca con un 1 (o
con el peso) tanto la entrada a[i][j] como la entrada a[j][i], puesto
que se puede recorrer en ambos sentidos.
int V,A;
int a[maxV][maxV];
void inicializar()
{
int i,x,y,p;
char v1,v2;
// Leer V y A
memset(a,0,sizeof(a));
for (i=1; i<=A; i++)
{
scanf("%c %c %d\n",&v1,&v2,&p);
x=v1-'A'; y=v2-'A';
a[x][y]=p; a[y][x]=p;
}
}
En esta implementación se ha supuesto que los vértices se nombran
con una letra mayúscula y no hay errores en la entrada.
Evidentemente, cada problema tendrá una forma de entrada distinta y
la inicialización será conveniente adaptarla a cada situación. En
todo caso, esta operación es sencilla si el número de nodos es
pequeño. Si, por el contrario, la entrada fuese muy grande se pueden
almacenar los nombres de nodos en un árbol binario de búsqueda o
utilizar una tabla de dispersión, asignando un entero a cada nodo,
que será el utilizado en la matriz de adyacencia.
La matriz de adyacencia siempre ocupa un espacio de V*V, es decir,
depende solamente del número de nodos y no del de aristas, por lo
que será útil para representar grafos densos.
Representación por lista de adyacencia
Otra forma de representar un grafo es por medio de listas que
definen las aristas que conectan los nodos. Lo que se hace es definir
una lista enlazada para cada nodo, que contendrá los nodos a los
cuales es posible acceder. Es decir, un nodo A tendrá una lista
enlazada asociada en la que aparecerá un elemento con una referencia
al nodo B si A y B tienen una arista que los une. Obviamente, si el
grafo es no dirigido, en la lista enlazada de B aparecerá la
correspondiente referencia al nodo A.
Las listas de adyacencia serán estructuras que contendrán un
valor entero (el número que identifica al nodo destino), así como
otro entero que indica el coste en el caso de que el grafo sea
ponderado. En el ejemplo se ha utilizado un nodo z ficticio en la
cola.
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<V; i++)
a[i]=z;
for (i=0; i<A; 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;
}
}
En este caso el espacio ocupado es O(V + A), muy distinto del
necesario en la matriz de adyacencia, que era de O(V
2). La
representación por listas de adyacencia, por tanto, será más
adecuada para grafos dispersos.
Hay que tener en cuenta un aspecto importante y es que la
implementación con listas enlazadas determina fuertemente el
tratamiento del grafo posterior.
BIBLIOGRAFIA
http://www.youtube.com/watch?v=wUCDZiTM59g
