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).
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(V2). 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
+5
ReplyDelete