Tipos de datos abstractos

Material didáctico
Tema
Grafos
Marcos Venegas y Karol Sánchez

Un grafo está compuesto de vértices (también llamados nodos) y de relaciones entre vértices. Los
grafos son muy utilizados en las matemáticas y en las ciencias de la computación. Aunque
prácticamente cualquier problema puede representarse mediante grafos, pues representa relaciones
binarias entre elemento.

En el siguiente material se explican los grafos, grafos dirigidos y grafos no dirigidos. Se abordan los
conceptos de camino, grado, grados de entrada y de salida.

En lo que respecta a los grafos dirigidos se estudian las representaciones a través de la matriz de
adyacencia y la lista de adyacencia. Se abordan el problema de los caminos más cortos con un solo
origen y el problema de los caminos más cortos entre todos los pares. Para ello se exponen las
soluciones propuestas por (Dijkstra, 1959) Dijkstra, que soluciona el primer problema y se explican los
trabajos de (Floyd, 1962) Floyd y (Warshall,1962) Warshall para resolver el segundo. Todos citados
por (Aho et al.,1988) Aho.

En relación a los grafos no dirigidos también se estudian las representaciones a través de la matriz de
adyacencia y la lista de adyacencia. Se realiza una introducción a árboles abarcadores de costo mínimo
y se analizan las técnicas propuestas por (Prim , 1957) Prim, y ( Kruscal , 1956) Kruscal para
construirlos.

2
 Tipos de datos abstractos

Material didáctico
Grafos

Un grafo G agrupa entes físicos o conceptuales y las relaciones entre ellos. Está conformado por un
conjunto de vértices o nodos V, que representa a los entes, y un conjunto de arcos A, que representan
las relaciones entre vértices.

Se representa con el par G = (V,A).

Muestra un grafo formado por:

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

Un arco o arista representa una relación entre dos nodos. Esta relación, al estar formada por dos nodos,
se representa por (u,v) siendo u,v el par de nodos.

Un grafo es no dirigido, si los arcos están formados por pares de nodos no ordenados, no apuntados.
Se representa con un segmento uniendo los nodos, u—v.

Ejemplo:

Un grafo es dirigido, también denominado digrafo, si los pares de nodos que forman los arcos son
ordenados.

Se representa con una flecha que indica la dirección de la relación, u → v.

Ejemplo:

3
 Tipos de datos abstractos

Material didáctico
Muestra un grafo formado por:
V= {C, D, E, F, H }
A ={ (C,D), (D,F), (E,H), (H,E), (E,C)}

Dado el arco (u, v) de un grafo, se dice que los vértices u y v son adyacentes.

Grafo valorado

En los modelos realizados con grafos, a veces, una relación entre dos nodos tiene asociada una
magnitud, denominada factor de peso, en cuyo caso se dice que es un grafo valorado.

Ejemplo:
Los pueblos que forman una comunidad junto con la relación entre un par de pueblos que están unidos
por un camino: esta relación tiene asociado el factor de peso, que es la distancia en kilómetros.

Grado

El grado es una cualidad que se refiere a los nodos de un grafo.

En un grafo no dirigido, el grado de un nodo v, grado(v), es el número de arcos que contienen a v.
Ejemplo:
Grado(Mojón) = 2.

Grado de entrada y salida

En un grafo dirigido se distingue entre grado de entrada y grado de salida:

• Grado de entrada de un nodo v, gradent (v): es el número de arcos que llegan a v.
• Grado de salida de v, gradsal(v): es el número de arcos que salen de v.

4
 Tipos de datos abstractos

Material didáctico
Ejemplo:

• Gradent (D) = 1
• Gradsal (E) = 2

Camino

Un camino P de longitud n desde el vértice v0 a vn en un grafo G, es la secuencia de n+1 vértices v0,

v1, v2, ..., vn.
La longitud del camino es el número de arcos que lo forma.
Ejemplo:
• P1 = (4, 6, 9, 7) es un camino de longitud 3.
• P2 = (10, 11) es un camino de longitud 1.

En un grafo valorado, la longitud del camino con pesos es la suma de los pesos de los arcos en el
camino.

