Estructura de datos avanzados

Carlos Alberto Torres Sastoque

Fecha de actualización: 30 de agosto de 2019

.
 Introducción

El tercer y último módulo del curso de estructuras de datos avanzados se enfoca

en algunos tipos de estructuras que son útiles para simplificar ciertas operaciones
que tienen que ver con la programación de datos; entre otras, pilas, colas, árboles
y grafos.

En el caso de las ‘Pilas y Colas’ se abordan desde el concepto básico y su función

en aplicaciones que se empelan con frecuencia. Los ‘Árboles’ desde su estructura
y desarrollo de nodos internos y externos. Por último en los ‘Grafos’
se conceptualiza desde la Teoría de Grafos y se analiza su representación y
matriz.

Por medio de la estructura de datos dinámica se logra una mayor efectividad en el

manejo de la información, durante el capítulo se trabajaran estructuras lineales y
no lineales mostrando sus ventajas y característica en el manejo de cada una de
ellas.

Se muestra las ventajas que tienen en el manejo de la información y las

cualidades que tienen para hacer una utilización de la programación más efectiva
ahorrando y optimizando recursos.

Se muestra de manera sencilla como se utilizan los conceptos de linealidad,

jerarquía y dependencia de los elementos de la información para poder darle un
manejo organizado y apropiado para la mejor utilización de esta en el medio
informático.

Con esta última parte del módulo se aspira que los estudiosos encuentren en las
estructuras, medios y herramientas útiles para la resolución de problemas, incluso
mediante la modelación de trayectos.
 Estructura temática

5.Estructuras de datos avanzado

5.1Pilas y colas.
5.1.1Pilas
5.1.2Colas
6.Arboles
6.1Conceptos básicos
6.2.Arboles binarios
6.2.1.Recorrido en arboles binarios
6.2.2. Arboles binarios de busqueda
7.Grafos
7.1 Grafos Dirigidos
7.2 Grafos no Dirigidos
7.3 Camino de un Grafo
7.4 Ciclo de un Grafo
7.5 Grafos Conexos
7.6 Grafos Completos
7.7 Grafos Ponderados
7.8 Densidad de un Grafo
7.9 Grafos Simples
7.10 Multigrafos
7.11 Matriz de Adyacencia
7.12 Lista de Adyacencia
Glosario
Bibliografía
 Ideograma

Figura 1. Ideograma Modulo 3.

 5. Estructuras de datos avanzadas

5.1 Pilas y Colas:

Este tipo de estructuras, no son estructuras de datos fundamentales por lo tanto

no aparecen definidas como tal en los lenguajes de programación. Estas
estructuras se crean a partir de arreglos y listas.

5.1.1 Pilas.

Este tipo de estructura es muy similar a la forma en que se apilan unas latas en un
supermercado o unos platos en un restaurante donde al retirar un elemento, se
obtiene el último en haberse introducido en dicha estructura.

Siendo así, entonces una pila es un conjunto de elementos, los cuales solo se
pueden acceder (insertar o eliminar) por un solo extremo, siendo esta su
característica fundamental, el extremo por el que se accede a los elementos de la
pila se denomina TOPE. Cuando se accede a un elemento en la pila el primer
elemento al que accederemos será el último en haber ingresado por esta razón se
dice que esta estructura es de tipo LIFO por sus siglas en inglés (last in
firstout/último en entrar primero en salir).

Al utilizar arreglos para la implementación de una pila se debe reservar un espacio

en la memoria con anticipación pues si la pila se encuentra llena y se intenta
insertar un elemento más, se produce un error conocido como desbordamiento
(overflow).

Para trabajar una pila, los elementos que se insertan no son los que se mueven
hacia arriba o abajo lo que ocurre en realidad es que existen dos punteros que
trabajan, uno es el que indica la posición tope o el elemento disponible en la cima
(puntero de pila) y el otro es el que se mantiene en la base de la pila y siempre
mantiene el mismo valor mientras la pila exista (base de pila).
8  Puntero de pila
4
1
3  Base de pila

 OPERACIONES:

En las pilas se realizan básicamente las operaciones de insertar o añadir

elemento PUSH y la de eliminar o quitar elementos POP, operaciones que
como ya se ha mencionado se realizan siempre en el tope de la pila. La
operación push se puede aplicar a cualquier pila siempre que su tamaño de
memoria lo permita cabe mencionar que la operación pop no es aplicable a
una pila vacía ya que en esta pila no habría elementos para eliminar, lo que
nos lleva a otra operación existente en las pilas que es la operación EMPTY
y cuya función es permitirnos saber si la pila está o no vacía por medio de
una función booleana que retornara TRUE si la pila está vacía y FALSE en
caso contrario.

Para observar la estructura de estas funciones tendremos en cuenta los

siguientes parámetros:
p = Tope puntero de la pila
LONGMAX longitud máxima de la pila
S(i) elemento i-esimo de la pila S
x elemento a insertar o eliminar
VACIA función booleana (pila vacía)

 PUSH (insertar o añadir): en este caso debemos insertar el

elemento x en la pila S.

inicio
si p=LONGMAX
entonces
escribir ´pila llena`
sino
pp+1
S(p) x
fin_si
fin
  POP (eliminar o quitar): en este caso se quitara el elemento del
tope de la pila y se pondrá en x.

inicio
si p=0
entonces
escribir `pila vacia´
sino
x S(p)
pp-1
fin_si
fin

 FUNCION PILA VACIA:

inicio
si p = 0
entonces
VACIA  verdadero
sino
VACIA  falso
fin_si
fin

Existe otra operación llamada stacktop, esta operación nos permite

conocer cuál es el elemento superior de la pila, o sea el elemento que se
encuentra en el TOPE. Aunque en realidad esta operación o es nueva pues
está compuesta de las operaciones POP y PUSH.

