Análisis y Diseño de Algoritmos                                                                                                      

Prof: Ing. Victor Garro

Asistente: Marco Elizondo Vargas

 

Grafos

 

Representación de Grafos

 

TDA GRAFO.

A la hora de diseñar el TDA grafo hay que tener en cuenta que hay que manejar datos correspondientes a sus vértices y aristas,pudiendo cada uno de ellos estar o no etiquetados.Además hay que proporcionar operaciones primitivas que permitan manejar el tipo de dato sin necesidad de conocer la implementación.Así,los tipos de datos que se usarán y las operaciones primitivas consideradas son las siguientes:

NUEVOS TIPOS APORTADOS.

Los nuevos tipos aportados por el TDA grafo son los siguientes:

• grafo.
• vertice.
• arista.

Existen diversas representaciones de naturaleza muy diferente que resultan adecuadas para manejar un grafo,y en la mayoría de los casos no se puede decir que una sea mejor que otra siempre ya que cada una puede resultar más adecuada dependiendo del problema concreto al que se desea aplicar.Así,si existe una representación que es peor que otra para todas las operaciones excepto una es posible que aún así nos decantemos por la primera porque precisamente esa operación es la única en la que tenemos especial interés en que se realice de forma eficiente.A continuación veremos dos de las representaciones más usuales:Matriz de adyacencia(o booleana) y Lista de adyacencia.

MATRIZ DE ADYACENCIA.

 

Grafos dirigidos.

G=(V,A) un grafo dirigido con |V|=n .Se define la matriz de adyacencia o booleana asociada a G como B_nxn con

 

Como se ve,se asocia cada fila y cada columna a un vértice y los elementos b_i,j de la matriz son 1 si existe el arco (i,j) y 0 en caso contrario.

Grafos no dirigidos.

G=(V,A) un grafo no dirigido con |V|=n .Se define la matriz de adyacencia o booleana asociada a G como B_nxn con:

La matriz B es simetrica con 1 en las posiciones ij y ji si existe la arista (i,j).

EJEMPLO:

 

Si el grafo es etiquetado,entonces tanto b_i,j como b_i,j representan al coste o valor asociado al arco (i,j) y se suelen denominar matrices de coste. Si el arco (i,j) no pertenece a A entonces se asigna b_i,j o b_i,j un valor que no puede ser utilizado como una etiqueta valida.

La principal ventaja de la matriz de adyacencia es que el orden de eficiencia de las operaciones de obtencion de etiqueta de un arco o ver si dos vertices estan conectados son independientes del número de vértices y de arcos. Por el contrario, existen dos grandes inconvenientes:

• Es una representación orientada hacia grafos que no modifica el número de sus vertices ya que una matriz no permite que se le o supriman filas o columnas.
• Se puede producir un gran derroche de memoria en grafos poco densos (con gran número de vértices y escaso número de arcos).

Para evitar estos inconvenientes se introduce otra representación: las listas de adyacencia.

LISTAS DE ADYACENCIA.

En esta estructura de datos la idea es asociar a cada vertice i del grafo una lista que contenga todos aquellos vértices j que sean adyacentes a él. De esta forma sóllo reservará memoria para los arcos adyacentes a i y no para todos los posibles arcos que pudieran tener como origen i. El grafo, por tanto, se representa por medio de un vector de n componentes (si |V|=n) donde cada componente va a ser una lista de adyacencia correspondiente a cada uno de los vertices del grafo. Cada elemento de la lista consta de un campo indicando el vértice adyacente. En caso de que el grafo sea etiquetado, habrá que añadir un segundo campo para mostrar el valor de la etiqueta.

Esta representacion requiere un espacio proporcional a la suma del número de vértices, más el nùmero de arcos, y se suele usar cuando el número de arcos es mucho menor que el número de arcos de un grafo completo. Una desventaja es que puede llevar un tiempo O(n) determinar si existe un arco del vértice i al vértice j, ya que puede haber n vertices en la lista de adyacencia asociada al vértice i.

Mediante el uso del vector de listas de adyacencias sólo se reserva memoria para los arcos existentes en el grafo con el consiguiente ahorro de la misma. Sin embargo, no permite que haya vértices que puedan ser añadidos o suprimidos del grafo, debido a que la dimension del grafo debe ser predeterminadoa y fija. Para solucionar esto se puede usar una lista de listas de adyacencia. Sólo los vértices del grafo que sean origen de algun arco aparecerán en la lista. De esta forma se pueden añadir y suprimir arcos sin desperdicio de memoria ya que simplemente habrá que modificar la lista de listas para reflejar los cambios.

