Download árboles y grafos

Tema 4
Estructura de datos no lineales
Arboles y Grafos
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.1 Arboles
4.1.1. Introducción
Las estructuras de datos vistas en apartados anteriores son de tipo lineales,
dado que a cada elemento le seguía siempre otro elemento. Esa linealidad
es típica en cadenas, listas, array, pilas, colas, campos en los registros, etc.-.
Pero existen otras estructuras de datos con características no lineales, es
decir, se introduce el concepto de bifurcación dado que en estas estructuras
cada elemento puede tener diferentes siguientes elementos. Estas
estructuras reciben el nombre de árboles y grafos, otros autores le dan el
nombre de estructuras multi-enlazadas.
Si nos referimos a estructuras de datos, se dijo en el tema anterior que las
pilas, colas y listas son estructuras lineales, puesto que en todas ellas cada
elemento tiene un único elemento anterior y un único elemento posterior.
Pero, además, existe estructuras de datos no lineales, en las que esta
restricción desaparece. Esto es, en estas estructuras cada elemento puede
tener varios anteriores y/o varios posteriores.
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.1 Arboles
4.1.1. Introducción
Definición
Un árbol es una estructura de datos no lineal y homogénea en el que
cada elemento puede tener varios elementos posteriores, pero tan
sólo puede tener un elemento anterior.
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.1 Arboles
4.1.2 Representación
Gráficamente puede representarse una estructura de árbol de diferentes
formas y serán todas ellas equivalentes.
E
G
B
F
A
D
( A ( B ( D , E ) ), C ( F ( G , H ) ) )
b) Anidación de Paréntesis
H
C
a) Diagrama de Venn
A
A
B
E
D
B
C
C
D
F
E
F
G
G
H
a) su representación está dada
por un diagrama de Venn.
b) por medio de anidación de
paréntesis.
c)
por
medio
de
la
representación indentada
d) por medio de grafos.
H
c) Identada
d) Grafo
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.1 Arboles
4.1.3 Terminologia básica
A
A
B
C
D
E
G
Ejemplo 1
A
B
F
C
H
Ejemplo 2
Ejemplo 3
Nodo Padre de un nodo N es aquel que apunta al mismo. En un árbol cada
nodo sólo puede tener un padre. En el ejemplo 1, A es el padre de B y C, y a
su vez, B es el padre de D.
Nodo Hijo de otro nodo A hijo es cualquier nodo apuntado por el nodo A. Un
nodo puede tener varios hijos. En el ejemplo 1, B y C son los nodos hijos de
A y todos los nodos tienen uno o dos hijos.
Nodo Raíz es el único del árbol que no tiene padre. En la representación que
hemos utilizado, el nodo raíz es el que se encuentra en la parte superior del
árbol: A.
Hojas son todos los nodos que no tienen hijos. En la representación del
ejemplo 1 son hojas los nodos situados en la parte inferior: D, G, H y F.
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.1 Arboles
4.1.3 Terminologia básica
A
A
B
C
D
E
G
Ejemplo 1
A
B
F
C
H
Ejemplo 2
Ejemplo 3
Nodos Interiores son los nodos que no son ni el nodo raíz, ni nodos hoja. En
el ejemplo 1, son nodos interiores B, C y E.
Camino es una secuencia de nodos, en el que dos nodos consecutivos
cualesquiera son padre e hijo. En el ejemplo 1 A-B-D es un camino, al igual
que E-G y C-E-H.
Rama es un camino desde el nodo raíz a una hoja. En el ejemplo 1, A-C-E-G
y AC-F son ramas.
Altura es el máximo número de nodos de las ramas del árbol. Dicho en otros
términos, el máximo número de nodos que hay que recorrer para llegar de la
raíz a una de las hojas. La altura del árbol del ejemplo 1 es 4, ya que esa es
la longitud de la rama A-C-E-H, que junto a A-C-E-G son las dos más largas.
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.1 Arboles
4.1.3 Terminología básica
A
A
B
C
D
E
G
Ejemplo 1
A
B
F
C
H
Ejemplo 2
Ejemplo 3
Grado es el número máximo de hijos que tienen los nodos del árbol. Así, en
el ejemplo anterior el árbol es de grado dos. Démonos cuenta de que una
lista no es más que un árbol de grado uno, tal y como podemos ver en los
ejemplos 2 y 3.
Nivel de un nodo, es el número de nodos del camino desde la raíz hasta
dicho nodo. En el árbol del ejemplo 1, A tiene nivel 1; B y C tienen nivel 2; D,
E y F tienen nivel 3 y G y H tienen nivel 4.
Bosque colección de dos o más árboles.
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.1 Arboles
4.1.4 Arbol Binario
Existe un tipo de arbol denominado arbol binario que puede ser
implementado facilmente en la computadora.
Definicion
Un arbol binario es un conjunto finito de cero o mas nodos tales que:
●
Existe un nodo denominado raiz del arbol.
●
Cada nodo puede tener 0,1, o 2 subarboles, conocidos como subarbol
izquierdo y subarbol derecho.
La figura representa diferentes tipos de arboles binarios: A) expresion de arbol A+B/C, y B) son
arboles de operación aritmetica con valores enteros
A)
/
B
B)
+
A
C
C)
5
+
100
A
B
D
C
E
G
F
H
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.1 Arboles
4.1.4 Arbol Binario
Si tomamos el grafico C) de la figura vemos que es un árbol binario, ya que cada
nodo tiene como máximo dos hijos.
Démonos cuenta que en cualquier árbol, no sólo en los binarios, si eliminamos el
nodo raíz, obtenemos dos árboles.
- Aquel que colgaba del enlace izquierdo del nodo raíz se denomina subárbol
izquierdo
- Aquel que colgaba del enlace derecho se denomina subárbol derecho.
Además, en un árbol binario, todos los subárboles son también árboles binarios.
De hecho, a partir de cualquier nodo de un árbol podemos definir un nuevo árbol
sin más que considerarlo como su nodo raíz. Por tanto, cada nodo tiene
asociados un subárbol derecho y uno izquierdo.
A)
/
B
B)
+
A
C
C)
5
+
100
A
B
D
C
E
G
F
H
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.1 Arboles
4.1.4 Arbol Binario
Existen algunos tipos especiales de árboles binarios en función de ciertas
propiedades. Así por ejemplo:
Árbol binario equilibrado es aquel en el que en todos sus nodos se cumple la
siguiente propiedad,
altura(subárbol_izquierdo) - altura(subárbol_derecho) | <=
1.
Así, el árbol del ejemplo 1 de la figura sería un árbol binario equilibrado, mientras
el del ejemplo 2 no lo sería. En el segundo caso el subárbol izquierdo de A tiene
una altura 2, mientras su subárbol derecho tiene una altura 0.
A
A
B
C
D
E
G
Ejemplo 1
A
B
F
C
H
Ejemplo 2
Ejemplo 3
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.1 Arboles
4.1.4 Arbol Binario
Árbol binario completo es aquel en el que todos los nodos tienen dos hijos y
todas las hojas están en el mismo nivel.
Se denomina completo porque cada nodo, excepto las hojas, tiene el máximo de
hijos que puede tener.
En estos árboles se cumple que en el nivel k hay 2k-1 nodos y que, en total, si la
altura es h, entonces hay 2h - 1 nodos.
A
B
D
C
E
F
G
La figura representa un árbol binario
completo.
En el nivel 1 tenemos 20 = 1 nodos
En el nivel 2 tenemos 21 = 2 nodos
En el nivel 3 tenemos 22=4 nodos.
En total el árbol es de altura 3 y por tanto
contiene 23-1 = 7 nodos.
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.1 Arboles
4.1.5 Implementación de un Arbol Binario
Al igual que ocurre en el caso de las listas, podemos implementar un
árbol binario mediante
●
estructuras estáticas
●
estructuras dinámicas.
En ambos casos, cada nodo del árbol contendrá tres valores:
La información de un tipobase dado contenida en el nodo.
●
Un enlace al hijo derecho (raíz del subárbol derecho)
●
Un enlace al hijo izquierdo (raíz del subárbol izquierdo)
●
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.1 Arboles
4.1.5 Implementación de un Arbol Binario
Implementación estática mediante un vector
Para realizar la implementación estática del árbol binario utilizamos una
estrategia similar a la usada en las listas, en las que simulábamos la
memoria dinámica mediante el uso de vectores.
- Cada nodo es un registro con los tres campos especificados
anteriormente
- Todos los nodos se almacenan en un vector de registros.
- Para implementar los enlaces utilizaremos números enteros que serán
los índices en el vector donde se encuentran los hijos izquierdo y
derecho.
Al igual que ocurre en el caso de las listas, las componentes vacías del
vector se enlazan formando una lista. Para ello podemos usar como
campo de enlace, tanto el correspondiente a los hijos izquierdos como a
los derechos.
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.1 Arboles
4.1.5 Implementación de un Arbol Binario
Implementación estática mediante un vector
No vamos a detallar la implementación de todas las operaciones
mediante vectores, sino que tan sólo mostraremos la estructura de datos
en Pascal que usaremos para llevar a cabo esta implementación.
CONST
MAX = ... {Tamaño del vector y máximo número de nodos del árbol}
TYPE
Posicion = 0 .. MAX;
Elemento = RECORD
info: <TipoBase>;
der, izq: Posicion
END;
TipoArbolB= RECORD
raiz, vacios: Posicion;
mem : ARRAY [1..MAX] OF Elemento
END;
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.1 Arboles
4.1.5 Implementación de un Arbol Binario
Implementación estática mediante un vector
La representación mediante esta estructura estática del árbol de la figura
vendría dada por el siguiente vector de registros:
Raiz=1
1
2
A
3
0
4
Vacios= 5
4
5
6
C
E
6
12 11
8
10
3
B
9
0
7
2
8
F
0
0
9
D
0
0
10
H
0
0
11
G
0
0
12
7
Inf
Izq
Der
A
B
C
D
E
G
F
H
En el ejemplo anterior hemos utilizado el 0 para
indicar un enlace que no apunta a ningún nodo. Las
componentes del vector cuyos campos izq y der
contienen un 0 son las hojas del árbol. Mientras la
componente 2 es en este caso la última de la lista de
componentes vacías.
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.1 Arboles
4.1.5 Implementación de un Arbol Binario
Implementación dinámica mediante punteros
La representación de cada nodo en esta implementación será también
un registro de tres campos, pero en este caso los enlaces serán
punteros a los subárboles izquierdo y derecho de cada nodo. Por lo
tanto, la estructura de datos en Pascal para definir un árbol binario será
la siguiente:
TYPE
TArbol = ^Nodo;
Nodo = RECORD
info: <tipobase>;
izq, der: TArbol
END;
De este modo, un árbol se identifica con un puntero a su nodo raíz, a
través del cual podemos acceder a sus distintos nodos.
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.1 Arboles
4.1.5 Implementación de un Arbol Binario
Implementación dinámica mediante punteros
Recorrido de un Árbol binario
Recorrer un árbol consiste en acceder una sola vez a todos sus nodos.
En el caso de los árboles binarios, el recorrido de sus distintos nodos se
debe realizar en tres pasos:
●
acceder a la información de un nodo dado,
●
acceder a la información del subárbol izquierdo de dicho nodo,
●
acceder a la información del subárbol derecho de dicho nodo.
Imponiendo la restricción de que el subárbol izquierdo se recorre
siempre antes que el derecho, esta forma de proceder da lugar a tres
tipos de recorrido, que se diferencian por el orden en el que se realizan
estos tres pasos.
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.1 Arboles
4.1.5 Implementación de un Arbol Binario
Implementación dinámica mediante punteros
Recorrido de un Árbol binario
Preorden: primero se accede a la información del nodo, después al
subárbol izquierdo y después al derecho.
A-B-D-C-E-G-H-F
Recorrido Preorden
A
B
C
D
E
G
F
H
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.1 Arboles
4.1.5 Implementación de un Arbol Binario
Implementación dinámica mediante punteros
Recorrido de un Árbol binario
Inorden: primero se accede a la información del subárbol izquierdo,
después se accede a la información del nodo y, por último, se accede a
la información del subárbol derecho.
D-B-A-G-E-H-C-F
Recorrido Inorden
A
B
C
D
E
G
F
H
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.1 Arboles
4.1.5 Implementación de un Arbol Binario
Implementación dinámica mediante punteros
Recorrido de un Árbol binario
Postorden: primero se accede a la información del subárbol izquierdo,
después a la del subárbol derecho y, por último, se accede a la
información del nodo.
D-B-G-H-E-F-C-A
Recorrido Postorden
A
B
C
D
E
G
F
H
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.1 Arboles
4.1.6 Arbol Binario de Búsqueda
Imaginémonos que queremos encontrar un elemento en una lista ordenada. Para
hacerlo deberemos recorrer sus elementos desde el primero hasta encontrar el
elemento buscado o uno mayor que este. El coste medio de esta operación
involucrará en un caso medio el recorrido y comparación de n/2 nodos, y un coste
en el caso peor O(n). Si en lugar de utilizar una lista, estructuramos la
información de modo adecuado en un árbol, podremos reducir el coste de la
búsqueda a O(log2n).
Para hacernos una idea de lo que supone esta reducción del coste, supongamos
que queremos encontrar un elemento entre 1000. Si almacenamos toda la
información en una lista ordenada, esta búsqueda puede suponernos recorrer y
comparar hasta 1000 nodos. Si esta misma información la almacenamos en un
árbol binario de búsqueda, el coste máximo será de log2(1000)<10. Hemos
reducido el coste de 1000 a 10 al cambiar la estructura de datos utilizada para
almacenar la información.
Tal y como hemos dicho, no basta con almacenar la información en un árbol para
facilitar la búsqueda, debemos utilizar un tipo especial de árbol: un árbol binario
de búsqueda. Si además queremos que esta búsqueda sea lo más eficiente
posible debemos utilizar árboles de búsqueda binarios equilibrados.
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.1 Arboles
4.1.6 Arbol Binario de Búsqueda
Definición
Un árbol binario de búsqueda es una estructura de datos de tipo
árbol binario en el que para todos sus nodos, el hijo izquierdo, si
existe, contiene un valor menor que el nodo padre y el hijo
derecho, si existe, contiene un valor mayor que el del nodo padre.
5
3
9
1
7
6
10
8
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.1 Arboles
4.1.6 Arbol Binario de Búsqueda
Búsqueda de un elemento
La operación de búsqueda en un árbol binario de búsqueda es bastante sencilla
de entender.
Supongamos que buscamos un elemento x en el árbol.
Lo primero que haremos será comprobar si se encuentra en el nodo raíz. Si no
es así, si el elemento buscado es menor que el contenido en el nodo raíz
sabremos que, de estar en el árbol, se encuentra en el subárbol izquierdo. Si el
elemento buscado es mayor que el contenido en el nodo raíz sabremos que, de
estar en el árbol, se encuentra en el subárbol derecho. Para continuar la
búsqueda en el subárbol adecuado aplicaremos recursivamente el mismo
razonamiento.
Por lo tanto, el esquema del algoritmo BuscarNodo será el siguiente:
●
Si el valor del nodo actual es igual al valor buscado, lo hemos encontrado.
●
Si el valor buscado es menor que el del nodo actual, deberemos inspeccionar el
subárbol izquierdo.
●
Si el valor buscado es mayor que el del nodo actual, deberemos inspeccionar el
subárbol derecho.
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.1 Arboles
5
5
5
3
9
9
Insertar 8
Insertar 3
5
Insertar 7
NIL
Insertar un elemento
Insertar 9
Arbol vacio
Insertar 5
4.1.6 Arbol Binario de Búsqueda
5
3
9
3
9
7
7
Insertar 1
Insertar 6
Insertar 10
8
5
5
3
3
9
7
9
7
10
8
5
6
3
10
9
1
8
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
7
6
10
8
4.1.6 Arbol Binario de Búsqueda
Eliminar un elemento
Suprimir 8 (Caso a)
Arbol Inicial
4.1 Arboles
5
3
9
1
7
3
10
9
1
7
8
10
6
Suprimir 5 (Caso c)
Suprimir 7 (Caso b)
6
5
1
5
3
3
9
9
6
3
10
10
Suprimir 1 (Caso c)
6
Suprimir 9 (Caso c)
1
1
3
6
6
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
10
10
4.1 Arboles
4.1.6 Arbol Binario de Búsqueda
Arboles de expresiones aritmeticas
Por ejemplo, la siguiente expresion dada en notacion habitual
((3*(4+5))-7:2)):6
:
-
6
*
3
:
7
+
4
2
5
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.2 Grafos
4.2.1 Introducción
El origen de la palabra grafo es griego y su significado etimológico es
"trazar". Aparece con gran frecuencia como respuesta a problemas de la
vida cotidiana,algunos ejemplos podrían ser los siguientes:un gráfico de
una serie de tareas a realizar indicando su secuenciación (un
organigrama),grafos matemàticos que representan las relaciones
binarias, una red de carreteras, la red de enlaces ferroviarios o aéreos o
la red eléctrica de una ciudad. (Véase la figura). En cada caso,es
conveniente representar gráficamente el problema dibujando un grafo
como un conjunto de puntos (vértices) con líneas conectándolos (arcos).
a) Red de computadoras
b) Red de Vías áereas
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.2 Grafos
4.2.1 Introducción
Los grafos tienen un campo amplio de aplicaciones. En el estudio de los
mismos se han interesados los matemáticos hace muchos siglos atrás.
También son usados como herramientas para definir sistemas expertos
y otros modelos utilizados en el área de la inteligencia artificial.
Definicion
Un grafo es un conjunto de puntos o nodos, y un conjunto de
líneas tal que cada una de ellas une un punto a otro punto.
Un grafo G es un conjunto en el que hay definida una relación binaria,es
decir,G=(V,A) tal que V es un conjunto de objetos a los que
denominaremos vértices o nodos y
es una relación binaria a cuyos elementos denominaremos
arcos o aristas.
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.2 Grafos
4.2.1 Introducción
Dados ,puede ocurrir que:
en cuyo caso diremos que x e y están unidos mediante un arco,y
en cuyo caso diremos que no lo están.
Si las aristas tienen asociada una dirección (las aristas (x,y) y (y,x)
no son equivalentes) diremos que el grafo es dirigido, en otro caso
((x,y)=(y,x)) diremos que el grafo es no dirigido.
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.2 Grafos
4.2.1 Introducción
Por ejemplo, sea el grafo G de la figura
V(G1) = {a,b,c,d}
A(G1) = {(a,b),(a,d),(b,c),(b,d)}
b
d
a
c
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.2 Grafos
4.2.2 Representación
Un grafo puede ser representado de varias formas equivalentes que
pongan de manifiesto en mayor o menor medida determinadas
características. Las formas de representación mas comunes son:
- Simbólicamente: Como ya se ha descripto en el apartado anterior,
como un par (V,A), donde V es un conjunto de variables y A es un
conjunto de aristas entre pares de variables.
- Gráficamente: por medio de un diagrama formado por un conjunto de
nodos (uno para cada variable) y un conjunto de líneas (una para cada
arista del conjunto A).
- Numéricamente: utilizando cierto tipos de matrices
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.2 Grafos
4.2.2 Representación
Existe una clasificación de grafos según sus aristas. Por tanto, las
aristas de un grafo pueden ser dirigidas o no dirigidas, dependiendo de
si se considera o no, el orden de los nodos. En la práctica esta
distinción dependerá de la importancia del orden en que se relacionen
los objetos.
Por lo tanto y teniendo en cuenta lo mencionado anteriormente, se
considerarán dos tipos de grafos:
- Dirigidos: cuando todas las aristas son dirigidas.
- No Dirigidos: cuando todas las aristas no son dirigidas.
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.2 Grafos
4.2.2 Representación
Un ejemplo de grafo dirigido lo constituye la red de aguas de una
ciudad ya que cada tubería sólo admite que el agua la recorra en un
único sentido.Por el contrario,la red de carreteras de un país
representa en general un grafo no dirigido,puesto que una misma
carretera puede ser recorrida en ambos sentidos.
Entonces, en un grafo dirigido es importante el orden del par de nodos
que definen cada arista, mientras que en un grafo no dirigido, el orden
carece de importancia. La figura muestra gráficas de grafos dirigidos y
no dirigidos
A
B
C
B
C
A
G
D
E
E
F
D
F
G
a)
b)
J.T.P. Maria
Eugenia Valesani - Programacion
1 - Fa.Ce.Na.
4.2 Grafos
4.2.3 Definición y Terminología
Grafo Dirigido:
Es un par G = (V;A) donde V es un conjunto finito de elementos
llamados vertices y A V x V es un conjunto finito de pares ordenados
de vertices llamados aristas.
Si a = (u; v) es una arista de G, se dice que a entra o incide en v y que
a sale o emerge de u.
Grafo no Dirigido:
Es un par G = (A; V ) donde V es un conjunto finito de vertices y
es un conjunto de “pares no ordenados" de vertices.
Equivalentemente, G es un Grafo no Dirigido si G es un Grafo Dirigido
y
si
es un arco no dirigido, se dice que a une a u y v y que a incide en u y
en v.
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.2 Grafos
4.2.3 Definición y Terminología
Grado:
Para todo vertice v,
- Grado de Entrada es el numero de aristas que inciden en v;
- Grado de Salida es el numero de aristas que emergen de v;
- Grado es la suma de los grados de entrada y salida de v.
- Grado de un Grafo es el maximo grado de sus vertices.
Camino: es una secuencia de uno o mas arcos que conectan dos
nodos.
Camino Simple:
distintos.
es un camino en el que todos sus vertices son
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.2 Grafos
4.2.3 Definición y Terminología
Grafo conectado: cuando existe siempre un camino que une dos
vertices cualesquiera
Grafo desconectado: cuando existen vèrtices que no estan unidos por
un camino.
Grafo completo: es aquel en que cada vèrtice esta conectado con
todos y cada uno de los restantes nodos. Si existen n vèrtices, habrà
n(n-1) aristas en un grafo completo y dirigido, y n(n-1)/2 aristas en un
grafo no dirigido completo.
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.2 Grafos
4.2.4 Representacion numérica de grafos
Existen dos tecnicas estandar para presentar numericamente un grafo
G:
- matriz de adyacencia (mediante arreglos)
- lista de adyacencia (mediante punteros/listas enlazadas)
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.2 Grafos
4.2.4 Representacion numérica de grafos
Matriz de adyacencias
Sea G = (V,A) un grafo de n nodos, suponemos que los nodos V =
{u1,...,un} están ordenados y podemos representarlos por sus ordinales
{1,2,...,n}.
La representación de los arcos se hace con una matriz A de nxn
elementos aij definida:
aij
1 si hay arco (ui,uj)
0 si no hay arco (ui,uj)
La matriz A se denomina matriz de adyacencias del grafo G.
Mediante sencillas manipulaciones algebraicas de la matriz de adyacencia
se pueden obtener algunas características del grafo como, por ejemplo, el
número de caminos distintos que unen dos nodos, comprobar si el grafo es
conexo,
usar la diagonal principal de la matriz de adyacencia para
representar la existencia de un vértice, etc.J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.2 Grafos
4.2.4 Representacion numérica de grafos
Matriz de adyacencias
Cuando aij = 0, entonces no existe ninguna arista del nodo Xi al nodo Xj , o
que los nodos son adyacentes, de ahí el nombre de la matriz.
La matriz A contiene toda la información topológica del grafo asociado; por
tanto, esta matriz caracteriza al grafo. Notar que:
1) La matriz de adyacencias de un grafo no dirigido es simétrica
2) Dado que Vij no pertenece a V para todos los valores de i, los elementos
diagonales de A son nulos.
3) La matriz de adyacencia de un grafo no dirigido completo debe contener
un 1 en todos los elementos no diagonales.
La matriz de adyacencia permite comprobar si existe algún camino entre
cada par de nodos. También puede calcularse la longitud de todos los
caminos que unan cada par de nodos. Para comprobar esto existen
teoremas que no son objetos de nuestro estudio.
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.2 Grafos
4.2.4 Representacion numérica de grafos
Matriz de adyacencias
Graficamente
x1
x1 x2 x3 x4
x1
x2
x3
X
x2 X
X
X
x3
X
x4 X
X
X
x4
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
A=
0
1
0
1
1
0
1
1
0
1
0
0
1
1
0
0
4.2 Grafos
4.2.4 Representacion numérica de grafos
Matriz de adyacencias
Ejemplo
1
2
3
5
0
1
0
0
1
1
0
1
1
1
4
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
0
1
0
1
0
0
1
1
0
1
1
1
0
1
0
4.2 Grafos
4.2.4 Representacion numérica de grafos
Lista de adyacencias
Este mètodo es util de usarlo cuando un grafo tiene muchos vertices y
pocas aristas.
En esta representación se utiliza una lista enlazada por cada vertice v
del grafo que tenga vertices adyacentes desde el.
El grafo completo incluye dos partes:
- un directorio
- un conjunto de listas enlazadas.
Hay una entrada en el directorio por cada nodo del grafo.
➔
La entrada al directorio del nodo i apunta a una lista enlazada que
representa los nodos que son conectados al nodo i.
➔
Cada registro de la lista enlazada tiene dos campos:
- un identificador de nodo
- un enlace al siguiente elemento de la lista
➔
La lista enlazada representa arcos.
➔
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
4.2 Grafos
4.2.4 Representacion numérica de grafos
Lista de adyacencias
Ejemplo
Grafo Dirigido
1
4
2
5
Lista de Adyacencia
3
6
Matriz de Adyacencia
4
1
2
2
5
3
5
4
2
-
5
4
-
6
6
-
-
-
6
-
J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
0
0
0
1
0
0
1