O sea: i = stacktop (s); es igual a decir i = pop (s);

push(s,i);

Al igual que en la operación POP para ejecutar STACKTOP se debe

realizar antes la operación de pila vacía pues estas funciones no aplican
para pilas vacías pues se genera subdesbordamiento.

Las pilas, son estructuras de datos muy usadas en la solución de varios

tipos de problemas, entre los más importantes encontramos:

 Llamadas a subprogramas. Cuando se tiene un programa que utiliza

otros subprogramas, se utilizan pilas ya que estas permiten guardar
las direcciones de dichos programas o subprogramas para regresar
posteriormente y seguir ejecutándose a partir de donde se llamó al
subprograma, también permite guardar el estado de las variables en
el momento en que se hace la llamada para recuperarlas al regresar
del subprograma.
  Recursividad. Se utilizan las pilas para proceso recursivos.

 Tratamiento de expresiones aritméticas. En computación son muy

útiles, ya que permiten con facilidad manejar las expresiones con
notación postfija o prefija ya que no son necesarios los paréntesis
para indicar el orden de las operaciones ya que esta previamente
establecido por el orden de los operadores con respecto a los
operandos.

 Ordenación. son muy usadas en los métodos de ordenación rápida.

5.1.2. Colas.

Este tipo de estructura de datos tiene similitud con las colas que se realizan en la
vida diaria en nuestras diferentes actividades, como la cola que se realiza para ser
atendido en un banco, o usar un teléfono público, donde no es permitido colarse y
las personas van siendo atendidas en su orden de llegada. Los elementos de una
cola son insertados por un extremo, la parte de atrás y retirados por el otro
extremo, el extremo de adelante.

Por su comportamiento, las colas son estructuras de tipo FIFO por sus siglas en
ingles first in-firstout (primero en entrar-primero en salir).

Para la implementación de las colas se usa dos punteros FRENTE (f =front), que
es el extremo por el cual se retiraran los elementos y FINAL (r= rear) que nos
indicara el extremo por el cual se insertaran los elementos a la cola.

1 4 8 9 3
r (rear) f (front)

1 4 8 9
r (rear) f (front)
La diferencia entre las pilas y las colas radica en el extremo en el que se realizan
las inserciones a cada estructura, ya que en las colas se realiza la inserción en la
parte final de la lista y no al principio como ocurre en las pilas.

 OPERACIONES:

En las colas se utilizan tres operaciones básicas que son:

 insert(C,x)que es el método de insertar x en la cola C.

inicio
si (r =MAX)
entonces
escribir `cola llena´
sino
r x
r r+1
fin_sino
fin_si

 remove (C) borra el elemento que se encuentra en la posición frontal de la

cola C. (esta operación solo puede ejecutarse cuando la cola no está vacía,
en caso que se intente ejecutar sobre una cola vacía se producirá un
subdesbordamiento).

inicio
si (cola_vacia(C))
entonces
escribir `cola vacia´
sino
ff+1
fin_sino
fin_si
  empty (C) función que retorna falso o verdadero dependiendo si la cola
está vacía o no.
inicio
si(f = r)
entonces
escribir`TRUE´
sino
escribir`FALSE´
fin_si
fin

Este tipo de estructuras las podemos ver en la informática en el caso de un

periférico externo del computador como la impresora, donde los documentos q se
envían a imprimir se encuentran en cola de impresión y son impresos en el orden
en que han llagando.

Existen diferentes tipos de colas como:

 Cola circular: o también llamada de anillo, es un estructura en la que todos

los elementos tienen un sucesor y un predecesor, se encuentran de forma
circular, las operaciones que se realizan aquí (consulta, añadir y eliminar)
solo se pueden hacer por la cabeza del círculo, que es una posición
conocida, aquí existen dos operaciones de rotación, una hacia cada lado
del anillo y allí la cabeza del anillo pasa a ser sucesor o predecesor de la
cabeza actual según el lado de la rotación.

Figura 2. Cola Circular.

 Cola de prioridad: Así como en la vida diaria por ejemplo en las colas de
los bancos se atiende clientes con ciertas preferencias o prioridades en la
informática también se realiza así, en esta estructura se asignan valores de
prioridad a los datos, este valor es un número entero y está asociado a que
a menor valor habrá mayor prioridad. En este tipo de estructuras, los datos
se procesan según la prioridad indicada para cada elemento, en el caso de
que haya elementos con la misma prioridad, serán procesados según la
posición q ocupen en la estructura.

 Bicolas: Esta es una cola bidimensional en la que se puede añadir eliminar

elementos por cualquier extremo, pero no por la mitad, a diferencia de una
cola simple, en la bicolas hay dos métodos para leer(uno para leer por el
frente y otro por atrás) y dos métodos para escribir (uno para escribir por el
frente y otro por atrás).

Hay dos tipos de bicolas:

 Doble cola de entrada restringida: en esta estructura se pueden

añadir elementos por un solo extremo de la estructura mientras que
para eliminarlos si se puede por cualquier extremo.

 Doble cola de salida restringida: en esta estructura se pueden

eliminar elementos por un solo extremo de la estructura mientras que
para insertarlos si se puede por cualquier extremo.
 En estas estructuras, se opera agregando el elemento por cualquier
extremo, al inicio o al final, los elementos que se encuentran en la primer o
última posición se pueden eliminar. Por esta razón no existe un método
para la doble cola, aunque se puede usar los métodos de tipo FIFO o LIFO.

6. Árboles.

Los árboles, son estructuras de datos no lineales, entendiéndose por no lineal,

