PDF de programación - Tema 6. Introducción a los esquemas algorítmicos - Estructuras de Datos y Algoritmos

Estructuras de Datos 

y Algoritmos

Tema 6. Introducción a los esquemas 

algorítmicos

Prof. Dr. P. Javier Herrera

Contenido

1
2
3

Conceptos básicos de grafos y su especificación algebraica
Algoritmos de ordenación
Algoritmos de búsqueda

Tema 6. Introducción a los esquemas 

algorítmicos

2

1. Grafos

•

llamados aristas.

Estructuras relacionales que generalizan las estructuras arbóreas.

el conjunto de vértices y A⊆ V × V es un conjunto de pares de vértices 

• Un grafo G se define como un par de conjuntos finitos (V, A), donde V es 

Tema 6. Introducción a los esquemas 

algorítmicos

3

1. Grafos

•

Se distinguen diferentes tipos de grafos:

– Dirigidos, cuando los pares de las aristas están ordenados.

En la arista (v,w), v es el origen, w es el destino y w es adyacente a v.
El grado de entrada de un vértice v es el número de aristas de las 
cuales v es el destino. El grado de salida es el número de aristas de 
las cuales v es el origen.

– No dirigidos, cuando los pares de las aristas no están ordenados.
Se habla simplemente de grado de un vértice y extremos de una 
arista, siendo ambos adyacentes entre sí.

– Valorados, cuando las aristas tienen asociado algún valor (peso, 

longitud, etc.). Sus vértices pueden estar ordenados o no.

Tema 6. Introducción a los esquemas 

algorítmicos

4

1.1 Terminología

Subgrafo: G′ = (V′, A′) es subgrafo de G = (V, A), denotado por G′ ⊆ G, si 
V′ ⊆ V, A′ ⊆ A y G′ está bien definido como grafo.
vi∈ V es un camino en G si ∀i : 1 ≤ i < n : (vi, vi+1) ∈ A.

• Camino: Para un grafo G = (V, A) la secuencia (v1, v2, …, vn) con n ≥ 1 y    

G1 y G2 son subgrafos de G

•

– La longitud de un camino es el número de aristas que lo forman.
– La distancia mínima entre dos vértices de un grafo se define como la 

longitud del camino más corto que parte de v y llega hasta w.

– Para grafos valorados, el coste de un camino es la suma total de los 

costes asociados a las aristas que lo forman.

Tema 6. Introducción a los esquemas 

algorítmicos

5

1.1 Terminología

• Ciclo: Es un camino de longitud no nula que comienza y termina en el 

mismo vértice.
– Se dice que un grafo es acíclico cuando no tiene ciclos.
– Los ciclos que pasan exactamente una vez por cada vértice se denominan 

hamiltonianos.

• Conexión: Se dice que un grafo no dirigido es conexo si para cada par de 

vértices diferentes v y w existe un camino desde v a w.
– Si un grafo no es conexo, los mayores conjuntos de vértices tales que los subgrafos 

inducidos son conexos se denominan componentes conexas del grafo.

– Se dice que un grafo dirigido es fuertemente conexo si para cada par de vértices 

diferentes v y w existe un camino desde v a w y un camino desde w a v.

– A los grafos no dirigidos, conexos y acíclicos se los denomina árboles libres.
– Un árbol de recubrimiento de un grafo no dirigido es un árbol libre que es subgrafo del 

grafo original y que incluye todos sus vértices.

Tema 6. Introducción a los esquemas 

algorítmicos

6

1.2 TAD de los grafos

•

El TAD de los grafos contiene las siguientes operaciones:

– crear el grafo vacío,
– añadir un vértice,
– añadir una arista,
– eliminar un vértice y todas las aristas de las que es origen o destino,
– eliminar una arista,
– determinar si un vértice pertenece a un grafo,
– determinar si una arista pertenece a un grafo,
– determinar si un grafo es vacío, y
– obtener el conjunto de vértices adyacentes a uno dado.

•

Las ecuaciones son las que hacen que el grafo sea dirigido o no.

Tema 6. Introducción a los esquemas 

algorítmicos

7

1.3 Especificación de grafos dirigidos

especificación GRAFOS[VÉRTICES]
usa BOOLEANOS, CONJUNTOS[VÉRTICES]
tipos grafo
operaciones

{ constructora }
{ constructora }
{ constructora }

grafo-vacío
añ-vértice
añ-arista
elim-vértice
elim-arista
está-vértice?
está-arista?
es-grafo-vacío?
adyacentes

→ grafo
→ grafo

