Representación en computadora de relaciones y dígrafos
El método directo para almacenar elementos de datos es colocarlos en una lista o arreglo lineal. Esto equivale a poner elementos de datos consecutivos en lugares de almacenamiento con numeración consecutiva en la memoria de la computadora. La siguiente figura ilustra dicho método para cinco elementos.
El problema principal que se tiene con este método es que no se puede insertar nuevos datos entre los datos existentes sin tener que mover un número que podría ser muy grande de elementos.
Un método alternativo para representar esa secuencia de datos es por medio de una lista enlazada, que se muestra esquemáticamente en la siguiente figura. Se imagina que tales celdas tienen espacio para dos elementos de información. El primero puede ser de datos (números o símbolos), y el segundo elemento es un apuntador (puntero), es decir un número que dice (señala) la localización de la siguiente celda. En consecuencia, las celdas pueden estar dispuestas en sucesión, pero los datos no necesariamente están en sucesión.
En la práctica el concepto de lista enlazada por punteros, se puede poner a funcionar utilizando dos arreglos enlazados, un arreglo de datos A y un arreglo de apuntadores P, como se muestra a continuación. Obsérvese que una vez que se ha tenido acceso a los datos de la posición A[i], el número de la posición P[i], da o señala, el índice de A que contiene el siguiente elemento de datos.
Ejemplo:
Considere la relación cuyo dígrafo aparece a continuación
Si se desea almacenar el dígrafo en forma de lista enlazada de manera que el orden lógico coincida con la numeración de sus lados, se puede usar el siguiente esquema.
El esquema anterior nos permite seguir el rastro del proceso, sin embargo, el mismo presenta desventajas importantes. En muchos algoritmos, es eficiente localizar un vértice, y luego comenzar de inmediato a investigar los lados que comienzan o terminan en ese vértice. En general esto no es posible con el esquema anterior, por lo que se proporciona una modificación al mismo. Usaremos un arreglo denominado VERT que tiene una posición para cada vértice en el dígrafo. Para cada vértice I, se deben arreglar los apuntadores de SIGUE de manera que enlacen todos los lados que salgan de I, que inicie en el lado al que señale VERT[I]. En cada caso el último de esos lados apuntará a cero. En este modelo Los arreglos COLA y CABEZA contienen realmente varias listas enlazadas de lados, una lista para cada vértice.