Como puede verse en el ejemplo de las figuras anteriores tanto el vector de listas de adyacencias como en la lista de listas se ha razonado en función de los vértices que actúan como origenes de los arcos. Análogamente se podía haber hecho con lod vertices destino, y combinando ambas representaciones podría pensarse en utilizar dos vectores de listas de adyacencia o dos listas de listas de adyacencia.

REPRESENTACION PROPUESTA.

La elección de una estructura idónea para representar el TDA grafo no es una tarea fácil ya que existen dos representaciones totalmente contrapuestas: por un lado tenemos la matriz de adyacencias que es muy eficiente para comprobar si existe una arista uniendo dos vertices peero que sin embargo desperdicia una gran cantidad de espacio si el grafo no es completo o esta lejos de serlo, además no tiene la posibilidad de añadir nuevos vértices; y por otra parte está la lista de adyacencias que no tiene el problema de la anterior respecto al espacio pero que sin embargo no es tan eficiente a la hora de ver si existe una arista entre dos nodos determinados.

Teniendo en cuenta estas consideraciones se ha optado por realizar una mezcla de ambas representaciones intentando aprovechar de alguna forma las ventajas que ambas poseen. Por otra parte siguiendo con la idea de tratar tanto los grafos dirigidos como los no dirigidos bajo una misma estructura, la estructura elegida posee dos apariencias ligeramente diferentes para tratar de forma adecuada cada uno de estos dos tipos de grafos.

La estructura consiste (en el caso de que tengamos un grafo dirigido en una lista de vértices donde cada uno de estos posee dos listas, una de aristas incidentes a él y otra de adyacentes. Cada vez que se añade una arista al grafo se inserta en la lista de aristas adyacentes del vertice origen y en la de incidentes del vértice destino. De esta forma la estructura desplegada se asemejaría a una matriz de adyacencia en la cual hay una arista por cada 1 y el índice de la matriz es la posición dentro de la lista de vertices.

Graficamente la estructura para un grafo dirigido queda como se puede apreciar en la siguiente figura.El puntero que de la estructura arco que apunta al destino se ha sustituido por la etiqueta del nodo destino en el grafico para simplificarlo y hacerlo mas claro.

Esta estructura no seria la mas idonea si trabajamos con solo con grafos no dirigidos ya que por cada arista no dirigida tendriamos que insertar en la estructura una misma arista dirigida repetida dos veces (una con un vértice como origen y el otro como destino y al contrario). En muchos problemas si asumimos el desperdicio de espacio podria , de todas formas, resultar interesante representar un grafo no dirigido como un grafo dirigido simetrico, el problema se preesenta cuando al tener dos aristas dirigidas esto supone la presencia de un ciclo en el grafo que realmente no existe.

Teniendo en cuenta el razonamiento anterior, en el caso de que queramos manejar grafos no dirigido la estructura consistiria en tener una lista de adyacencia para cada uno de los vertices pero tratando aquellas aristas que aparecen en la lista de adyacencia de dos vertices distintos y que unen ambos vértices como una única arista lógica (a estas dos aristas que forman una misma arista lógica las llamaremos aristas gemelas).

Estructuras Internas.

Esta representacion tiene tres estructuras diferenciadas:

• Estructura correspondiente a un vértice.
• nodo: Codigo interno que permite numerar los nodos de 1 a n.
• etiq: Puntero a caracter en el que se encuentra la información que posee ese vértice, es decir su etiqueta.
• ady: Es un puntero a una lista que contiene las aristas que tienen como origen ese vértice.
• inc: Es un puntero a una lista que contiene las aristas que tienen como destino ese vértice (solo para grafos dirigidos).
• sig: Es un puntero que apunta al vértice que ocupa la posicion siguiente dentro de la lista de vertices.

 

• 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:
• nodo: Contien el número de nodos del grafo.
• sig: Es un puntero que apunta al vértice que ocupa la primera posicion dentro de la lista de vertices.

 

• Estructura correspondiente a una arista (grafo dirigido).
• origen: Es un puntero al vértice que es el origen de esa arista.
• 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).
• valor: Este campo contiene el peso de la arista que sera un numero entero.
• sig: Puntero que apunta a la siguente arista dentro de la lista de aristas adyacentes o incidentes.

 

Estructuras Internas del TDA grafo.

 

/* Implementacion 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;