Ejemplo:
El camino (Mojón, Espíritu Santo, Macacona) tiene la longitud 5 + 3 = 8.

Un camino es simple si todos los nodos que forman el camino son distintos.
En un grado dirigido, un ciclo es un camino simple cerrado. Por tanto, un ciclo empieza y termina en el
mismo nodo, v0=v1, y además, debe tener más de un arco.

Un grafo dirigido sin ciclos se denomina GDA = Grafo Dirigido Acíclico.

5
 Tipos de datos abstractos

Material didáctico
Grafos dirigidos

Un grafo dirigido G consiste en un conjunto de vértices V y un conjunto de arcos A. Los vértices de un

grafo dirigido pueden usarse para representar objetos, y los arcos, relaciones entre los objetos. Por
ejemplo, los vértices pueden representar ciudades, y los arcos, vuelos aéreos de una ciudad a otra. Otro
ejemplo puede ser utilizar un grafo dirigido para representar el flujo de control en un programa de
computadora, los vértices representan los bloques básicos, y los arcos, posibles transferencias del flujo
de control.

Representaciones de grafos dirigidos

Para representar un grafo dirigido se pueden emplear varias estructuras de datos; la selección apropiada
depende de las operaciones que se aplicarán a los vértices y a los arcos del grafo.

a. Matriz de adyacencia.
La matriz de adyacencia para G es una matriz A de dimensión nxn, de elementos booleanos, donde
A[i,j] es verdadero si, y sólo si, existe un arco que vaya del vértice i al j. Con frecuencia se utilizarán
matrices de adyacencias con 1 para verdadero y 0 para falso.

La representación con matriz de adyacencia es útil en los algoritmos para grafos, en los cuales suele ser
necesario saber si un arco dado está presente.

Algo muy relacionado en este tipo de representación es la matriz de adyacencia etiquetada de un grafo
dirigido, donde A[i,j] es la etiqueta del arco que va del vértice i al vértice j. Si no existe un arco de i a j,
debe emplearse como entrada para A[i,j] un valor que no pueda ser una etiqueta válida.

Ejemplo de grafo dirigido con su representación de matriz de adyacencia etiquetada.

a
1 a 2
b

b
b

a
4 a 3

Una desventaja que tiene este tipo de representación es que tiene un tiempo de duración mayor.
Solo examinar o leer la matriz puede llevar un tiempo O( n2 ).

6
 Tipos de datos abstractos

Material didáctico
b. Lista de adyacencia
Otro método de representación es la lista de adyacencia. La lista de adyacencia para un vértice i
es una lista, en algún orden, de todos los vértices adyacentes a i.
La representación de un grafo dirigido con lista de adyacencia requiere un tiempo de O(n).

Ejemplo:

Problema de los caminos más cortos con un solo origen.

Supóngase un grafo dirigido G=(V,A) en el cual cada arco tiene una etiqueta no negativa, y donde un
vértice se especifica como origen. El problema es determinar el costo del camino más corto del origen a
todos los demás vértices de V, donde la longitud de un camino es la suma de los costos de los arcos del
camino. Esto se conoce con el nombre de problema de los caminos más cortos con un solo origen.

Sea G un mapa de vuelos en el cual cada vértice representa una ciudad, y cada arco v ---> w, una ruta
aérea de la ciudad v a la ciudad w. La etiqueta del arco es el tiempo que se requiere para volar de v a w.
La solución del problema de los caminos más cortos con un solo origen para este grafo dirigido
determinaría el tiempo de viaje mínimo para ir de cierta ciudad a todas las demás del mapa.

Para resolver este problema se manejará una técnica conocida como algoritmo de Dijkstra, que opera a
partir de un conjunto S de vértices cuya distancia más corta desde el origen ya es conocida. En
principio, S contiene sólo el vértice de origen. En cada paso, se agrega algún vértice restante v a S,
cuya distancia desde el origen es la más corta posible. Suponiendo que todos los arcos tienen costo no
negativo, siempre es posible encontrar un camino más corto entre el origen y v que pasa sólo a través
de los vértices de S. En cada paso del algoritmo, se utiliza un arreglo D para registrar la longitud del
camino especial más corto a cada vértice. Una vez que S incluye todos los vértices, todos los caminos
son “especiales”, así que D contendrá la distancia más corta del origen a cada vértice.

