EsTrUcTuRaS De DaToS

jueves, 21 de mayo de 2009

ESTRUCTURA DE DATOS EN LA REPRESENTACION DE GRAFOS

Estructuras de datos en la representación de grafos [editar]
Artículo principal: Grafo (estructura de datos)
Existen diferentes formas de almacenar grafos en una computadora. La estructura de datos usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria.
Estructura de lista [editar]
lista de incidencia - Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido), donde cada par representa una de las aristas.
lista de adyacencia - Cada vértice tiene una lista de vértices los cuales son adyacentes a él. Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las búsquedas son más rápidas, al costo de almacenamiento extra.
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ólo 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.

GRAFOS

Implementación en Java
/**
* Calcular el camino mínimo en un grafo
*/
public static CaminoConPesos caminoMinimoAciclico
(Grafo g, int origen, int destino)
throws NoExiste, IdIncorrecto, HayCiclos
{
int anterior[]= new int[g.numVertices()];
double[] peso= new double[g.numVertices()];
// dar valor infinito a todas las casillas de peso
for (int i=0; i procesar =
new LinkedList();
int procesados=0;
// insertar en la cola vértices de grado cero
for (int v=0; v> ady=g.listaAristas(v);
for (Arista a: ady) {
int dest=a.destino();
grado[dest]--;
if (grado[dest]==0) {
procesar.addLast(new Integer(dest));
}
if (!Double.isInfinite(peso[v])) {
double p=a.contenido().doubleValue();
if (peso[dest]>peso[v]+p) {
anterior[dest]=v;
peso[dest]=peso[v]+p;
}
}
}
}
if (procesados!=g.numVertices()) {
throw new HayCiclos();
}
if (Double.isInfinite(peso[destino])) {
throw new NoExiste();
} else {
return caminoDe
(origen,destino,anterior,peso[destino],g);
}
}