UNIDAD 4.-Estructuras no lineales.
Árboles.
Un conjunto finito
de elementos no vacío en el cual un elemento se denomina raíz y los restantes
se dividen en subconjuntos separados, cada uno de los cuales es por sí mismo un
árbol. Cada elemento en un árbol se denomina nodo del árbol. Su estructura es
denominada como de bifurcación, también conocida como estructura
multi-enlazada.
En un árbol no hay
lazos, lo que indica que no hay pasos que comiencen en un vértice y puedan
volver al mismo, un árbol puede tener un vértice o nodo llamado raíz, el cual
se indica como vértice principal. Este nodo raíz no puede ser hijo de otro
nodo.
Representación en memoria de árboles.
Para
representar un árbol binario puede hacerse de forma tradicional, por arreglos o
Struct. En la tradicional se emplean dos punteros de tipo variables dinámicas o
listas; por la otra se emplea el uso de arreglos. La manera dinámica es la más
empleada.
Strutc;
es una manera de registro utilizado en C que define una lista de variables, que
puede ser utilizada en árboles binarios.
Los
arboles binarios se pueden expresar mediante registros divididos en por lo
menos tres campos, el primero y el último contienen la información de los
arboles anterior y siguiente del árbol en cuestión, y un campo más para
almacenar el valor.
Árboles generales.
Se utiliza la recursión para definir un árbol
porque representa la forma más apropiada y porque además es una característica
primordial de los mismos. Dentro de los ejemplos de la aplicación de árboles,
podemos citar:
-Los sistemas de archivos ( file system ) de los sistemas
operativos, compuestos por jerarquías de directorios y archivos.
-La jerarquía
de clases en los lenguajes orientados a objetos.
-La jerarquía de países,
provincias, departamentos y municipios que organiza al poder político de una
república.
Árboles binarios.
Al
tener un árbol ordenado, este se identifica, porque el nodo padre es mayor que
las claves del subárbol izquierdo, además de ser menor que todas las claves del
subárbol derecho.
El
árbol binario es empleado para reconocer un conjunto de registros que tienen un
identificador o clave única.
Tipos
esenciales de árboles binarios.
-Árbol
binario distinto.
.png)
Aquí, dos árboles tienen diferentes estructuras, por lo
tanto se les considera árboles distintos.
-Árboles binarios similares.
.png)
En este árbol las estructuras son
iguales, pero los datos contenidos en el son distintos, entonces se dice que el
árbol es distinto.
-Árboles binarios equivalentes.
.png)
Además
de ser de tipo similar, si un árbol contiene los mismos datos, el árbol es
equivalente.
-Árboles
binarios completos.
.png)
Árbol
en el que sus diferentes niveles tienen dos hijos, un subárbol izquierdo y un
subárbol derecho, a excepción del último nodo.
Recorrido
en un árbol binario.
Maneras
de recorrer un árbol y su secuencia.
Inorden
-Recorrido
del subárbol izquierdo en inorden.
.png)
-Buscar
la raíz.
-Recorrido
del subárbol derecho en inorden.
Preorden.
-Examinar
la raíz.
-Recorrido
del subárbol izquierdo en preorden.
-Recorrido
del subárbol derecho en preorden.
Postorden.
-Recorrido
del subárbol izquierdo en postorden.
-Recorrido
del subárbol derecho en postorden.
-Examinar
la raíz.
El
recorrido para este árbol es el siguiente:
Inorden:
GDBHEIACJKF
Preorden:
ABDGEHICFJK
Postorden:
GDHIEBKJFCA
Otro
tipo de árboles, son los enhebrados:
Se
denomina así porque contiene hebras a la derecha o a la izquierda.
Estos
árboles se utilizan para el mejor aprovechamiento de la memoria.
.png)
Árbol
enhebrado a la derecha.
Balanceo
de árboles binarios.
Terminología.
-Un
árbol esta balanceado, si para cada uno de sus nodos, las alturas de sus dos
subárboles difieren a lo más en 1.
-Los
arboles pueden estar balanceados, por altura o por peso.
-Balanceado
por altura: todos los hijos o nodos hoja, se intentan mantener a la misma
distancia de la raíz.
-Balanceado
por peso: los nodos más visitados o utilizados se mantienen a poca distancia de
la raíz
Grafos
Definición
Un
grafo es un conjunto de nodos (o vértices) unidos por un conjunto de arcos (o
aristas) que permiten representar relaciones binarias entre los elementos de un
conjunto.
Representación:
Un
conjunto de nodos {A, B, C, D, E, F, G, H} y su conjunto de arcos {(A, B), (A,
D), (A, C), (C, D), (C, F), (E, G), (A, A)}, para el siguiente grafo.
Terminología
-
Al número de nodos del grafo se le llama orden del grafo.
-
Un grafo nulo es un grafo de orden cero (0).
-
Dos nodos son adyacentes si hay un arco que los une.
-
Camino es una secuencia de uno o más arcos que conectan dos nodos.
-
El camino de un nodo así mismo se llama ciclo.
-
Un grafo es conexo si existe un camino simple entre cualesquiera dos de sus
nodos.
-
Un grafo sin ciclos es un árbol.
-
Un grafo es completo cuando cada nodo está conectado con todos y cada uno de
los nodos restantes.
-
El grafo se denomina conectado cuando existe siempre un camino que une dos
nodos cualesquiera y desconectado en su caso contrario.
Ejemplos;
1
Una línea aérea que realiza vuelos entre las ciudades conectadas por líneas
2
Un comerciante de frutas tiene que visitar n poblados, conectados entre si por
carreteras, su interés será minimizar la distancia recorrida (o el tiempo, si
puede haber ciertos problemas).
Entonces
el grafo tendrá como vértices las ciudades, como aristas las carreteras y la
valuación será la distancia entre ellas.
Tipos de grafos.
Los
grafos se pueden clasificar en dos grupos, dirigidos y no dirigidos. El grafo
dirigido (o dígrafo) se caracteriza porque cada arista tiene una dirección asignada,
es decir, que cada arista está asociada a un par ordenado de vértices, de forma
que (v1, v2) ≠ (v2, v1) representen dos arcos diferentes. En un grafo no
dirigido el par de vértices que representa un arco no está ordenado, por lo
tanto los pares (v1, v2) = (v2, v1) representan el mismo arco.
De los principales tipos de grafos mencionamos los siguientes:
Grafo
regular: grafo con el mismo grado en todos los vértices. Si ese grado se hace
llamar k lo llamaremos K-regular.
grafo
3-regular y grafo no regular.
Grafo bipartito: es aquel cuyos vértices pueden formarse
dos conjuntos distintos disyuntos de modo que no haya adyacencias entre
vértices pertenecientes al mismo conjunto.
Grafo bipartito regular: se puede denotar como Km, n
donde m, n es el grado de cada conjunto disjunto de vértices. K2,
5
Grafo
completo: grafo con una arista entre cada par de vértices; un grafo completo
con n vértices se denota Kn.
K5
Grafo
nulo: en este grafo los vértices que lo componen no están conectados, esto es,
que son vértices aislados.
Grafos
Isomorfos: (aquí se hace una comparación de dos grafos) se dice entonces, que
dos grafos son isomorfos cuando existe una correspondencia uno a uno
(biunívoca), entre sus vértices de tal forma que dos de estos quedan unidos por
una arista en común.
(Referencia
con la matriz de adyacencia para conocer si existe Isomorfismo en los dos
grafos)*
Grafos
platónicos: grafos formados por los vértices y aristas de los cinco sólidos
regulares (sólidos platónicos) que son; el tetraedro, el cubo, el octaedro, el
dodecaedro y el icosaedro.
Grafos
Eulerianos: este, es un camino que contiene a todas las aristas del grafo,
apareciendo una vez. Consiste en recorrer todas las aristas del grafo
sin repetir ninguna.
Grafos
Hamiltonianos: este camino recorre todos los vértices de un grafo sin
pasar dos veces por el mismo vértice.
Representación
de grafos en memoria.
-Por
medio de matriz de incidencia, que corresponde a 0 y 1.
.jpg)
-Por
matriz de adyacencia.
Aquí
las filas, son los nodos y las columnas, son los nodos destino.
Existen
grafos con peso o sin peso
Los
grafos con peso, no tienen valor, solo unión.
Los
grafos sin peso, tienen aristas con valor.
.png)
-Lista
de adyacencia
Se
asocia cada nodo del grafo una lista que contenga todos aquellos nodos que sean
adyacentes a el.
.jpg)
Clases
para la implementación de grafos.
Las
operaciones dentro de los grafos, son las siguientes:
Dentro
de la matriz de adyacencia;
-Creación
Public
Grafo BM (bolean d) {
Max
vértices = num aristas = 0; (considerado null)
Dirigido
= d;
-Inserción
(de aristas)
Para
una matriz, siendo simétrica, se intercambian las filas por las columnas, en
este caso;
i = filas
j = columnas
i j j i
123 147
456 258
789 369
Public void insert arista {
int i;
int j;
Matriz Adya [i] [j] = true
If (!
dirigido);
Matriz
[j] [i] = Matriz Adya [i] [j]
}
-Búsqueda
En
la búsqueda se realiza alguno de estos procesos, únicamente haciendo el
reconocimiento de la variable que se desea buscar.
-Eliminación.
Public
eliminar arista {
int
i;
int
j;
matriz
adya [i] [j] = falso
if
(! dirigido);
matriz
adya [j] [i] = falso
}Operaciones,
en la lista de adyacencia
-Insertar aristas
Public void inseratr arista {
int i;
int j;
Lista
adya [i] insertar [j];
If
(dirigido)
Lista
adya [j] insertar [i];
-Eliminar
Public void eliminar arista {
int i;
int j;
lista
adya [i] [j];
lista
[j] [i];