:
: vértice grafo
: vértice vértice grafo → p grafo
: vértice grafo
: vértice vértice grafo → grafo
: vértice grafo
: vértice vértice grafo → bool
: grafo
: vértice grafo

variables

v,w, v′ ,w′ : vértice
g : grafo

→ grafo

→ bool

→ bool
→p conjunto[vértice]

Tema 6. Introducción a los esquemas 

algorítmicos

8

1.3 Especificación de grafos dirigidos

ecuaciones

añ-vértice(v, añ-vértice(v, g))
añ-vértice(w, añ-vértice(v, g))
añ-arista(v, w, g)

añ-arista(v,w, añ-arista(v, w, g))
añ-arista(v, w, añ-arista(v′, w′, g))
añ-arista(v, w, añ-vértice(v′, g))

elim-vértice(v, grafo-vacío)
elim-vértice(v, añ-vértice(v, g))
elim-vértice(v, añ-vértice(w, g))
elim-vértice(v, añ-arista(v, w, g))
elim-vértice(v, añ-arista(w, v, g))
elim-vértice(v, añ-arista(v′ ,w′, g))

= añ-vértice(v, g)
= añ-vértice(v, añ-vértice(w, g))

= error ⇐ ￢está-vértice?(v, g) ∨ ￢está-vértice?(w, g)
⇐ (v′ ≠ v∧ v′ ≠ w) ∨ (está-vértice?(v, g) ∧ está-vértice?(w, g))
= añ-vértice(w, elim-vértice(v, g)) ⇐ v ≠ w

= añ-arista(v, w, g)
= añ-arista(v′,w′, añ-arista(v, w, g))
= añ-vértice(v′, añ-arista(v, w, g))

= grafo-vacío
= elim-vértice(v, g)

= elim-vértice(v, g)
= elim-vértice(v, g)
= añ-arista(v′, w′, elim-vértice(v, g))

⇐ v ≠ v′ ∧ v ≠ w′

Tema 6. Introducción a los esquemas 

algorítmicos

9

1.3 Especificación de grafos dirigidos

elim-arista(v, w, grafo-vacío)
elim-arista(v, w, añ-vértice(v′, g))
elim-arista(v, w, añ-arista(v, w, g))
elim-arista(v, w, añ-arista(v′, w′, g))

está-vértice?(v, grafo-vacío)
está-vértice?(v, añ-vértice(w, g))
está-vértice?(v, añ-arista(v′, w′, g))

está-arista?(v, w, grafo-vacío)
está-arista?(v, w, añ-vértice(v′, g))
está-arista?(v, w, añ-arista(v′, w′, g))

= falso

= grafo-vacío
= añ-vértice(v′, elim-arista(v, w, g))
= elim-arista(v, w, g)
= añ-arista(v′, w′, elim-arista(v, w, g))

⇐ v ≠ v′ ∨ w ≠ w′
= v == w∨ está-vértice?(v, g)
= (v == v′ ∧ w == w′) ∨ está-arista?(v, w, g)

= está-vértice?(v, g)

= falso
= está-arista?(v, w, g)

Tema 6. Introducción a los esquemas 

algorítmicos

10

1.3 Especificación de grafos dirigidos

es-grafo-vacío?(grafo-vacío)
es-grafo-vacío?(añ-vértice(v, g))
es-grafo-vacío?(añ-arista(v, w, g))

adyacentes(v, g)
adyacentes(v, añ-vértice(v, g))
adyacentes(v, añ-vértice(w, g))
adyacentes(v, añ-arista(v, w, g))
adyacentes(v, añ-arista(v′, w′, g))

fespecificación

= cierto
= falso
= falso

= error
= cjto-vacío

⇐ ￢está-vértice?(v, g)
⇐ ￢está-vértice?(v, g)
= adyacentes(v, g) ⇐ v ≠ w∨ está-vértice?(v, g)
= adyacentes(v, g) ⇐ v ≠ v′

= añadir(w, adyacentes(v, g))

Tema 6. Introducción a los esquemas 

algorítmicos

11

1.4 Especificación de grafos no dirigidos

añ-arista(v, w, g)

= añ-arista(w, v, g)

elim-arista(v, w, grafo-vacío)
elim-arista(v, w, añ-vértice(v′, g))
elim-arista(v, w, añ-arista(v, w, g))
elim-arista(v, w, añ-arista(w, v, g))
elim-arista(v, w, añ-arista(v′, w′, g))

está-arista?(v, w, grafo-vacío)
está-arista?(v, w, añ-vértice(v′, g))
está-arista?(v, w, añ-arista(v′, w′, g))

