Relaciones Como Listas Enlazadas
Relaciones Como Listas Enlazadas
Relaciones Como Listas Enlazadas
CAPTULO 6. RELACIONES
2
2 7 1 5 9 6 4 1 6 1 3 8
Suponer que se coloca la informacin en los arreglos primeramente todas las aristas que salen del nodo 1, despus todas las que salen del 2 y as sucesivamente de tal forma que se tiene: X=* 1 2 3 4 5 6 7 8 9 10 . . N D 1 1 1 2 2 3 3 3 5 6 A 2 3 6 1 3 4 5 6 4 1 P
En lugar de acomodar la informacin en los arreglos de acuerdo a las arista que salen de un nodo, podra ser de acuerdo a las que llegan o bien sin guardar ningn orden.
De tal forma que colocando la informacin en el arreglo P e indicando el inicio del recorrido se tiene que para recorrer el grafo de acuerdo a la numeracin de las aristas. X=5 1 2 3 4 5 6 7 8 9 10 . . N D 1 1 1 2 2 3 3 3 5 6 A 2 3 6 1 3 4 5 6 4 1 P 7 3 6 9 4 1 10 * 2 8
X=5 indica que la arista numerada con el 1 est en la posicin 5, el arreglo P indica que la arista 2 est en la posicin 1 y as sucesivamente hasta recorrer todas las aristas del grafo.
Posiblemente se desee recorrer el mismo grafo por vrtices, primero todas las que salen del nodo 1 de acuerdo al nmero de la arista y despus todas las que salen del nodo 2, de acuerdo a la numeracin de las aristas de tal manera que se puede tener un conjunto de listas, cada una de ellas correspondiente a cada vrtice, como se muestra a continuacin.
1 2 3 4 5 6
Nodo 1 4 6 * 9 10
1 2 3 4 5 6 7 8 9 10 . . N
D 1 1 1 2 2 3 3 3 5 6
A 2 3 6 1 3 4 5 6 4 1
P 2 3 * 5 * 7 8 * * *
En este caso se tiene una lista para cada nodo de acuerdo a las aristas que salen de l. Ejemplo la arista ms pequea que sale del nodo 1 est en la posicin 1, despus la que est en la posicin 2 y la ltima que de este nodo se encuentra en la posicin 3. El nodo 4 no tiene ninguna arista que salga de l es por esa razn que su lista es nula.
Lo importante; es que es posible representar las relaciones por medio de arreglos, permitiendo de esta manera facilidad en su manejo. Ejemplo 1: Recorrer el siguiente grafo, de acuerdo al orden que marcan las aristas, usando para ello el arreglo D para guardar la informacin del nodo de donde sale la arista, el arreglo A para guardar la informacin a donde llega la flecha y el arreglo P para indicar la arista siguiente, adems de la variable X para indicar el inicio del recorrido.
2 1 1
9 7 11
3
10
4 5
8
1 2 3 4 5 6 7 8 9 10 11
Ejercicio 1: Recorrer el siguiente grafo de acuerdo al orden de las aristas usando para ello los arreglos A, P y la variable X para indicar el inicio del recorrido de la informacin.
2
5 4 8 7 6
3 4
2 3 10
11
Ejemplo 2: Para recorrer el grafo del problema 1 por vrtices, de acuerdo al nmero de las aristas. Primero todas las aristas que salen del nodo 1, respetando su numeracin, despus todas las aristas que salen del nodo 2, de acuerdo a la numeracin de la arista y as sucesivamente. Si los datos del grafo en los arreglos D y A se coloca como se muestra a continuacin. Completar la informacin faltante en los arreglos nodo y P.
Nodo 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11
D 2 6 3 5 1 4 1 3 4 3 6
A 1 5 4 2 4 5 5 2 6 6 3
1 2 3 4 5 6
1 2 3 4 5 6 7 8 9 10 11
Ejercicio 2: Para recorrer el grafo del problema 1 se tiene la informacin en los arreglos D y A como se indica a continuacin. Colocar la informacin faltante en los arreglos nodo y P para llevar a cabo el recorrido por vrtices. Primero todas las aristas que salen del nodo 1respetando la numeracin, despus las del nodo 2 y as sucesivamente.
Nodo 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 9 10 11 12 13 14
D 4 6 2 1 4 2 1 4 3 5 7 7 5 6
A 5 2 3 6 6 4 2 1 4 3 4 2 7 7