como estructuras que pueden tener no solo un sucesor y un predecesor sino
varios enlaces a sucesores o predecesores, para el caso de los árboles, cada
elemento solo puede estar enlazado a un predecesor y sus sucesores. Entonces
la definición de árbol la tomaremos como la estructura no lineal jerárquica en la
que a cada elemento le corresponde un único antecesor y sus sucesores, estos
elementos se conocen como nodos y están conectados entre sí por medio de
ramas o enlaces.

El símil a los árboles, son los árboles genealógicos, estructuras en las que hay
jerarquía y sus elementos están unidos a otros por debajo.

6.1 Conceptos básicos.

Para entender el funcionamiento y la descripción de los arboles es necesario

conocer cuáles son sus elementos y conceptos básicos:

 NODO: ítem o elementos del árbol, pueden ser :

o Nodo raíz: Nodo superior de la estructura, no tiene antecesor.

o Nodo terminal u hoja: nodo que no tiene descendientes, no tiene
ningún subárbol.
o Nodo interior: nodos que no son hojas, pueden tener uno o más
subárboles.
o Nodo descendiente o hijo: el descendiente de un nodo dado, cada
subárbol de un nodo.
o Ascendiente o padre: nodo de jerarquía superior o predecesor de un
nodo dado.
o Nodos hermanos: nodos de un mismo padre.
  ENLACE: conexión que hay entre los nodos del árbol.

 CAMINO: enlace entre dos nodos. No existe un camino entre todos los
nodos de un árbol.

 RAMA: camino que termina en una hoja.

 GRADO DE UN NODO: indica el número de subárboles de un nodo

determinado, el grado de un árbol es el máximo nodo de todos los nodos de
este.

 NIVEL DE UN NODO: o longitud de camino, son la cantidad de enlaces

existentes entre el nodo raíz y un nodo dado.
 ALTURA DE UN ARBOL: o profundidad, es la cantidad máxima de nodos
de una rama, también dado por el nivel más alto más uno.

 PESO DE UN ARBOL: cantidad de nodos hoja que posee el árbol.

En la siguiente figura se observaran las definiciones anteriores de forma gráfica:

Figura 3. Definiciones.
 Nodo raíz.

 Los nodos de nivel 1, son nodos hermanos.

 Hoja o nodo terminal.

 Grado de la raíz :2

 Altura del árbol: 4

 Peso del árbol: 6

Longitud de camino: También es importante conocer que la longitud de

camino es la cantidad de enlaces que se deben recorrer para llegar a
determinado nodo desde la raíz del árbol. Por definición la longitud de camino
de la raíz es 1, sus hijos es de 2 y así sucesivamente.

 Longitud de camino interno: es la suma de las longitudes de

camino de todos los nodos de un árbol y se calcula por medio de
la siguiente fórmula:

h
LC I = ∑ni*i
I=0

Dónde: i= nivel de árbol

H= altura
Ni= Numero de nodos en nivel i

La longitud de camino interno para nuestro árbol de la figura 1 seria:

LCI=1*1 + 2*2 + 5*3 +4*4 = 36 donde h= 4

 La media de la longitud de camino interno (LCIM) es el número

de enlaces promedio que se deben recorrer para llegar a un nodo
desde su raíz y se calcula dividiendo la LCI entre el número de
nodos del árbol (n).
Para nuestro árbol seria:

 Longitud de camino externo: para lograr esta definición es

necesario conocer los siguientes conceptos:

Árbol extendido: es un árbol en el que el número de hijos de

cada nodo es igual al grado del mismo. Si no cumple esta
condición se pueden agregar nodos especiales para lograr
satisfacer esta condición.

Nodos especiales: son nodos cuya función es reemplazar los

enlaces vacíos, no tienen descendientes y se representan en
forma de cuadrado.

Completando con nodos especiales el árbol extendido de nuestro ejemplo

quedaría de la siguiente forma:

Figura 4. Ejemplo.

Ahora si la definición de longitud camino externo para este seria, la suma de

las longitudes de camino de todos los nodos especiales del árbol, que se
calcularía por medio de la siguiente fórmula:
 donde: i = nivel del árbol
h = altura del árbol
nei = número de nodos especiales en el nivel i.

Para nuestro árbol seria:

LCE = 1*2 + 1*3 +11*4 + 12*5 = 109

Ahora, la media de la longitud de camino externo se calcula dividiendo la LCE

sobre el número de nodos especiales del árbol y esta longitud, nos indica la
cantidad promedio de enlaces que debemos recorrer para llegar desde la raíz a
cualquier nodo especial del árbol y está dada por:

LCEM = LCE/ne

Para nuestro árbol seria:

LCEM = 109/25 = 4.36

6.2 ARBOLES BINARIOS:

Este es un tipo de árbol muy común en computación, este árbol, tiene la

característica de ser un árbol de grado 2, ósea cada uno de sus nodos puede
tener máximo dos hijos, solamente uno o ninguno. Y estos hijos se denominaran
como subárbol izquierdo o subárbol derecho.

Un árbol binario se representara con nodos compuestos del campo de la

información y dos punteros que indicaran la posición de sus hijos, los punteros
pueden ser nulos si de dicho nodo no se desprenden hijos. Estos tres campos se
conocerán como:

- Clave: que es el campo de datos, donde contiene la información.

- Puntero izquierdo.
- Puntero derecho.

Puntero Clave Puntero

izqdo. dcho.
(información)
6.2.1 Recorrido en Arboles Binarios.

El recorrido de un árbol, es la visita sistemática que se hace a los nodos de este,

de tal manera que todos los nodos sean visitados una sola vez, esta visita puede
ser a todos los nodos (recorrido completo) por ejemplo para saber la cantidad de
nodos del árbol o parcial por ejemplo en el caso de la búsqueda de un valor clave.

Existen tres formas recursivas en las que se puede realizar el recorrido de un árbol
y estas son:

- Preorden: este tipo de recorrido es el más utilizado pues conserva el

orden
Jerárquico del árbol. En este tipo de recorrido se realizan los siguientes
pasos:

o Visitar nodo raíz.

o Recorrer subárbol izquierdo.
o Recorrer subárbol derecho.

- Inorden: este recorrido es útil para procesos en los que es necesario

recorrer el árbol de acuerdo al orden físico de los nodos. En este tipo de
recorrido se realizan los siguientes pasos:

o Recorrer subárbol izquierdo.

o Visitar nodo raíz.
o Recorrer subárbol derecho.

- Postorden: este es un recorrido poco utilizado, sirve para liberar

memoria o cuando la información de los niveles profundos afecta la
información buscada. En este tipo de recorrido se realizan los siguientes
pasos:

o Recorrer subárbol izquierdo.

o Recorrer subárbol derecho.
o Visitar nodo raíz.
 Figura 5. Recorrido de un Árbol.

A continuación observaremos el resultado de recorrer este árbol con las diferentes

formas de recorrerlo.

PREORDEN M F C A E H P R Q Z
INORDEN A C E F H M P Q R Z
POSTORDEN A E C H F Q Z R P M

Para la implementación de estos recorridos se utilizan funciones específicas

desarrolladas para dichas tareas.

Preorden:

Voidpreorden (arbol*a)
{si (a!=NULL)
{visitar (a);
preorden(izq);
preorden(der);
}
}
Inorden:

Voidinorden (arbol*a)
{si (a!=NULL)
{inorden(izq);
visitar (a);
inorden(der);
 }
}
Postorden:

Voidpostorden (arbol*a)
{si (a!=NULL)
{postorden(izq);
postorden(der);
visitar (a);
}
}

6.2.2 Arboles Binarios de búsqueda.

Este es un tipo especial de árbol, cuya característica principal es la forma en que

se encuentran e insertan ordenadamente los datos en este, facilitando
notablemente la búsqueda de elementos dentro de este.

Los arboles binarios de búsqueda contienen elementos que pueden ser ordenados
entre ellos pueden ser enteros, reales, caracteres, etc. De modo que siempre el
primer elemento será el nodo del árbol y el segundo se ubicara a la izquierda si es
menor o a la derecha si es mayor y así sucesivamente con todos los elemento que
se van insertando, de modo que en cualquier nodo los elementos del subárbol
izquierdo son menores o iguales al del nodo en cuestión y hacia la derecha serán
mayores.

Una característica importante de estos árboles, es que al momento de realizar un

recorrido inorden se obtendrán los elementos debidamente ordenados.

Para entender un poco más el concepto de árboles binarios de búsqueda

crearemos nuestro árbol a partir de los siguientes elementos: 5 3 7 2 4 8.

5 por ser el primer elemento será la raíz.

3 por ser menor que 5 ira ubicado a la izquierda.

7por ser mayor que 5 ira ubicado a la derecha.

2 por ser menor que 5 ira a la izquierda

2 por ser menor que 3 ira a su izquierda.

4 por ser menor que 5 ira a su izquierda

4por mayor que 3 iraa la derecha.
8 por ser mayor que 5 y mayor que 7 ira a su derecha

Este tipo de árboles son muy eficientes para la búsqueda de datos en sus nodos.
Veremos ahora las operaciones de los arboles binarios de búsqueda.

Búsqueda de un elemento: Es una búsqueda en la que cada comparación

fracciona en rango de búsqueda, ya que cada comparación elimina uno de los
subárboles que no contiene el valor, ya sea el subárbol mayor o el subárbol
menor.

Este algoritmo compara el valor buscado con la raíz del árbol, si no es el valor
buscado, pasa al árbol mayor o menor según sea el caso y así repite la búsqueda
de forma recursiva.

Así, en nuestro ejemplo anterior, si buscamos el elemento”4”, se visitaran los

nodos 5-3-4, ahora si buscáramos el elemento “6” el recorrido se haría hasta llegar
al nodo 7 y no encontrar el elemento buscado.

Insertar un elemento. Para insertar un elemento, primero se debe verificar que

dicho elemento no esté contenido ya en el árbol. Si el elemento no existe, la
inserción se realiza en una forma similar al proceso de búsqueda puesto que se
inserta en la posición que este tendría como si ya se encontrara en el árbol, se
desciende en el árbol por izquierda o derecha según el valor del elemento a
insertar hasta cuando se llega a un nodo en el que no se puede continuar y el
nuevo elemento se inserta a la izquierda o derecha de este nodo según
corresponda.

Para el caso de nuestro árbol del ejemplo anterior insertaremos los números 1 - 6
- 9 respectivamente y será de la siguiente forma.
 Figura 6. Insertar un elemento.

Eliminar un elemento. Para eliminar un elemento se debe conservar el orden de

los elementos del árbol para esto se encontraran tres posibles casos según el tipo
de no que se desea eliminar:

 Si el nodo es un nodo hoja, simplemente se elimina el nodo.

De nuestro árbol del ejemplo anterior, eliminaremos el nodo 9.

Figura 7. Eliminar un Nodo.

 Si el elemento no tiene más que un descendiente, solo se

sustituye el nodo a eliminar por este descendiente. Para nuestro
mismo ejemplo, eliminaremos el 8.

Figura 8. Eliminación de un Nodo.

  Si el elemento a eliminar tiene dos descendientes, se debe tener
más cuidado, pues el simple intercambio por cualquiera de sus
hijos puede causar que se pierda la estructura de árbol binario.
De esta manera, el nodo que se elimine se debe reemplazar por
el nodo que se encuentre más a la derecha o izquierda de tal
manera que se conserve su ordenación.

Para llevar a cabo esta operación, es necesario conocer del nodo a

eliminar:

o Posición en el árbol.
o Dirección de su padre.
o Dirección de su ascendencia, saber si es derecho o
izquierdo.

Para nuestro árbol, eliminaremos el nodo 7.

Figura 9. Eliminación de un Nodo.

7. GRAFOS

La teoría de grafos también conocida como la teoría de las gráficas es un amplio

campo de estudio de las matemáticas y de las ciencias de la computación, la cual
se encarga de estudiar las propiedades de los grafos. Los grafos son estructuras
que se componen de dos partes, el conjunto de vértices, nodos o puntos, y el
conjunto de aristas, líneas o lados los cuales pueden ser orientados o no.

El origen de la palabra grafo proviene de la

lengua griego y su significado etimológico
es “trazar”.

En general, un grafo es una forma de representar relaciones que existen entre

pares de objetos. Así un grafo es un conjunto de objetos, llamados vértices, y
relaciones entre objetos que establecen una relación entre pares de vértices,
representadas por aristas.

Nodos = vértices

Aritas =
Conexiones entre
los nodos
 Los grafos son de gran utilidad en la vida cotidiana
dado que se usan para representar una serie de
tareas a realizar e indicando su secuencia o también
un organigrama, los grafos matemáticos que
representan las relaciones binarias, una red de
carreteras, la red de eléctrica de una ciudad o las
rutas de enlaces aéreos.

En cada ejemplo es conveniente representar los problemas de forma gráfica

dibujando un grafo como un conjunto de puntos o vértices con líneas
conectándolos (arcos).

Figura 10. Ejemplo de Grafos. Figura 11. Ejemplo de

Grafos.

Componentes de un grafo:
  Vértices: Los vértices son aquellos objetos de un grafo que
contienen información, su representación suele ser
circunferencias o puntos los cuales dentro de los mismos llevan el
contenido.

 Aristas: Son las conexiones o uniones que se usan entre los

vértices, se representan por medio de líneas, se suele añadir
junto a la línea el nombre de los vértices origen y destino, además
el peso de la arista en algún tipo de unidad.

Los vértices de un grafo pueden usarse para representar objetos. Los arcos se
utilizan para representar relaciones entre estos objetos, no hay restricciones para
forma un grafo, además puede haber varias aristas entre dos vértices, el vértice de
partida o de inicio y el de llegada o de final puede ser el mismo. Las aristas
pueden o no llevar flechas.

Las aplicaciones más importantes de los grafos son las siguientes:

 Rutas entre ciudades.

 Determinar tiempos máximos y mínimos en un proceso.
 Representación de circuitos electrónicos analógicos y digitales.
 Representación de red de computadores.
 Flujo y control en un programa.

Definición de grafo:

Un grafo G = (V,A)

Donde V, el conjunto de vértices o nodos, que representan los

objetos.
A, el conjunto de arcos, que representan las relaciones.

V = {1, 4, 5, 7, 9}
 A = {(1,4), (5,1), (7,9), (7,5), (4,9), (4,1), (1,5), (9,7), (5,7), (9,4)}

Figura 12. Grafo.

Tipos de Grafos:

Los grafos son estructuras de datos no lineales que tiene una naturaleza dinámica.
Su estudio puede dividirse en dos grandes bloques:
7.1 GRAFOS DIRIGIDOS

También conocidos como dígrafo. En los grafos dirigidos los arcos tienen una
dirección asociada, el primer elemento del arco es el origen y el segundo es
considerado el destino. Es aquel cuyas aristas son dirigidas, estos grafos suelen
representar relaciones asimétricas como por ejemplo: relaciones de herencia, los
vuelos entre ciudades, etc.

Un grafo dirigido (gd) es un par G = (V, A)

V es el conjunto finito de vértices (o nodos)

A es el conjunto de aristas (o arcos) dirigidos

Arista: par ordenado de vértices (u, v): u --> v

Ejemplo:

V = {Ciudad1, Ciudad2, Ciudad3, Ciudad4, Ciudad5} |V| = 5

A= {(Ciudad2, Ciudad3), (Ciudad3, Ciudad1), (Ciudad3, Ciudad4),

(Ciudad3,Ciudad5), (Ciudad1, Ciudad3), (Ciudad1, Ciudad5)} |A| = 6
 Figura 13. Grafo Dirigido.

Cada arista del grafo dirigido incluye una fleca para indicar la dirección, la punta
de cada flecha representa el segundo nodo del par ordenado de nodos que
constituye un arco y la cola de la flecha representa el primer nodo del par.

El grado interno de un nodo en un grafo, es el número de aristas que terminan en

ese nodo; el grado externo de un nodo, es el número de aristas que salen de ese
nodo. El grado de un nodo, es la suma de sus grados internos y externos.

7.2 GRAFOS NO DIRIGIDOS

Los grafos no dirigidos se caracterizan porque sus arcos no están orientados o no

tiene sentido en sus conexiones (no son flechas). Es aquel cuyas aristas son no
son dirigidas, representan relaciones simétricas como relaciones de hermandad y
colaboración, conexiones de transportes, etc.

Sea G un grafo no dirigido donde G = (V, E), donde V corresponde al conjunto de

vértices y E el conjunto de aristas de un grafo, un grafo no dirigido se diferencia de
un grafo dirigido porque cada arista en E es un par no ordenado de vértices.

Cuando no importa la dirección de una arista, el grafo se denomina no dirigido,

una aplicación de grafos no dirigidos, es la red de computadores de una empresa,
en donde los vértices están representados en las terminales de los computadores
y las aristas son el cableado o en su defecto la conexión inalámbrica. En ese
sentido la información de la red se da en ambos sentidos al enviar y recibir
información de cada computador.

Figura 14. Grafo No Dirigido.