= grafo-vacío
= añ-vértice(v′, elim-arista(v, w, g))
= elim-arista(v, w, g)
= elim-arista(v, w, g)
= añ-arista(v′, w′, elim-arista(v, w, g))

⇐ (v ≠ v′ ∨ w ≠ w′) ∧ (v ≠ w′ ∨ w ≠ v′)
= (v == v′ ∧ w == w′) ∨ (v == w′ ∧ w == v′ ) ∨

= falso
= está-arista?(v, w, g)

está-arista?(v, w, g)

Tema 6. Introducción a los esquemas 

algorítmicos

12

1.4 Especificación de grafos no dirigidos
⇐ ￢está-vértice?(v, g)
⇐ ￢está-vértice?(v, g)
= adyacentes(v, g) ⇐ v ≠ w∨ está-vértice?(v, g)
= adyacentes(v, g) ⇐ v ≠ v′ ∧ v ≠ w′

adyacentes(v, g)
adyacentes(v, añ-vértice(v, g))
adyacentes(v, añ-vértice(w, g))
adyacentes(v, añ-arista(v, w, g))
adyacentes(v, añ-arista(w, v, g))
adyacentes(v, añ-arista(v′, w′, g))

= error
= cjto-vacío

= añadir(w, adyacentes(v, g))
= añadir(w, adyacentes(v, g))

Tema 6. Introducción a los esquemas 

algorítmicos

13

1.5 Especificación de grafos valorados 
dirigidos

especificación GRAFOS-VALORADOS[VÉRTICES, VALORES]
usa BOOLEANOS, CONJUNTOS[VÉRTICES]
tipos grafo-val
operaciones
gv-vacío
gv-añ-vértice
gv-añ-arista
gv-valor
gv-elim-vértice
gv-elim-arista
gv-está-vértice?
gv-está-arista?
gv-es-vacío?
gv-adyacentes

→ grafo-val
:
→ grafo-val
: vértice grafo-val
: vértice vértice valor grafo-val →p grafo-val
: vértice vértice grafo-val
: vértice grafo-val
: vértice vértice grafo-val
: vértice grafo-val
: vértice vértice grafo-val
: grafo-val
: vértice grafo-val

variables

v, w, v′, w′ : vértice
p, q, p′ : valor
g : grafo-val

{ constructora }
{ constructora }
{ constructora }

→p valor
→ grafo-val
→ grafo-val
→ bool
→ bool
→ bool
→p conjunto[vértice]

Tema 6. Introducción a los esquemas 

algorítmicos

14

1.5 Especificación de grafos valorados 
dirigidos

ecuaciones

gv-añ-vértice(v, gv-añ-vértice(v, g))
gv-añ-vértice(w, gv-añ-vértice(v, g))
gv-añ-arista(v, w, p, g)

= gv-añ-vértice(v, g)
= gv-añ-vértice(v, gv-añ-vértice(w, g))

= error ⇐ ￢gv-está-vértice?(v, g) ∨ ￢gv-está-vértice?(w, g)
⇐ (v′ ≠ v∧ v′ ≠ w) ∨ (gv-está-vértice?(v, g) ∧ gv-está-vértice?(w, g))

⇐ v ≠ v′ ∨ w ≠ w′

gv-añ-arista(v, w, p, gv-añ-arista(v, w, q, g)) = gv-añ-arista(v, w, p, g)
gv-añ-arista(v, w, p, gv-añ-arista(v′, w′, p′, g)) = gv-añ-arista(v′, w′, p′, gv-añ-arista(v, w, p, g))

gv-añ-arista(v, w, p, gv-añ-vértice(v′, g)) = gv-añ-vértice(v′, gv-añ-arista(v, w, p, g))

gv-valor(v, w, gv-vacío)
gv-valor(v, w, gv-añ-vértice(v′, g))
gv-valor(v, w, gv-añ-arista(v, w, p, g))
gv-valor(v, w, gv-añ-arista(v′, w′, p′, g))
…

= error
= gv-valor(v, w, g)
= p

= gv-valor(v, w, g) ⇐ v ≠ v′ ∨ w ≠ w′

Tema 6. Introducción a los esquemas 

algorítmicos

15

2.

Algoritmos de ordenación

•

•

•

La ordenación o clasificación de datos (sort, en inglés) es una operación 
consistente en disponer un conjunto (estructura) de datos en algún 
determinado orden con respecto a uno de los campos de elementos del 
conjunto.

El orden de clasificación