El algoritmo supone que existe un grafo dirigido G=(V,A) en el que V={1,2,3 …, n} y el vértice 1 es el
origen. C es un arreglo bidimensional de costos donde C[i,j] es el costo de ir del vértice i al al vértice j
por el arco i → j. Si no existe el arco i → j se supone que C[i,j] es ∞, un valor mucho mayor que
cualquier costo real. En cada paso, D[i] contiene la longitud del camino especial más corto actual para
el vértice i.

7
 Tipos de datos abstractos

Material didáctico
Grafo Considere la siguiente matriz C:

1 2 3 4 5
1 ∞ 10 ∞ 30 100
2 ∞ ∞ 50 ∞ ∞
3 ∞ ∞ ∞ ∞ 10
4 ∞ ∞ 20 ∞ 60
5 ∞ ∞ ∞ ∞ ∞

Inicialmente S contiene el origen.

En la primera iteración el vector D contendrá como valores iniciales la distancia del origen (vértice 1) a
cada vértice si el arco existe. Si no tendrá el valor ∞.

Iteración S w D[2] D[3] D[4] D[5]

Inicial {1} _ 10 ∞ 30 100

Para seleccionar el vértice w a agregar en S se escoge el vértice con el mínimo valor en el vector D. El
min(10, ∞, 30, 100) es 10 y pertenece al vértice 2. Por lo que se elige en la siguiente iteración como
vértice w a 2, y se agrega al conjunto S. El nuevo valor en cada posición del vector D estará dado por
la siguiente fórmula: D[v]=min(D[v],D[w]+C[w,v]). Se consideran solamente aquellos vértices que no
están en S, pues los que están en S ya están identificados como vértices con distancia mínima.
Entonces, se omite la comparación para D[2].

w=2
Fórmula D[v]=min(D[v],D[w]+C[w,v])
Para v=3 D[3]=min(D[3], D[2]+C[2,3]), (recuerde que arriba puede observar la matriz C[fila,columna])
D[3]=min(∞ , 10 + 50 )
D[3]=60

Para v=4 D[4]=min(D[4], D[2]+C[2,4]),

D[4]=min(30 , 10 + ∞ )
D[4]=30

Para v=5 D[5]=min(D[5], D[2]+C[2,5]),

D[5]=min(100 , 10 + ∞ )
D[5]=100

8
 Tipos de datos abstractos

Material didáctico
Iteración S w D[2] D[3] D[4] D[5]
Inicial {1} _ 10 ∞ 30 100
1 {1,2} 2 10 60 30 100

Para elegir el vértice w se debe encontrar el menor de elemento de la tabla, excluyendo los vertices que
se encuentran en S. Por el momento solo se encuentran en S el origen y el vértice 2, el min(60, 30, 100)
es 30. Entonces, el vértice w será 4 y se agrega al conjunto S. Se consideran solamente aquellos
vértices que no están en S, pues los que están en S ya están identificados como vértices con distancia
mínima. Entonces, se omite la comparación para D[2] y para D[4].

w=4
Fórmula D[v]=min(D[v],D[w]+C[w,v])
Para v=3 D[3]=min(D[3], D[4]+C[4,3]), (recuerde que arriba puede observar la matriz C[fila,columna])
D[3]=min( 60, 30 + 20 )
D[3]=50

Para v=5 D[5]=min(D[5], D[4]+C[4,5]),

D[5]=min(100 , 30 + 60 )
D[5]=90

Iteración S w D[2] D[3] D[4] D[5]

Inicial {1} _ 10 ∞ 30 100
1 {1,2} 2 10 60 30 100
2 {1,2,4} 4 10 50 30 90

En esta iteración w es 3.

Fórmula D[v]=min(D[v],D[w]+C[w,v])
Para v=5 D[5]=min(D[5], D[3]+C[3,5]),
D[5]=min(90 , 50 + 10 )
D[5]=60

Iteración S w D[2] D[3] D[4] D[5]

Inicial {1} _ 10 ∞ 30 100
1 {1,2} 2 10 60 30 100
2 {1,2,4} 4 10 50 30 90
3 {1,2,4,3} 3 10 50 30 60

