Representación de grafos mediante matrices dispersas

Solo disponible en BuenasTareas
  • Páginas : 2 (330 palabras )
  • Descarga(s) : 0
  • Publicado : 5 de octubre de 2010
Leer documento completo
Vista previa del texto
REPRESENTACIÓN DE GRAFOS MEDIANTE MATRICES DISPERSAS
Para evitar uno de los problemas que teníamos con las listas de adyacencia, que era la dificultad de obtener las relaciones inversas, podemosutilizar las matrices dispersas, que contienen tanta información como las matrices de adyacencia, pero, en principio, no ocupan tanta memoria como las matrices, ya que al igual que en las listas deadyacencia, sólo representaremos aquellos enlaces que existen en el grafo.
Matrices dispersas (también se conocen como matrices ralas ó sparse matrix): son matrices grandes donde la mayor parte de loselementos son ceros. Se dan mucho en algunos problemas de ingeniería.
Implementación

Una posible Representación para este tipo de Matrices sería hacer una Lista de Listas, para lo cual seutilizaría el concepto de Listas de Adyacencia, solo en vez de usar un arreglo para identificar, en este caso, las filas se utilizaría otra lista.
Ejemplo:
Si se posee la siguiente disposición:La Lista de Listas sería la siguiente:
0 0 2 ^


1 1 2 ^2 1 ^
^

Según el Libro de Pfaltz, podríamos implementar este tipo de modelo de 2 formas distintas, esta distinción se realiza en la estructurade los nodos
Forma 1:
*filas numero *columna
dato
En donde *filas y *columna son punteros, numero indica el numero de fila o el numero de la columna al cual pertenezca el nodo y el dato es lacantidad de vecinos vivos posee la celda.
En esta forma existen 2 listas que en el dato no posee ningún dato, ya que son los índices de las filas y/o columnas

Forma 2:
*filas numero_f numero_c*columna
dato
En donde *filas y *columna son punteros, numero_f indica el numero de fila y el numero_c el numero de la columna al cual pertenezca el nodo y el dato es la cantidad de vecinos vivos...
tracking img