Grafos

Sumario
•Definiciones y terminología
•Servicios del TDA grafo
•Algoritmos para el recorrido
–En profundidad
–A lo ancho
•Algunas estructuras de datos
para la representación de
grafos
Bibliografía

- Estructura de datos y algoritmos.

Aho, HopcroPt y Ullman.

- Fundamentals of data strutures.

Horowitz & Sahni.

Los grafos son el mecanismo más
general para la codificación de
interrelaciones entre objetos. La
versatilidad de los grafos les
permiten representar los
problemas más difíciles desde el
punto de vista teórico en las
ciencias de la computación.
En computación los grafos pueden
ser de dos formas:
– Grafos explícitos donde todas las
componentes del grafo existen en
la memoria de la computadora
– Grafos implícitos cuando no es
posible que el grafo como tal exista
representado completamente en la
memoria de una computadora
Definición de grafo,
grafo dirigido y
grafo ponderado
• Un grafo G es un par (V,E), donde
V es conjunto de elementos que se
denominan vértices y E es un
conjunto de pares no ordenados
<x,y> denominados arcos (aristas)
donde xV y yV.
Ejemplo de grafo
G = (V, E)
• V = {A,B,C,D,E}.
• E ={<A,B>, <A,E>, <B,D>, <B,E>, <C,D>,
<C,E>, <D,E>}
A B

C D
• Un grafo Dirigido G es un par
(V,E), donde V es conjunto
de elementos que se
denominan vértices y E es un
conjunto de pares ordenados
(x,y)VxV, denominados
arcos dirigidos.
Ejemplo de grafo dirigido
G = (V, E)
• V = {A,B,C,D,E}.
• E ={(A,B), (A,E), (B,D), (B,E), (C,D), (C,E),
(D,E)}
A B

C D
• Un grafo (Dirigido) ponderado
G es un Grafo (Dirigido) en
que cada una de las aristas
tiene asignada un peso.
5
A B
8 4
E 10
11 6
3
C D
Terminología
– Vértices adyacentes
– Caminos. Camino simple
– Longitud de un camino
– Ciclo. Bucle
– Grafo conectado o conexo
Vértices adyacentes. Dos
vértices v y u son
adyacentes si ellos forman
un arco Vértices adyacentes
A I

D J
B C

E F G H
Camino. Un camino de longitud
n (n>=0) es una sucesión de
vértices
v0, v1, ..., vn,
donde cada vértice vk-1 es
adyacente a vk, para 1=< k <=n;
en este caso se dice que el
camino va desde vo a vn.
 A I

D J
B C

E F G H

Camino: CFEBCADG
Camino simple. Un camino
es simple si los vértices
que lo componen son
distintos excepto
posiblemente el primero y
el último.
 A I

D J
B C

E F G H

Camino Simple: BCADG

Longitud de un camino. La
longitud de un camino es el
número de arcos que lo
componen
 A I

D J
B C

E F G H

La Longitud del camino BCADG es 4

Un ciclo (o circuito) es un
camino que empieza y
acaba en el mismo
vértice. Los ciclos de
longitud 1 se denominan
los bucles
 Ciclo: CFEBC

A TI

D J
B C

E F G H

Ciclo: CFEBC Bucle: T T

• Grafo conectado (conexo).
Un grafo es conectado si
existe al menos un camino
de cualquier vértice a
cualquier otro.
 A I

D J
B C

E F G H

Este grafo no es conexo