9
 Tipos de datos abstractos

Material didáctico
Finalmente, w es 5.

Iteración S w D[2] D[3] D[4] D[5]

Inicial {1} _ 10 ∞ 30 100
1 {1,2} 2 10 60 30 100
2 {1,2,4} 4 10 50 30 90
3 {1,2,4,3} 3 10 50 30 60
4 {1,2,4,3,5} 5 10 50 30 60

Problema de los caminos más cortos entre todos los pares.

Suponga que se tiene un grafo dirigido etiquetado que da el tiempo de vuelo para ciertas rutas entre
ciudades, y se desea construir una tabla que brinde el menor tiempo requerido para volar entre dos
ciudades cualesquiera. El problema es encontrar el camino de longitud más corta entre v y w para cada
par ordenado de vértices (v,w).

Podría resolverse este problema por medio del algoritmo de Dijkstra, tomando por turno cada vértice
como vértice origen, pero una forma más directa de solución es mediante el algoritmo de Floyd.

El algoritmo de Floyd usa una matriz A de n x n, en la que se calculan las longitudes de los caminos
más cortos. Inicialmente se hace A[i,j] = C[i,j] para toda i diferente a j. Si no existe un arco que vaya de
i a j, se supone que C[i,j] = ∞. Cada elemento de la diagonal se hace 0.

Después, se hacen n iteraciones en la matriz A. Al final de la k-ésima iteración, A[i,j] tendrá por valor
la longitud más pequeña de cualquier camino que vaya desde el vértice i hasta el vértice j y que no pase
por un vértice con número mayor que k. Esto es, i y j, los vértices extremos del camino, pueden ser
cualquier vértice, pero todo vértice intermedio debe ser menor o igual que k. En la k-ésima iteración se
aplica la siguiente fórmula para calcular A.

En cada iteración se aplica la siguiente fórmula:

Ak-1 [ i, j ]
Ak [ i, j ] = mín
Ak-1 [ i, k ] + Ak-1 [ k, j ]

El subíndice k denota el valor de la matriz A

10
 Tipos de datos abstractos

Material didáctico
C=
1 2 3
1 2 8 5
2 3 ∞ ∞
3 ∞ 2 ∞

A0[i,j]
1 2 3 A0 es la matriz inicial (la base para realizar el algoritmo de Floyd), es igual a la
1 0 8 5 matriz de costos C, solo que la diagonal se hace 0. En todas las matrices, la
2 3 0 ∞ diagonal siempre es 0.
3 ∞ 2 0

A1 (Para calcular A1, se mantiene la fila y la columna 1 de la matriz anterior)

1 2 3 A1 [2,3]= min A0 [2,3]= ∞

1 0 8 5 A0 [2,1]+ A0 [1,3] = 3 + 5 = 8
2 3 0 8
3 ∞ 2 0 A1 [3,2]= min A0 [3,2]= 2
A0 [3,1]+ A0 [1,2] = ∞ + 8 = ∞

A2
A2 [1,3]= min A1 [1,3]= 5
1 2 3 A1 [1,2]+ A1 [2,3] = 8 + 8 = 16
1 0 8 5
2 3 0 8 A2 [3,1]= min A1 [3,1]= ∞
3 5 2 0 A1 [3,2]+ A1 [2,1] = 2 + 3 = 5

A3

1 2 3 A3 [1,2]= min A2 [1,2]= 8

1 0 7 5 A2 [1,3]+ A2 [3,2] = 5 + 2 = 7
2 3 0 8
A3 [2,1]= min A2 [2,1]= 3
3 5 2 0
A2 [2,3]+ A2 [3,1] = 8 + 5 = 13

11
 Tipos de datos abstractos

Material didáctico
Cerradura Transitiva

Supóngase que la matriz de costo C es sólo la matriz de adyacencia para el grafo dirigido dado.
Esto es, C[i,j] = 1 si hay un arco de i a j, y 0 si no lo hay.
También se conoce como cerradura transitiva de la matriz de adyacencia.

1 2 3 Se conoce también como