V = {A, B, C, D}
E = {(A,B), (B,A), (A,C), (C,A), (A,D), (D,A), (B,C), (C,B), (B,D), (D,B)}

Cami
no
7.3 CAMINO DE UN GRAFO

Es la secuencia o ruta de un vértice inicial a un vértice final. El número de aristas

de un camino (ciclo) se denomina longitud de camino. Un camino es simple si solo
pasa una sola vez por cada nodo. Un camino A es simple si no se repite ningún
vértice en él. Dos caminos son independientes si no tienen ningún vértice excepto
el primero y el último.

Longitud de camino: Es el número de arcos que se encuentran en un grafo, o el

número de enlaces que tiene el camino.

Por ejemplo:

 1, 2, 5, 1, 2, 3 es un camino con longitud 5.

 5,2,1 es un camino simple con longitud 2.

Un camino de un grafo G = (V, R) es una secuencia de nodos de V en los que

cada nodo es adyacente al siguiente mediante un arco de R.

Por ejemplo:

V = {1, 2, 3, 4, 5, 6}
R = {(1, 4), (1, 5), (1, 6), (2, 3),…….,(5, 1), (6, 2)}

Caminos: {1, 6, 2, 3}, {5, 1, 4},…….

 Figura 15. Camino de un Grafo.

Existen diferentes tipos de caminos:

Camino simple: Es el camino que no recorre el ismo arco dos veces. b, d y g es

un camino simple, pero b, d, g y b no es un camino simple.

Es un camino en el que todos los nodos contenidos son diferentes, con la posible
excepción del primero y el último, que podrían ser el mismo.

Camino simple: 6, 4, 5, 2

Figura 16. Camino simple.

Camino Cerrado: Es el camino que no pasa un mismo nodo más de una vez, b y
d es un camino elemental, pero b, d y g no lo es.
7.4 CICLO DE UN GRAFO

Cuando los dos extremos de un camino son iguales, el camino se llama circuito o
ciclo pero que no tenga aristas repetidas

Un ciclo es una cadena finita donde el nodo inicial de la cadena coincide con el
nodo terminal de la misma. Es un camino de longitud de al menos uno que
empieza y acaba en el mismo vértice. Se dice que se le puede llamar un ciclo a un
circuito simple si no existen vértices repetidos excepto el primero y el último.

Un ciclo por decir de otra forma, es un camino en el cual el primer y el último

vértice son iguales. Se llama ciclo simple si el camino es simple. En grafos no
dirigidos es necesario que las aristas sean diferentes.

Dados dos vértices (V, W) se dice que están conectados si existe un camino de V
a W.

Tipos de Ciclos:

 Ciclo simple: Es el ciclo que a su vez es una cadena simple, es un camino

de longitud no mayor o igual a 1, el cual comienza y termina en el mismo
vértice.

 Ciclo de Euler: Es un ciclo que pasa exactamente una vez por cada uno de
los arcos. Es un camino euleriano que comienza y termina en el mimo
vértice. Un grafo que admite un ciclo euleriano se dice que es un grafo
euleriano.

 Ciclo Hamiltoniano: Es un ciclo que pasa exactamente una vez por cada
uno de los vértices del grafo.
7.5 GRAFO CONEXO

Un grafo es conexo si cualquier vértice V le pertenece al conjunto de vértices y es

alcanzable por algún otro.

Sea G = (V, E) un grafo no dirigido, entonces G es conexo si existe un camino

entre cada par de vértices de G. Por otra parte, sea G un grafo dirigido, y sea G’
su grafo no dirigido asociado, entonces si G’ es conexo, G se considera conexo.

Es un grafo no dirigido que para cualquier par de nodos existe al menos un camino
que los une.

Figura 17. Grafo Conexo.

Un grafo no dirigido es conexo si existe un camino entre cualquier par de nodos

que forman el grafo. Grafo conexo y grafo no conexo con dos componentes
externos.
 Figura 18. Representación de Grafos.

Un grafo es doblemente conexo si para cada par de vértices está conectados al

menos dos caminos disjuntos, es decir, se dice que es conexo y no existe un
vértice tal que al sacarlo el grafo resultante sea disconexo.

Figura 19. Grafos.

7.6 GRAFOS COMPLETOS

Es aquel con una arista entre cada par de vértices, es decir un grafo con todas las
aristas posibles. Por otra parte, se denomina grafos densos aquellos que tienen
muchas aristas.
7.7 GRAFOS PONDERADOS

Se le asignan pesos a las aristas para representar la distancia o el costo asociado

a pasar por dicha arista.

Figura 20. Grafo Ponderado.

Grafo Nulo: Se dice que un grafo es nulo cuando

Grafos Isoformos

Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a
uno), entre sus vértices de tal forma que dos de estos quedan unidos por una
arista en común.

Incidencia, adyacencia y grado de un vértice:

Sea un grafo G = (V, A), los vértices u y v pertenecientes a V; y una arista (u, v)
perteneciente a A, se dice que:

Incidencia: La arista (u,v) es incidente con los vértices u y con v.

Adyacencia: Dos vértices u y v son adyacentes si existe una arista cuyos

vértices sean u y v:
  El vértice u es adyacente a v
 El vértice v es adyacente desde u

Grado: El grado de un vértice u es el número de vértices adyacentes a u.

Para un grafo dirigido, el grado de salida de un vértice u es el número de
vértices adyacentes desde u, mientras que el grado de entrada de un
vértice u es el número de vértices adyacentes a u.

En las siguientes imágenes podemos observar los grados de los vértices para un
grafo dirigido y un grafo no dirigido.

Figura 21. Grafos.

7.8 DENSIDAD DE UN GRAFO

La densidad de un grafo es el promedio de incidencia de los nodos. Si sumamos