ya que de A no se puede llegara a J
Descripción de los
algoritmos de
recorridos
Recorrido en
profundidad
RecorrerEnProfundidad
• Para cada vєV marcar v
como no visitado
• Para cada vєV hacer
– Si v no esta visitado
entonces BPP(v)
BPP(v) /* el vértice v no esta visitado
• Marcar v como visitado
• Para cada w adyacente a v
hacer
– Si w no esta visitado
entonces BPP(v)
 A I

B C D J

E F G H

Marcar todos como no visitados

A I

B C D J

E F G H

BPP(v)
1BPP(A) A I

B C D J

E F G H

Recorrido
A,
1BPP(A) A I

1.1BPP(B) D J
B C

E F G H

Recorrido
A,B,
1BPP(A) A I
1.1BPP(B)
B C D J
1.1.1BPP(C)

E F G H

Recorrido
A,B,C
1BPP(A) A I

1.1BPP(B)
B C D J
1.1.1BPP(C)
1.1.1.1BPP(F)
E F G H

Recorrido
A,B,C,F,
1BPP(A) A I

1.1BPP(B)
B C D J
1.1.1BPP(C)
1.1.1.1BPP(F)
E F G H
1.1.1.1.1BPP(E)

Recorrido
A,B,C,F,E,
1BPP(A) A I

1.1BPP(B)
B C D J
1.1.1BPP(C)
1.1.1.1BPP(F)
E F G H
1.1.1.1.1BPP(E)

Todos los adyacentes a E están visitados

Recorrido
A,B,C,F,E,
 A I
1BPP(A)
1.1BPP(B) J
B C D
1.1.1BPP(C)
1.1.1.1BPP(F)
E F G H
1.1.1.1.1BPP(E)

Recorrido
A,B,C,F,E,
1BPP(A) A I

1.1BPP(B)
B C D J
1.1.1BPP(C)
1.1.1.1BPP(F)
E F G H
1.1.1.1.1BPP(E)

Todos los adyacentes a F están visitados

Recorrido
A,B,C,F,E,
1BPP(A) A
I
1.1BPP(B)
B C D J
1.1.1BPP(C)
1.1.1.1BPP(F)
E F G H
1.1.1.1.1BPP(E)

Recorrido
A,B,C,F,E,
 A I
1BPP(A)
1.1BPP(B) B C D J
1.1.1BPP(C)
1.1.1.1BPP(F) E F G H
1.1.1.1.1BPP(E)

Todos los adyacentes a C están visitados

Recorrido
A,B,C,F,E,
 A
1BPP(A) I

1.1BPP(B)
B C D J
1.1.1BPP(C)
1.1.1.1BPP(F) H
E P
F G
1.1.1.1.1BPP(E)

Recorrido
A,B,C,F,E,
1BPP(A) A I

1.1BPP(B)
J
B C D
1.1.1BPP(C)
1.1.1.1BPP(F)
E F G H
1.1.1.1.1BPP(E)

Todos los adyacentes a B [ E,C yA] están visitados

Recorrido
A,B,C,F,E,
1BPP(A) A I

1.1BPP(B)
B C D J
1.1.1BPP(C)
1.1.1.1BPP(F)
E F G H
1.1.1.1.1BPP(E)

Recorrido
A,B,C,F,E,
1BPP(A) A I

1.1BPP(B)
B C D J
1.1.1BPP(C)
1.1.1.1BPP(F)
E F G H
1.1.1.1.1BPP(E)

Hay un adyacentes a A no visitado

Recorrido
A,B,C,F,E,
 A I
1BPP(A)
1.1BPP(B) J
B C D
1.1.1BPP(C)
1.1.1.1BPP(F) H
E F G
1.1.1.1.1BPP(E)
1.2BPP(D)

Recorrido
A,B,C,F,E,D,
 A
1BPP(A) I

1.1BPP(B)
B C D J
1.1.1BPP(C)
1.1.1.1BPP(F) H
E F G
1.1.1.1.1BPP(E)
1.2BPP(D)
1.2.1BPP(G)

Recorrido
A,B,C,F,E,D,G,
 A I
1BPP(A)
1.1BPP(B) J
B C D
1.1.1BPP(C)
1.1.1.1BPP(F) H
E F G
1.1.1.1.1BPP(E)
1.2BPP(D)
1.2.1BPP(G)
1.2.1.1BPP(H)
Recorrido
A,B,C,F,E,D,G,H,
1BPP(A) A I

1.1BPP(B)
B C D J
1.1.1BPP(C)
1.1.1.1BPP(F)
E F G H
1.1.1.1.1BPP(E)
1.2BPP(D)
1.2.1BPP(G)
1.2.1.1BPP(H)
Todos los adyacentes a H están visitados
Recorrido
A,B,C,F,E,D,G,H,
1BPP(A) A I

1.1BPP(B)
B C D J
1.1.1BPP(C)
1.1.1.1BPP(F)
E F G H
1.1.1.1.1BPP(E)
1.2BPP(D)
1.2.1BPP(G)
1.2.1.1BPP(H)

Recorrido
A,B,C,F,E,D,G,H,
 A
1BPP(A) I

1.1BPP(B)
B C D J
1.1.1BPP(C)
1.1.1.1BPP(F) H
E F G
1.1.1.1.1BPP(E)
1.2BPP(D)
1.2.1BPP(G)
1.2.1.1BPP(H)
Todos los adyacentes a G están visitados
Recorrido
A,B,C,F,E,D,G,H,
 A
1BPP(A) I

1.1BPP(B)
B C D J
1.1.1BPP(C)
1.1.1.1BPP(F) H
E F G
1.1.1.1.1BPP(E)
1.2BPP(D)
1.2.1BPP(G)
1.2.1.1BPP(H)
Recorrido
A,B,C,F,E,D,G,H,
 A
1BPP(A) I

1.1BPP(B)
B C D J
1.1.1BPP(C)
1.1.1.1BPP(F) H
E F G
1.1.1.1.1BPP(E)
1.2BPP(D)
1.2.1BPP(G)
1.2.1.1BPP(H)
Todos los adyacentes a D están visitados

Recorrido
A,B,C,F,E,D,G,H,
 A I
1BPP(A)
1.1BPP(B) B C D J
1.1.1BPP(C)
1.1.1.1BPP(F) E F G H
1.1.1.1.1BPP(E)
1.2BPP(D)
1.2.1BPP(G)
1.2.1.1BPP(H)
Recorrido
A,B,C,F,E,D,G,H,
1BPP(A) A
I
1.1BPP(B)
B C D J
1.1.1BPP(C)
1.1.1.1BPP(F)
E F G H
1.1.1.1.1BPP(E)
1.2BPP(D)
1.2.1BPP(G)
1.2.1.1BPP(H)
Todos los adyacentes a A están visitados
Recorrido
A,B,C,F,E,D,G,H,
RecorrerEnProfundidad
• Para cada vєV hacer
– Si v no esta visitado entonces BPP(v)
BPP(A) BPP(I)
A
I

B C D J

E F G H
 A
1BPP(A) I

1.1BPP(B) B C D J
1.1.1BPP(C)
1.1.1.1BPP(F) E F G H

1.1.1.1.1BPP(E)
1.2BPP(D)
1.2.1BPP(G)
1.2.1.1BPP(H)
Recorrido
2BPP(I) A,B,C,F,E,D,G,H,I,
 A
1BPP(A) I

1.1BPP(B) B C D J
1.1.1BPP(C)
1.1.1.1BPP(F) E F G H

1.1.1.1.1BPP(E)
1.2BPP(D)
1.2.1BPP(G)
1.2.1.1BPP(H)
Recorrido
2BPP(I) A,B,C,F,E,D,G,H,I,J
2.1BPP(j)
 A
1BPP(A) I

1.1BPP(B) B C D J
1.1.1BPP(C)
1.1.1.1BPP(F) E F G H

1.1.1.1.1BPP(E)
1.2BPP(D)
1.2.1BPP(G) Todos los adyacentes a J
1.2.1.1BPP(H) están visitados
2BPP(I)
Recorrido
2.1BPP(j) A,B,C,F,E,D,G,H,I,J
 A
1BPP(A) I

1.1BPP(B) B C D J
1.1.1BPP(C)
1.1.1.1BPP(F) E F G H

1.1.1.1.1BPP(E)
1.2BPP(D)
1.2.1BPP(G)
1.2.1.1BPP(H)
2BPP(I)
Recorrido
2.1BPP(j) A,B,C,F,E,D,G,H,I,J
 A
1BPP(A) I

1.1BPP(B) B C D J
1.1.1BPP(C)
1.1.1.1BPP(F) E F G H

1.1.1.1.1BPP(E)
1.2BPP(D)
1.2.1BPP(G)
Todos los adyacentes a I
1.2.1.1BPP(H) están visitados
2BPP(I)
Recorrido
2.1BPP(j) A,B,C,F,E,D,G,H,I,J
RecorrerEnProfundidad
• Para cada vєV hacer
– Si v no esta visitado entonces BPP(v)
A
I

B C D J

E F G H

Como todos los vértices han sido

visitados el algoritmo termina
Recorrido a lo
ancho
RecorrerALo Ancho
Para cada vєV marcar v como no
visitado
Para cada vєV hacer
• Si v no esta visitado
entonces BPA(v)
 BPA(v) /* el vertice v no esta visitado
• Ccola ← Ø
• Marcar v como visitado
• Insertar v en Ccola
• Mientras Ccola no es vacía hacer
– u← Frente de Ccola y elimino u de Ccola
– Para cada w adyacente a u hacer
• Si w no esta visitado entonces
Marcar w como visitado
Insertar w en CCola
 A

B C D

E F G H

Marcar todos como no visitados

A

B C D

E F G H

BPA(v)
BPA(A) IF
• Ccola ← Ø
• Se Marca A como
visitado A
F I
• Se Inserta A en
Ccola
A
A

B C D

H
Recorrido
E F G
A,
 F I
Como Ccola no es vacía
u← A
A
FI
elimino A de Ccola
A

B C D

E F G H

Ady(A)={ B,C,D}
 FI
Cada Ady(A)={ B,C,D}
Se Marca como visitado

F I
Se Insertan en Ccola
B C D
A

B C D

Recorrido,
E F G H
A,B,C,D,
 F I
Como Ccola no es vacía
u← B y
B C D
elimino B de Ccola F I

A
C D
B C D

E F G H

Para cada Ady(B)={A,C,E}

 F I
Para Ady(B)={ A,E,C}
El no visitado E se marca
como visitado C D
F I
Se Inserta E en Ccola
C D E
A

B C D

Recorrido,
E F G H
A,B,C,D,E,
Como Ccola no es vacía F I
u← C
C D E
elimino C de Ccola
F I
A

D E
B C D

E F G H

Para cada Ady(C)={A,B,F}

 F I
Para Ady(C)={ A,B,F}
El no visitado F se marca
como visitado D E

F I
Se Inserta F en Ccola

A D E F

B C D

Recorrido,
E F G H
A,B,C,D,E,F,
 F I
Como Ccola no es vacía
u← D
D E F

elimino D de Ccola F I
A

E F
B C D

E F G H

Para cada Ady(D)={A,G,H}

 F I
Para Ady(D)={ A,G,H}
Los no visitados G y H E F
se marcan como visitados
F I
Se Insertan G y H en Ccola
E F GH
A

B C D

H
Recorrido,
E F G
A,B,C,D,E,F,G,H
Como Ccola no es vacía F I
u← E

elimino E de Ccola E F G H
A
F I

B C D
F G H
E F G H

Como los Ady(E)={B,F}

fueron visitados no se hace
nada
Como Ccola no es vacía F I
u← F
F G H
Elimino F de Ccola F I
A

D
G H
B C

E F G H

Como los Ady(F)={C,E}

fueron visitados no se hace
nada
 F I
Como Ccola no es vacía
u← G
G H
Elimino G de Ccola
A
F I

B C D
H
E F G H

Como los Ady(G)={D,H}

fueron visitados no se hace
nada
Como Ccola no es vacía F I
u← H
H
H
Elimino H de Ccola
FI
A

B C D

E F G H
Como los Ady(H)={D,G}
fueron visitados no se hace
nada
RecorrerALoAncho
• …..
• Mientras Ccola no es vacía hacer
• // un conjunto de instrucciones//
FI

Como Ccola es vacía el algoritmo termina

Recorrido,
A,B,C,D,E,F,G,H
 Estructuras de
datos para la
representación de
grafos
Lista de vértices y
Matriz de adyacencia
Para el grafo G=(V,E) A B
la representación de
Lista de vértices y E
matriz de adyacencia
C D
es:
1 2 3 4 5
A B C D E
1 2 3 4 5
1 0 1 0 0 1
2 1 0 0 1 1 1 si i ady j
G= 3 0 0 0 1 1 Gi,j =
4 0 1 1 0 1 0 si i no ady j
5 1 1 1 1 0
 Lista de vértices y
Lista de adyacencia
 A B
Para el grafo G=(V,E)
la representación de
Lista de vértices y E
listas de adyacencia C D
es:
A 2 5

B 1 4 5

C 4 5

D 2 3 5

E 1 2 3 4
Dado el siguiente grafo:

• a) Identifica los caminos simples que

existen entre el vértice a y f
• b) ¿Es conexo el grafo?
• c) Realice el recorrido en
profundidad y el recorrido a lo
ancho.
• d) Represéntelo usando las
representaciones Lista de Vértices –
Matriz de Adyacencia y Lista de
• Vértices – Lista de Adyacencia.
Muchas gracias