1 0 1 1 Algoritmo de Warshall
2 1 0 1
3 1 1 0

Localización del centro de un grafo dirigido

Supóngase que se desea determinar el vértice más central de un grafo dirigido. Este problema se puede
resolver fácilmente con el algoritmo de Floyd. Primero se hace más preciso el término “vértice más
central”. Sea v un vértice de un grafo dirigido G= (V,A). La excentricidad de v es:
max {longitud mínima de un camino de w a v}
w en V

El centro de G es un vértice de mínima excentricidad. Así, el centro de un grafo dirigido es un vértice

más cercano al vértice más distante.
a
1

b
2 1
2

c 3 d
4 5
e

b c d e a
ab=1 ac=3 ad=5 ae=7 ba=∞ Se escogen los valores más altos de cada
cb=3 bc=2 bd=4 be=6 ca=∞ vértice.
db=1 dc=3 cd=2 ce=4 da=∞
eb=6 ec=8 ed=5 de=7 ea=∞

12
 Tipos de datos abstractos

Material didáctico
Las excentricidades de los vértices son:

vértice excentricidad
a ∞ Por tanto, el centro es el vértice d.
b 6
c 8
d 5 Se escoge el vértice con menor valor.
e 7

Práctica:
Dado el siguiente grafo:

1. Obtenga, por medio del algoritmo de Dijkstra, el camino más corto del vértice “a” hacia todos los
demás.
2. Obtenga, por medio del algoritmo de Floyd, el camino más corto entre todos los vértices.
3. Encuentre el centro del grafo.

13
 Tipos de datos abstractos

Material didáctico
Grafos no dirigidos

Un grafo no dirigido G=(V,A) consta de un conjunto finito de vértices V y de un conjunto de aristas A.

Se diferencia de un grafo dirigido en que cada arista en A es un par no ordenado de vértices. Si (v,w) es
una arista no dirigida, entonces (v,w)=(w,v).

Los grafos se emplean en distintas disciplinas para modelar relaciones simétricas entre objetos. Los
objetos se representan por los vértices del grafo, y dos objetos están conectados por una arista si están
relacionados entre sí.

Buena parte de la terminología para grafos dirigidos es aplicable también a los no dirigidos. Por
ejemplo, los vértices v y w son adyacentes si (v,w) ó (w,v) es una arista.

Un camino es una secuencia de vértices v1,v2,...,vn tal que (vi, vi+1) es una arista para 1  i  n. Un
camino es simple si todos su vértices son distintos, excepción de v 1 y vn, que pueden ser el mismo. La
longitud del camino es n-1, el número de aristas a lo largo del camino. Se dice que el camino v 1,v2,...,vn
conecta v1 y vn. Un grafo es conexo si todos sus pares de vértices están conectados.

Sea G=(V,A) un grafo con conjunto de vértices V y conjunto de aristas A. Un subgrafo de G es un

grafo G’=(V’,A’) donde:

1. V’ es un subconjunto de V.
2. A’ consta de las aristas (v,w) en A tales que v y w están en V’.

Un ciclo (simple) de un grafo es un camino (simple) de longitud mayor o igual a tres, que conecta un
vértice consigo mismo. No se consideran ciclos los caminos de la forma v (camino de longitud 0), v, v
(camino de longitud 1), o v,w,v (camino de longitud 2).

Un grafo es cíclico si contiene por lo menos un ciclo. Un grafo conexo acíclico algunas veces se
conoce como árbol libre.

Un árbol libre puede convertirse en ordinario si se elige cualquier vértice deseado como raíz y se
orienta cada arista desde ella.

Los árboles libres tienen dos propiedades importantes:

1. Todo árbol libre con n  1 vértices contiene exactamente n-1 aristas.
2. Si se agrega cualquier arista a un árbol libre, resulta un ciclo.

14
 Tipos de datos abstractos

Material didáctico
Métodos de representación

Los métodos de representación de grafos dirigidos se pueden emplear también para representar los no
dirigidos. Una arista no dirigida entre v y w se representa simplemente con dos aristas dirigidas, una de
v a w, y otra de w a v.

1. Matriz de adyacencia

2. Lista de adyacencia

15
 Tipos de datos abstractos