los grados de incidencia se tendra un valor 2E, ya que se cuenta dos veces cada
enlace.
 La densidad D resulta: D = 2E / V.

Si un grafo tiene una densidad proporcional a V entonces es denso (el numero de

enlaces sera proporcional a en caso contrario es un grafo liviano.

7-9 GRAFOS SIMPLES

Un grafo simple es aquel que no tiene aristas paralelas o múltiples que unan el
mismo par de vértices. Un grafo que cuente con múltiples aristas entre dos
vértices se denomina multígrafo.

En la siguiente imagen podemos observar un ejemplo de grafo simple y de

multígrafo, donde existen aristas paralelas incidentes a los vértices a y d, y e y d.
En este caso, se dice que el grafo tiene multiplicidad 2 (máximo de aristas
paralelas entre dos vértices).

Figura 22. Grafos simple y Multigrafo.

Si asumimos un grafo simpe, se observan las siguientes propiedades:

 Si G es un grafo no dirigido con m vértices, entonces:

 Una arista (u, v) se cuenta dos veces en este sumatorio, uno como
vértice final u y otro como final v. Entonces, la contribución total de
las aristas a los grados de los vértices es dos veces el número de las
aristas.

 Si G es un grafo dirigido con m vértices, entonces:

En un grafo dirigido, una arista (u,v) contribuye una unidad al grado de

salida de su origen u y una unidad al grado de entrada de su vértice final v.
Por tanto, la contribución total de las aristas al grado de salida de los
vértices es igual al número de aristas, y similar para los grados de salida.

 Sea G un grafo simple con n vértices y m aristas, entonces:

o Si G es no dirigido:
o Si G es dirigido:

7.10 MULTÍGRAFO

Un multígrafo es cuando se acepta más de un arco uniendo dos vértices. En

términos generales no son grafos. Un multígrafo es un grafo que consta de
segmentos múltiples y lazos.

Un multígrafo es un grafo en el que hay pares de vértices unidos por más de una
arista, es decir, que tienen aristas múltiples.
 Figura 23. Multígrafo.

En la imagen anterior, los vértices 1 y 2 tienen grado 3 y el vértice 3 tiene grado 2.

En general, en un multígrafo sigue teniendo sentido definir el grado de un vértice
como el número de aristas incidentes con este.

Multígrafo con dos pares de aristas

Figura 24. Multígrafo.

Esto resulta sencillo transformar un multígrafo en un grafo añadiendo un vértice en

medio de cada lazo o de algunas aristas múltiples, En la siguiente imagen,
añadiendo vértices y uniéndolos mediante aristas, se ha convertido el multígrafo
en grafo.
Grafo generado a partir de un multígrafo de 3 lazos.

Figura 25. Multígrafo.

Un multígrafo M se dice que es finito si tiene un número finito de nodos y de

aristas. Debemos tener claro que un grafo G con un numero finito de nodos debe
automáticamente un número finito de aristas y por consiguiente debe ser finito.
Esta premisa no será cierta para los multígrafos, ya que estos tendrán múltiples
aristas.

Un multígrafo es un grafo dirigido que está diseñado para tener aristas múltiples,
es decir, para tener aristas con los mismos nodos iníciales y finales.

Un multígrafo G es un par ordenado de G (V, A) donde:

 V es un conjunto de vértices o nodos.

 A es un conjunto de pares ordenados de nodos, llamados aristas
dirigidas, arcos o flechas.

Un multígrafo es un grafo en el que hay aristas o lazos que tienen el mismo

extremo, estos son combinaciones de los otros tipos de grafos. Un multígrafo
mixto G = (V, E, A) tiene la misma definición que un grafo mixto, es decir, tiene la
capacidad de poseer al mismo tiempo las aristas dirigidas A y las aristas no
dirigidas E.

7.11 MATRIZ DE ADYACENCIA

Un grafo se puede representar mediante una matriz, esta es la forma más sencilla
de representar un grafo. A esta matriz se le conoce con el nombre de Matriz de
Adyacencia.

La matriz de adyacencia consiste en un arreglo bidimensional de tamaño n, donde

la n representa la máxima cantidad de nodos de un grafo. Cada una de las casillas
de la matriz se carga con valores verdaderos V o falso F en caso de que posea un
camino de un nodo o fila con columna. La matriz será simétrica cuando los grafos
sean no dirigidos.

La principal ventaja de la matriz de adyacencia es su simplicidad, ya que facilita

las operaciones que puedan realizarse sobre el grafo, pero su desventaja es que
se limita a un número máximo de nodos en el grafo, lo que provoca que sea
imposible almacenar más información en la matriz. Cuando la matriz se hace muy
grande para representar un grafo pequeño, se perderá espacio de
almacenamiento de la matriz y de la memoria. En el caso de los grafos no
dirigidos, la perdida de almacenamiento y de memoria será mayor dado que la
matriz es simétrica y los datos se duplicaran.

Los vértices se conciben como enteros en el conjunto {0,1,2,3,….,n-1} y las aristas

como parte de tales enteros. Esto permite almacenar referencias a las aristas en
las celdas de la matriz bidimensional de nxn. Cada fila y cada columna
representan un vértice del grafo y cada posición representa una arista (o la
ausencia de esta) cuyo vértice origen se encuentra en la fila y vértice final se
encuentra en la columna.

En la siguiente figura veremos la representación de un grafo en una matriz de

adyacencia:
 Figura 26. Representación de una Matriz de Adyacencia

Grafo y matriz de adyacencia para un grafo no dirigido, donde podemos observar

la matriz simétrica:

Figura 27. Matriz de Adyacencia.

En una matriz de adyacencia, los vértices se representan mediante índices.

Por ejemplo:

Sea un grafo con los vértices:

V = {a,b,c,d,e}

Serán representados con los índices:

I = {0,1,2,3,4}
En la siguiente imagen veremos la relación entre vértices e índices.
 Figura 28. Vértices e Índices.

Ejemplo de representación de un grafo en una matriz de adyacencia:

Figura 29. Grafo.

Figura 30. Matriz de Adyacencia

Ventajas de la Matriz de adyacencia:

  Se puede determinar en un tiempo fijo y constante si un arco pertenece o
no al grafo.
 Es fácil determinar si existe o no un arco o enlace, solo se debe posicionar
en la matriz.
 Es fácil determinar si existe un ciclo en el grafo, basta multiplicar la matriz
por ella misma n veces hasta obtener la matriz nula (no hay ciclos) o bien
una sucesión periódica de matrices (hay ciclo).

Desventajas de la Matriz de adyacencia:

 Se requiere un almacenamiento |v|*|v|. Es decir O(n2).

 Solo al leer o examinar la matriz puede llevar un tiempo de O(n2).

7.12 LISTAS DE ADYACENCIA

Otra estructura de datos es la lista de adyacencia, en la que la idea es asociar a

cada vértice i del grafo una lista que contenga todos aquellos vértices j que sean
adyacentes a él. De esta forma solo se reserva memoria para las aristas
adyacentes a i y no para todas las posibles aristas que pudieran tener como origen
i (de la misma forma que sucede en la matriz de adyacencia).

Para implementar un grafo será conveniente usar listas de adyacencia

cuando el grafo es poco denso, y además, el problema a resolver tiene que
recorrer todas las aristas.
Se utiliza una lista enlazada, llamada directorio que almacena los nodos N del
grafo, y asociado a cada nodo del grafo se encuentra una lista enlazada con los
nodos que son adyacentes a él.

En las listas están las aristas del grafo.

  Un grafo no dirigido de orden N con A aristas requiere N entradas en el
directorio y 2*A entradas de listas enlazadas, excepto si existen bucles,
que reduce el número de entradas a la lista en 1.
 Un grafo dirigido de orden N con A arcos requiere N entradas en el
directorio y A entradas de listas enlazadas.

Ejemplos:

Grafo No dirigido:

Figura 31. Grafo No Dirigido.

En la siguiente imagen vemos la representación de un grafo no dirigido en una

lista de adyacencia.
 Figura 32. Matriz de Adyacencia.

Grafo Dirigido:

Figura 33. Grafo Dirigido.

En la siguiente imagen vemos la representación de un grafo dirigido en una lista

de adyacencia.
 Figura 34. Matriz de Adyacencia.

Los números de vértice en una lista de adyacencia no están obligados a aparecer

en ningún orden en particular, aunque a menudo es conveniente enumerarlos en
orden ascendente.

Ventajas de la lista de Adyacencia:

 La lista de adyacencia requiere un espacio proporcional a la suma

del número de vértices más el número de arcos. Hace buen uso de la
memoria.
 Se utiliza bastante cuando el numero de enlaces es mucho menor
que O(n2).

Desventajas de la lista de Adyacencia:

 La representación con lista de adyacencia es que puede llevar un

tiempo O(n) determinar si existe un arco vértice i al vértice j, ya que
pueden haber O(n) vértices en la lista de adyacencia. Para el vértice
i.
 Glosario

PILA: es un conjunto de elementos, los cuales solo se pueden acceder (insertar o

eliminar) por un solo extremo.

COLA: es una estructura de datos, caracterizada por ser una secuencia de

elementos en la que la operación de inserción se realiza por un externo y la
operación de extracción por el otro.

ARBOL: estructura no lineal jerárquica en la que a cada elemento le corresponde

un único antecesor y sus sucesores.

NODO: elementos de un árbol y están conectados entre sí por medio de ramas o

enlaces.

GRAFO: son estructuras que se componen de dos partes, el conjunto de vértices,

nodos o puntos, y el conjunto de aristas, líneas o lados los cuales pueden ser
orientados o no.

VÉRTICE: son aquellos objetos de un grafo que contienen información, su

representación suele ser circunferencias o puntos los cuales dentro de los mismos
llevan el contenido.

ARISTA: son las conexiones o uniones que se usan entre los vértices, se
representan por medio de líneas, se suele añadir junto a la línea el nombre de los
vértices origen y destino.

CAMINO: es la secuencia o ruta de un vértice inicial a un vértice final.

GRADO: el grado de un vértice es el número de vértices adyacentes a u.

 Bibliografía

Joyanes Aguilar, Luis, Algoritmos y Estructuras de Datos. Una Perspectiva En C

Editorial: McGraw-Hill (2005).

Guardati Buemo, Silvia. Estructura de datos orientada a objetos: Algoritmos con

C++ Editorial: Pearson (2007).

Prieto A., Lloris A. y Torres J.C. Introducción a la informática Editorial McGraw-Hill

(2001).

Lazaro, Obenza J. C. Estructuras de datos y Algoritmos, Editorial Prentice Hall,

Madrid (2000).

Euguíluz Morán, Andoni Estructuras de datos y algoritmos Editorial McGraw-Hill

(1999).

Rodríguez Baena, Luis; Fernandez Azuela, Matilde; Joyanes Aguilar Fundamentos

de programación: algoritmos, Estructuras de datos y objetos. Editorial McGraw-Hill
(2003).

Román Martínez, Elda Quiroga. Estructura de datos referencia practica con

orientación a objetos Editorial: Thomsan Learning (2002).

Orallo, Enrique Hernández, Orallo, José Hernández, Ma. Carmen Juan Lizandra.
C++ Estándar. Editorial Paraninfo (2001).

Marquez, Gabriela, Osorio, Sonia, Olvera, Noemi. Introducción a la Programación

Estructurada en C. Editorial Pearson (2011).