• Author / Uploaded
• Pas Chejo

• Categories
• Cola (tipo de datos abstractos)
• Puntero (Programación de computadora)
• Poco
• Java (lenguaje de programación)
• Recursividad

Citation preview

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS 333333

FUNDAMENTOS DE ESTRUCTURA DE DATOS DEFINICIÓN DE COMPUTADORA. Computadora,

computador

u

ordenador,

es una máquina electrónica, capaz de reconocer

datos

procesarlos

y

de

producir

entrada, información

relevante; todo esto bajo el control de un programa de instrucciones, que es almacenado previamente.

SISTEMA DE PROCESAMIENTO DE DATOS.

El

propósito

de

toda

computadora

es

el

procesamiento

de

datos, estos datos pueden ser: las cifras de ventas de un supermercado,

las

calificaciones

de

un

curso,

lista

de

clientes, lista de proveedores, registros de los empleados.

1

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

DEFINICIÓN DE DATO, El

dato

alfabética,

es

una

representación

algorítmica,

etc.)

de

simbólica un

atributo

(numérica, o

variable

cuantitativa. Los datos describen hechos empíricos, sucesos y entidades. La ejecución de programas de instrucciones, son reflejados en los cambios de valor que sufren los datos de entrada, dando lugar a los datos de salida (información).

En la resolución de problemas con computadora. El diseño de la estructura de datos es tan importante, como el diseño del algoritmo, o el desarrollo e implementación del programa.

REPRESENTACIÓN FÍSICA DE LOS DATOS. a. DEFINICIÓN DE BIT: Es la unidad de información más sencilla posible en el sistema binario. Significa dígito binario, o lo que es lo mismo, número (dígito) con dos posibles valores: 0 ó 1. b. DEFINICIÓN DE BYTE: Unidad de información que consta de 8 bits equivalente a un

único

caracter,

como

una

letra,

número

o

signo

especial. 2

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

c. DEFINICIÓN DE CARACTER: Es un elemento tomado de un conjunto de símbolos. En el cual se incluyen dígitos, los caracteres del alfabeto y algunos caracteres especiales. {0,1,2,3,4,5,6,7,8,9, A, B, C....Y, Z, ¡,-,+,*} d. DEFINICIÓN DE PALABRA: Conjunto

de

manipular

una

bits

que,

como

computadora.

unidad

La

elemental,

longitud

en

bits

puede de

una

palabra en una computadora puede ser de 8, 16, 32, etc., y depende

del

microprocesador

de

su

unidad

central

de

proceso.

DEFINICIÓN DE ESTRUCTURA DE DATOS:

En programación, una estructura de datos es una forma de organizar un conjunto de datos simples con el objetivo de facilitar su manipulación. Un dato elemental es la mínima información que se tiene en un sistema1.

Una

estructura

interrelación

de

que

datos

existe

define entre

la

éstos

organización datos. Además

y

la

de

un

conjunto de operaciones que permite manipularlos.

1

3

http://es.wikipedia.org

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

CLASIFICACIÓN DE ESTRUCTURAS DE DATOS: En un programa, cada variable pertenece a alguna estructura de datos explícita o implícitamente, la cual establece el conjunto de operaciones válidas para ella. La clasificación se la describe de la siguiente manera:

- Entero

E S T R U C T U R AS D E D A T O S

ESTANDAR O PRIMITIVOS

- Real - Logico - Caracter

DATOS SIMPLES DEFINIDOS POR EL PROGRAMADOR

- Subrango (subrange) - Enumerativo (enumerated)

- Cadena ESTÁTICOS

- Array 's (vector/Matriz) - Registro - Archivo

DATOS ESTRUCTURA DOS

- Pilas - LINEALES

- Colas - Listas

DINÁMICOS - NO LINEALES

4

-Árboles - Grafos

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

DATOS

SIMPLES

(PRIMITIVOS).

Son

aquellos

que

no

están

compuestos por otras estructuras: a. Enteros, Una estructura de datos primitiva. Miembro del siguiente conjunto de números: {...,-(n+1), -n,...-2,1,0,1,2...n,n+1,...} Las operaciones fundamentales sobre enteros son: suma, resta, multiplicación, división, exponenciación y otras. b. Reales,

Los

números

reales

siempre

tienen

un

punto

decimal y pueden ser positivos o negativos. Un número real

consta

de

un

entero

y

una

parte

decimal,

por

ejemplo, 0.08,3789.25,-8.12,3.0 Las operaciones fundamentales sobre enteros son: suma, resta, multiplicación, división, exponenciación y otras c. Booleanos, llamado también lógico. Es un elemento que puede tener uno de dos valores: verdadero o falso (1 o 0). Los tres operadores booleanos básicos son not, and, y or (negación, conjunción, y disyunción) d. Carácter, carácter.

Un se

dato

tipo

reconoce

carácter los

contiene

siguientes

sólo

un

caracteres

alfabéticos y numéricos: - Caracteres Alfabéticos (A,B,C...X,Y,Z) (a,b,c,.....z) - Caracteres Numéricos (1,2,3......,9,0) - Caracteres especiales (+,-,*,/,`,,°,$,&....) DATOS ESTRUCTURADOS. Los datos simples se pueden combinar de varias maneras para formar estructuras más complejas como:

5

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

a. ESTRUCTURA DE DATOS ESTÁTICOS. Son aquellos que tienen una cantidad fija de memoria, la cual es asignado en el momento de su creación y no puede cambiar durante la ejecución del programa. Ejemplo. String, Array’s, Registros y Archivos b. ESTRUCTURA DE DATOS DINÁMICOS. Son aquellos que no tienen una cantidad fija de memoria. La

cantidad

de

memoria

va

incrementando

o

disminuyendo

durante la ejecución del programa. Entre las principales tenemos -

Lineales: Pilas, Colas (simples, circulares, dobles) y Listas (simples, circulares, dobles)

-

No Lineales: Árboles (general, binario, binario de búsqueda) y Grafos.

OPERACIONES SOBRE LOS DATOS ESTRUCTURADOS. Las operaciones básicas son: a. Inserciones,

adicionar

un

nuevo

valor

a

la

estructura. b. Eliminaciones, borrar un valor de la estructura. c. Búsquedas,

encontrar

estructura

para

valor,

forma

en

un

realizar

determinado una

secuencial(o

valor

operación binario,

con

en

la este

siempre

y

cuando los datos estén ordenados). d. Recorridos, visitar cada uno de los elementos de la estructura.

6

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

CONCLUSIÓN. Cada estructura de datos, ofrece ventajas y desventajas en relación a la sencillez y eficiencia para la realización de cada operación. De esta forma, la elección de la estructura de datos apropiada para cada problema; depende de factores como

la

frecuencia

y

el

orden

en

que

se

realiza

cada

operación sobre los datos.

7

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

RECURSIVIDAD

DEFINICIÓN DE FUNCIONES.

Las

funciones,

son

SUBPROGRAMAS

(conjunto

de

instrucciones), que realizan una tarea concreta y retornan un único valor.

CARACTERÍSTICAS DE LAS FUNCIONES. a) Poseen un nombre (identificador). b) Posee

variables

para

recibir

datos

(parámetros

de

entrada). c) Una función es invocado por el programa principal u otras funciones. d) El resultado se almacena en el nombre de la función. e) Para retornar un valor se usa la palabra return. 8

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

RECURSIVIDAD. La recursividad no es una estructura de

datos,

sino,

una

técnica

programación

que

bloque

instrucciones

de

permite

que

de un sea

ejecutada un cierto número de veces. Establece una alternativa al uso de los bucles while, do while y for.

DEFINICIÓN DE FUNCIÓN RECURSIVA. Una función es recursiva, si y solo, si se llama a sí misma repetidas

veces,

hasta

que

satisfaga

una

condición

establecida con anterioridad, denominado criterio base.

REGLA DE RECURSIVIDAD EN LA RESOLUCIÓN DE PROBLEMAS. Para poder implementar la solución de un problema de forma recursiva, es necesario cumplir con las siguientes condiciones: a) El problema debe poder definirse en términos de sí mismo. b) El

problema

debe

incluir

una

condición

de

finalización (criterio base). c) Cuando la condición de finalización (criterio base), sea verdadera, la función no debe volver a llamarse a sí misma. d) El

problema

debe

poder

resolverse

en

un

conjunto

finito de pasos.

9

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

TIPOS DE FUNCIONES RECURSIVAS. Dependiendo

del

número

de

funciones

a

utilizarse

podemos

diferenciar:

1. RECURSIVIDAD DIRECTA. a. FUNCIÓN RECURSIVA SIMPLE. En la recursión simple cada llamada

recursiva

genera,

como

mucho,

otra

llamada

recursiva.

Ejemplo 1. Implementar una función recursiva en java, que obtener el factorial de un número n.

int factorial(int n) { if(n==0) return 1; else return n*factorial(n-1); }

Ejemplo 2. Implementar una función recursiva en java, que permita hacer la división por restas sucesivas.

int division(int a, int b) { if(b > a) return 0; else return division(a-b, b) + 1; }

10

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

b. FUNCIÓN

RECURSIVA

MÚLTIPLE.

Cada

llamada

recursiva

genera más de una llamada a la función. Ejemplo 3. Implementar una función recursiva en java, que calcule un número de la serie Fibonacci.

int fibonacci(int n){ if(n==1 || n==2) return 1; else return fibonaci(n-1)+fibonaci(n-2); }

2. RECURSIVIDAD INDIRECTA. c. FUNCIÓN RECURSIVA MUTUA. Cada llamada recursiva genera que dos funciones se llamen mutuamente. Ejemplo 4. Implementar una función recursiva en java, que determine si un número es impar.

public boolean par(int n){ if(n==0) return true; else return impar(n-1); }

public boolean impar(int n){ if(n==0) return false; else return par(n-1); } 11

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

Ejemplo 5. Implementar una función recursiva en java, que determine si un número es positivo.

public boolean positivo(int n){ if(n>0) return true; else return negativo(n); }

public boolean negativo(int n){ if(n raizAux.dato) { padre = raizAux; raizAux = raizAux.derecho; } else { padre = raizAux; raizAux = raizAux.izquierdo; } } return null; } 2. OPERACIONES FUNDAMENTALES, lo conforman los métodos que permiten insertar nuevos nodos y eliminarlos; para ello se apoyan en otros métodos como ser: buscar (existeDato), padre de, recorrerIzquierda, etc.

a. BÚSQUEDA EN UN ABB: La búsqueda se iniciará por el nodo raíz. Si X es igual al campo dato del nodo, la búsqueda finaliza con éxito. Si X es menor al campo dato del nodo,

se

deberá

realizar

la

búsqueda

en

el

subárbol

izquierdo. Si por el contrario, X es mayor entonces la búsqueda continua por el subárbol derecho. El proceso continúa hasta que se encuentre un nodo con el campo dato igual a X o un subárbol vacío [NULL] quién avala que no existe ningún nodo con el valor X. 103

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

public nodo existeDato(int datoX) { nodo raizAux = raiz; while (raizAux != null) { if (datoX == raizAux.dato) return raizAux; else if (datoX > raizAux.dato) raizAux = raizAux.derecho; else raizAux = raizAux.izquierdo; } return null; }

b. INSERCIÓN DE UN NODO EN UN ABB: lo primero que se debe hacer es realizar la búsqueda. Si el dato a insertar se encuentra contrario,

en se

el

árbol,

inserta

no el

se dato

hace en

nada. el

En

lugar

caso que

corresponde. Manteniendo la estructura ABB.

104

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

public void insertarNodo(int x) { nodo nuevo = new nodo(); nuevo.dato = x; if (arbolVacio()) // Caso: árbol estuviese vacío el nuevo es la raíz raiz = nuevo; else { // Caso: árbol tuviera otros nodos. if (existeDato(x) == null) { nodo padre = null; nodo raizAux = raiz; // Recorre hasta ubicar el lugar a insertar while (raizAux != null) { padre = raizAux; if (x < raizAux.dato) raizAux = raizAux.izquierdo; else raizAux = raizAux.derecho; } // Enlaza como hijo izquierdo o derecho if (x < padre.dato) padre.izquierdo = nuevo; else padre.derecho = nuevo; } else // Caso: valor repetido, no se inserta System.out.println("YA Existe... " + x + "!, en el Árbol."); } }

105

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

NOTA: Los nodos se insertan siempre por las hojas, ya que la búsqueda acaba sin éxito cuando se accede a un subárbol izquierdo o derecho que está vacío. c. ELIMINACIÓN DE UN NODO EN UN ABB: Es un proceso complejo ya que se debe mantenerse la estructura de un árbol binario, lo primero es buscar en el árbol la posición del nodo a eliminar y luego eliminar según el caso: - Eliminar

un

nodo

sin

hijos

con

un

(hoja),

simplemente

se

elimina el nodo. - Eliminar

un

nodo

solo

hijo,

solo

hay

que

realizar una reasignación de punteros. el padre del nodo que queremos eliminar pasa a apuntar al hijo del nodo que está siendo eliminado. - Eliminar un nodo con dos hijos, 1. Se reemplaza el campo dato del nodo que queremos eliminar con el dato máximo de su subárbol izquierdo (o el elemento mínimo de su subárbol derecho) 2. Seguidamente, se elimina el nodo máximo (o mínimo, según el caso).

public int eliminarNodo(nodo dne) { if (!arbolVacio()) { int x = dne.dato; // Creamos var para saber si tiene hijos izq y der boolean tieneNodoDerecha = dne.derecho != null? true : false; boolean tieneNodoIzquierda = dne.izquierdo != null? true : false; // Caso 1: No tiene hijos (es un nodo hoja) 106

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

if(!tieneNodoDerecha && !tieneNodoIzquierda) { nodo padre = padreDe(dne); if (padre.izquierdo == dne) { padre.izquierdo = null; } if (padre.derecho.dato == dne.dato) { padre.derecho = null; } } // Caso 2: Tiene un solo hijo y el otro no if ((tieneNodoDerecha && !tieneNodoIzquierda) || (!tieneNodoDerecha && tieneNodoIzquierda)) { nodo padre = padreDe(dne); /* Guardemos los hijos del padre temporalmente para saber cuál de ellos hay que eliminar*/ nodo hijoActual = dne.izquierdo != null ? dne.izquierdo : dne.derecho; if (padre.izquierdo == dne) { padre.izquierdo = hijoActual; } if (padre.derecho == dne) { padre.derecho = hijoActual; } } // Caso 3: Tiene ambos hijos if (tieneNodoDerecha && tieneNodoIzquierda) { /* Tomamos el hijo derecho del Nodo que queremos eliminar*/ nodo nodoMasALaIzquierda =

recorrerIzquierda(dne.derecho);

nodo padre = padreDe(nodoMasALaIzquierda);

107

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

/* Reemplazamos el valor del nodo que queremos eliminar por el nodo que se encuentra más a la izquierda.*/ dne.dato = nodoMasALaIzquierda.dato; // Eliminamos el nodo más a la izquierda if (padre.dato != nodoMasALaIzquierda.dato) padre.izquierdo = null; else padre.derecho = null; } return x; } else System.out.println("Árbol Vacío...! No hay nada para eliminar"); return 0; } /* Recorre recursivamente hasta encontrar el nodo más a la izquierda*/ public nodo recorrerIzquierda(nodo dne) { if (dne.izquierdo != null) { return recorrerIzquierda(dne.izquierdo); } return dne; }

d. Recorrido en In-Orden, se realiza mediante el recorrido In-Orden.

private void imprimirInOrden(nodo aux) { if (aux != null) { imprimirInOrden(aux.izquierdo); System.out.print(aux.dato + " "); 108

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

imprimirInOrden(aux.derecho); } } public void imprimirInOrden() { if (!arbolVacio()) { imprimirInOrden(raiz); System.out.println(""); } else System.out.println("Árbol sin hojas...! No hay nada que mostrar."); }

e. Recorrido Pre-Orden, se realiza mediante el recorrido Pre-Orden.

private void imprimirPreOrden(nodo aux) { if (aux != null) { System.out.print(aux.dato + " "); imprimirPreOrden(aux.izquierdo); imprimirPreOrden(aux.derecho); } } public void imprimirPreOrden() { if (!arbolVacio()) { imprimirPreOrden(raiz); System.out.println(""); } else System.out.println("Árbol sin hojas...! No hay nada que mostrar."); }

109

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

f. Recorrido Post-Orden, se realiza mediante el recorrido Post-Orden.

private void imprimirPostOrden(nodo aux) { if (aux != null) { imprimirPostOrden(aux.izquierdo); imprimirPostOrden(aux.derecho); System.out.print(aux.dato + " "); } } public void imprimirPostOrden() { if (!arbolVacio()) { imprimirPostOrden(raiz); System.out.println(""); } else System.out.println("Árbol sin hojas...! No hay nada que mostrar."); }

3. OPERACIONES COMPLEMENTARIAS, son aquellos métodos que son adicionales a las operaciones fundamentales como recorrer el árbol, mostrar los datos del árbol, etc. EJERCICIOS. 1. Desarrollar un método que muestre por pantalla la cantidad de nodos hoja. 2. Desarrollar un método que muestre por pantalla la altura del árbol. 3. Desarrollar

un

método

que

muestre

por

pantalla

por

pantalla

Localización de un dato mayor del árbol. 4. Desarrollar

un

método

que

muestre

Localización de un dato menor del árbol. 110

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

ESTRUCTURA: GRAFOS.

Un

grafo

es

una

manera

de

representar

relaciones

que

existen entre pares de objetos. En un grafo se distinguen básicamente dos elementos: los nodos, mejor conocidos como vértices, y los arcos, llamados aristas,

que

conecta

un

vértice

con

otro.

Los

vértices

almacenan información y las aristas representan relaciones entre dichas información. DEFINICIONES DE GRAFOS.

111

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

Definición 1. Un grafo se define como un par G = (V, A), donde V es un conjunto finito no vacío de vértices y A es un conjunto de pares de vértices de V, es decir, las aristas. Definición 2. Un grafo G se define como un par ordenado, G = (V, A), donde V es un conjunto finito y A es un conjunto que consta de dos elementos de V. TERMINOLOGÍA Y CONCEPTOS. 1. GRAFOS DIRIGIDOS Y NO DIRIGIDOS. Dependiendo del tipo de relación distintos

entre

los

tipos

de

vértices grafos.

del

grafo,

se

definen

Así se distinguen

aristas

dirigidas y no dirigidas: ARISTA DIRIGIDA: es aquella que define un par ordenado de

vértices

(u,v),

donde

el

primer

u

vértice

es

el

origen de la arista y el segundo vértice v es el término (o vértice final). El par (u, v) ≠ (v, u). ARISTA NO

DIRIGIDA:

es

aquella

que define

un

par

no

ordenado de vértices (u, v), donde (u, v) = (v, u). GRAFO DIRIGIDO: Es aquel cuyas aristas son dirigidas. Los

grafos

dirigidos

asimétricas como por

suelen

representar

ejemplo: relaciones

relaciones

de

herencia,

los vuelos entre ciudades, etc.

GRAFO

NO

DIRIGIDO: Es

dirigidas. relaciones 112

aquel

Representan de

hermandad

cuyas

relaciones y

aristas

son

simétricas

colaboración,

no como

conexiones de

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

transportes, etc.

2. 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, donde: 

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.

113

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

3. GRAFOS SIMPLES Y MULTIGRAFOS. 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 multigrafo.

Si asumimos un grafo simple, 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 vértice final v. Entonces, la de

las

aristas

a

los

contribución

grados

de

total

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 114

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

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 al

grado

de

salida

de

aristas

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: 

Si G es no dirigido: m ≤ n(n-1)/2.



Si G es dirigido: m ≤ n(n-1).

4. CAMINO, BUCLE Y CICLO.

CAMINO.

Es

aristas

q ue

una

secuencia

comienza

que

por

un

alterna

vértice

y

vértices

y

termina

en

vértice tal que cada arista es incidente a su vértice predecesor y sucesor. Es decir, un camino es un sucesión de vértices de vi

V:

que cumple que: (vi,,vi+1) ∊ A ∀ i ∊ {0 … k-1}. Se dice que este camino tiene longitud k. Es decir, el número de aristas de un camino o ciclo es la longitud del camino. Un camino es simple si cada vértice en el camino es distinto, último

excepto

vértice.

Un

posiblemente camino

por

simple

el

primero

cumple

la

y

el

siguiente

restricción: vi ≠ vj ∀ i ∊ {0…k}, j ∊ {1…k-1}, i≠j Para todo vértice x, existe el camino simple , que 115

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

sería el camino de longitud 0. BUCLE.

Es

un

camino

de

longitud

1

que

comienza

y

termina en el mismo vértice: .

CICLO. Es un camino simple que cumple las siguientes restricciones: v0= vk Si es no dirigido, k = 1 (es un bucle) o k ≥ 3.

5. GRAFOS CONEXOS. Sea G = (V, A) un grafo no dirigido, se le

denomina

conexo

si

existe

un

camino

entre

dos

vértices cualesquiera de G. Para un grafo dirigido G, su

grafo

asociado

no dirigido es aquel que se obtiene

ignorando la dirección de las aristas. G se considera conexo si su grafo asociado es conexo.

La Figura 5.5

muestra ejemplos de grafos conexos y no conexos.

116

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

6. GRAFOS VALORADOS Y GRAFOS ETIQUETADOS. Un grafo valorado (o ponderado) es una terna donde es un grafo y f es una función cualquiera, denominada función de coste, que asocia un valor o peso a cada arista en el grafo. El peso de un camino en un grafo con pesos es la suma de los pesos de todas las aristas atravesadas. En un grafo etiquetado, la función f tiene como imagen un conjunto de etiquetas no numéricas.

IMPLEMENTACIÓN DE GRAFOS Los

dos

tipos

de

implementación

más

frecuentes

(independientemente del lenguaje de programación)

para

la

representación de grafos son las matrices de adyacencias y las listas de adyacencias. En este tema, se detallarán ambas implementaciones en el lenguaje Java. 1. MATRIZ DE ADYACENCIAS

117

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

Una matriz de adyacencias A (implementada como una matriz bidimensional) determina vértices los

de

vértices

las

un

grafo.

se

conciben

adyacencias

En

una

como

matriz enteros

entre

pares

de

de adyacencias, en

el

conjunto

{0,1,…,n-1} y las aristas como pares 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. La Figura 5.7 muestra la representación gráfica de un grafo y su matriz de adyacencias. En una tabla de adyacencias, los vértices se representan mediante índices. Así, sea un grafo {a,b,c,d,e},

estos

serán

con

representados

los

vértices

mediante

sus

índices {0,1,2,3,4} tal y como se muestra en la Figura 5.9.

De esta manera, podemos definir una matriz A bidimensional de n x n donde la celda [i, j] guarda información referente a la arista (v, w), en caso de que exista, donde v es el vértice con índice i y w es el vértice con índice j. Existen varias posibilidades para representar la arista (v, w) en su 118

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

correspondiente celda A [i, j]: Si no es etiquetado: un valor booleano que toma el valor 1 si existe la arista y 0 en caso contrario. Si es valorado: un real con el valor f (i, j) si existe la arista. En caso contrario,toma el valor ∞. Se obtendría la matriz de costes del grafo. Si es etiquetado: una etiqueta con el valor f (i, j) si existe

la

arista.

En

caso

contrario,

toma

el

valor

“etiqueta imposible”. Se obtendría la matriz de etiquetas del grafo. A continuación, se muestra una posible implementación de un grafo en una matriz de adyacencias en Java. Se asume que se trata de un grafo simple no etiquetado (tanto dirigido como no dirigido). 2. LISTA DE ADYACENCIAS

Otra implementación frecuente para la estructura grafo es la lista de adyacencias. En una

lista

de

adyacencias,

a

cada vértice i se le asocia una lista enlazada con todos los

vértices

j

adyacentes

a

i.

De

esta

forma

sólo

se

reserva memoria para las aristas adyacentes a i y no para todas las posibles aristas que pudieran tener como origen i (como ocurre en una matriz de adyacencias).

119

Ing. Pascual Yana Chejo

UNIVERSIDAD PÚBLICA DE EL ALTO ING. DE SISTEMAS – ESTRUCTURA DE DATOS

El grafo, por tanto, se representa por medio de un vector de n componentes, siendo n el número de vértices del grafo, donde cada componente constituye la lista de adyacencias correspondiente a cada uno de los vértices del grafo. Cada nodo de la lista consta de un campo indicando el vértice adyacente.

En

caso

de

que

el

grafo

sea

etiquetado

o

valorado, habrá que añadir un segundo campo para mostrar el valor de la etiqueta o el peso de la arista.

120

Ing. Pascual Yana Chejo