Material didáctico
Árboles abarcadores de costo mínimo (AAM)

Supóngase que G = (V, A) es un grafo conexo en donde cada arista (u,v) de A tiene un costo asociado c
(u,v). Un árbol abarcador para G es un árbol libre que conecta todos los vértices de V; su costo es la
suma de los costos de las aristas del árbol.

Una aplicación típica de los árboles abarcadores de costo mínimo tiene lugar en el diseño de redes de
comunicación. Los vértices del grafo representan ciudades, y las aristas, las posibles líneas de
comunicación entre ellas. El costo asociado a una arista representa el costo de seleccionar esa línea
para la red. Un árbol abarcador de costo mínimo representa una red que comunica todas las ciudades a
un costo minimal.

Hay distintas formas de construir un árbol abarcador de costo mínimo, en este curso se estudiarán:
a. Algoritmo de Prim
b. Algoritmo de Kruskal

16
 Tipos de datos abstractos

Material didáctico
Algoritmo de Prim

Existen dos técnicas populares que explotan la propiedad AAM (Árbol Abarcador de costo Mínimo)
para construir un árbol abarcador de costo mínimo a partir de un grafo ponderado G=(V,A); una de
ellas se conoce como algoritmo de Prim.

Suponga que V={1,2,...,n}. El algoritmo de Prim comienza cuando se asigna a un conjunto U un valor
inicial {1}, en el cual “crece” un árbol abarcador, arista por arista. En cada paso localiza la arista más
corta (u,v) que conecta U y V-U, y después agrega v, el vértice en V-U, a U. Este paso se repite hasta
que U=V.

17
 Tipos de datos abstractos

Material didáctico
Algoritmo de Kruskal

Sea G=(V,A), con V={1,2,...,n} y un función de costo c definida en las aristas de A. Otra forma de
construir un árbol de extensión de costo mínimo para G es empezar con un grafo T=(V, ) constituido
sólo por los vértices de G y sin aristas. Por tanto, cada vértice es un componente conexo por sí mismo.
Conforme el algoritmo avanza, habrá siempre una colección de componentes conexos, y para cada
componente se seleccionarán las aristas que formen un árbol de extensión.

Para construir componentes cada vez mayores, se examinan las aristas a partir de A, en orden creciente
de acuerdo con el costo. Si la arista conecta dos vértices que se encuentran en dos componentes
conexos distintos, entonces se agrega la arista T. Se descartará la arista si conecta dos vértices
contenidos en el mismo componente, ya que puede provocar un ciclo si se la añadiera al árbol de
extensión para ese componente conexo. Cuando todos los vértices están en un solo componente, T es
un árbol de extensión de costo mínimo para G.

Ejemplo. Secuencia de aristas añadidas por el algoritmo de Kruskal.

18
Tipos de datos abstractos

Material didáctico

19
 Tipos de datos abstractos

Material didáctico
Bibliografía

Aho, A. V., Hopcroft, J. E., & Ullman, J. D. (1988). Estructuras de datos y algoritmos (Vol. 1).
Addison-Wesley Iberoamericana.

Birtwistle, G. M., Dahl, O. J., Myhrhaug, B., & Nygaard, K. (1973) SIMULA BEGIN. Filadelfia,
Pensilvania. Auerbach Press

Cook, W. R. (2009, October). On understanding data abstraction, revisited. In Proceedings of the 24th
ACM SIGPLAN conference on Object oriented programming systems languages and applications (pp.
557-572).

Guttag, J. V. (1975). The specification and application to programming of abstract data types.
University of Toronto.

Liskov, B., & Zilles, S. (1974). Programming with abstract data types. ACM Sigplan Notices, 9(4), 50-
59.

Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische mathematik,
1(1), 269-271.

Floyd, R. W. (1962). Algorithm 97: shortest path. Communications of the ACM, 5(6), 345.

Warshall, S. (1962). A theorem on boolean matrices. Journal of the ACM (JACM), 9(1), 11-12.

Prim, R. C. (1957). Shortest connection networks and some generalizations. The Bell System Technical
Journal, 36(6), 1389-1401.

Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem.
Proceedings of the American Mathematical society, 7(1), 48-50.

20