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

Imágen de pdf Tema 6. Introducción a los esquemas algorítmicos - Estructuras de Datos y Algoritmos

Tema 6. Introducción a los esquemas algorítmicos - Estructuras de Datos y Algoritmosgráfica de visualizaciones

Publicado el 12 de Enero del 2019
299 visualizaciones desde el 12 de Enero del 2019. Una media de 14 por semana
482,9 KB
42 paginas
Creado hace 4a (08/05/2015)
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
  • Links de descarga
http://lwp-l.com/pdf14836

Comentarios de: Tema 6. Introducción a los esquemas algorítmicos - Estructuras de Datos y Algoritmos (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad

Revisar política de publicidad