INFORMATICA III

Capitulo VII
ESTRUCTURA DE
DATOS

“GRAFOS”

Lic. Juan Samuel Cáceres

Grafos
Un grafo es un conjunto de puntos (estructura de datos) y un conjunto de líneas,
cada una de las cuales une un punto a otro. Los puntos se llaman nodos o vértices
del grafo y las líneas se llaman aristas o arcos del grafo.
Ejemplo de un grafo en la vida real:
Una red de rutas de una ciudad a otra, una red de enlaces ferroviarios o aéreos.
Grafos
Un grafo, G, es un par ordenado de V y A, donde V es el conjunto de vértices o nodos del grafo y A es
un conjunto de pares de vértices, a estos también se les llama arcos o ejes del grafo. Un vértice puede
tener 0 o más aristas, pero toda arista debe unir exactamente a dos vértices.
Los grafos representan conjuntos de objetos que no tienen restricción de relación entre ellos. Un grafo
puede representar varias cosas de la realidad cotidiana, tales como mapas de carreteras, vías férreas,
circuitos eléctricos, etc.

La notación G = A (V, A) se utiliza comúnmente para identificar un grafo.

Los grafos se constituyen principalmente de dos partes: las aristas, vértices y los caminos que pueda
contener el mismo grafo.

Son las líneas con las que se unen los vértices de un grafo y con la que se construyen también
caminos.

Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que
une.

Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos.

Grafos
A B

Ejemplificamos la definición del siguiente grafo. C

D E

G = (V,A)

V = Conjunto de vértices o nodos (representan los objetos)

A = Conjunto de arcos (representan las relaciones)

V = {A,B,C,D,E}
A = {(A,B),(A,C),(C,D),(D,E),(B,A),(C,A),(D,C),(E,B),(E,D)}
Grafos
Existen varios tipos de representación de grafos.

Grafo no dirigido – no ponderado (no tiene dirección - ni peso de aristas)

A C D

Grafo dirigido - no ponderado (tiene dirección - no tiene peso de aristas)

A C D

Grafo no dirigido – ponderado (no tiene dirección - tiene peso de aristas)

4 6
A C D

Grafo dirigido – ponderado (tiene dirección – tiene peso de aristas)

A 4 C 6
D
Aristas
Aristas Adyacentes: Dos aristas son adyacentes si convergen en el
mismo vértice.
C
A D

Aristas Paralelas: Dos aristas son paralelas si su vértice inicial y el final

son el mismo.
A D

Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.

A

Cruce: Son dos aristas que se cruzan en un punto.

A B

C D
Vértices
Son los puntos o nodos con los que esta conformado un grafo.
Llamaremos grado de un vértice al número de aristas de las que es
extremo. Se dice que un vértice es ‘par’ o ‘impar’ según lo sea su grado.

Vértices Adyacentes: Si tenemos un par de vértices de un grafo (U, V) y

un arista que los une, entonces U y V son vértices adyacentes y el vértice
U es el vértice inicial y V el vértice adyacente. U V

Vértice Aislado: Es un vértice de grado cero.

U V Y

Vértice Terminal: Es un vértice de grado 1 (tiene una sola relación).

A D

B C
Caminos
Sean x, y  V, tiene un camino en G de x a y si existe una sucesión finita
no vacía de aristas {x,v1}, {v1,v2},..., {vn,y}.
x a b c d y

 En este caso x e y se llaman los extremos del camino

 El número de aristas del camino se llama la longitud del camino.
 Si los vértices no se repiten el camino se llama propio o simple.
 Cuando los dos extremos de un camino son iguales, el camino se llama
circuito o camino cerrado.
 Llamaremos ciclo a un circuito simple
 Un vértice a es accesible desde el vértice b si existe un camino entre
ellos. Todo vértice es accesible respecto a si mismo
Caminos
Ejemplo de notación de caminos, vamos a indicar todos los caminos
posibles del vértice x al vértice y b c d
Se debe tener en cuenta la dirección
a x y
de las flechas
Camino 1
C1 = {x,a,b,c,d,y}
Camino 2
C2 = {x,c,d,y}
Camino 3
C3 = {x,y}
Longitudes
C1 = 5 C2 = 3 C3 = 1
Caminos
Ejemplo de notación de caminos, vamos a indicar el camino más óptimo
desde el vértice x al vértice y b 4 c 4 d
5 2
20
Para eso tendremos en cuenta el peso
a x y
de cada arista. 6 100

Camino 1
xa=6, ab=5, bc=4, cd=4, dy=2 => C1 = 6+5+4+4+2 = 21
Camino 2
xc=20, cd=4, dy=2 => C2 = 20+4+2 = 26
Camino 3
xy = 100 => C3 = 100
En conclusión podemos decir que el camino 1 (C1) es el más óptimo,
aunque tiene mayor longitud, es el camino que tiene menor peso en la
sumatoria de los valores de cada arista.
REPRESENTACIÓN DE GRAFOS EN PROGRAMAS

Hay tres maneras de representar un grafo en un programa: mediante

matrices, mediante listas y mediante matrices dispersas.

Representación mediante matrices: La forma más fácil de guardar la

información de los nodos es mediante la utilización de un vector que indexe
los nodos, de manera que los arcos entre los nodos se pueden ver como
relaciones entre los índices. Esta relación entre índices se puede guardar
en una matriz, que llamaremos matriz de adyacencia.
REPRESENTACIÓN DE GRAFOS EN PROGRAMAS

La matriz de adyacencia es un arreglo de dos dimensiones que representan

las conexiones entre pares verticales.

Las columnas y las filas de la matriz representan los vértices del grafo, si
existe una arista desde una fila a una columna, es por que aquel vértice es
adyacente a otro. Se introduce un cero (0) en las aristas no adyacentes y el
valor uno (1) si existe una adyacencia entre los nodos.
REPRESENTACIÓN DE GRAFOS EN PROGRAMAS
Ejemplo de la representación de grafos A B
mediante matriz de adyacencia
C
Los vértices deben representarse como
filas y columnas de la matriz. D E

No Dirigido – No Ponderado
Significa que no se tiene en cuenta las
direcciones de las relaciones, si A y B tiene A B C D E
una arista, quiere decir que A es accesible A 0 1 1 0 1
por B, y B es accesible por A. una relación B 1 0 0 0 1
de doble sentido.
C 1 0 0 1 1
Tampoco se tiene en cuenta el peso de las
D 0 0 1 0 1
aristas.
E 1 1 1 1 0
Se coloca 0 si no hay relación
Se coloca 1 si hay relación
REPRESENTACIÓN DE GRAFOS EN PROGRAMAS
Ejemplo de la representación de grafos A B
mediante matriz de adyacencia
C
Los vértices deben representarse como
filas y columnas de la matriz. D E

Dirigido – No Ponderado
Significa que se tiene en cuenta las
direcciones de las relaciones si A y B tienen A B C D E
relación y la flecha va de A hacia B, A 0 1 1 0 1
entonces B es accesible por A, pero A no B 0 0 0 0 0
es accesible por B.
C 0 0 0 1 1
Pero no se tiene en cuenta el peso de las
D 0 0 0 0 1
aristas.
E 0 1 0 0 0
Se coloca 0 si no hay relación
Se coloca 1 si hay relación
REPRESENTACIÓN DE GRAFOS EN PROGRAMAS
6
Ejemplo de la representación de grafos A B
5
mediante matriz de adyacencia
7 4
C 9
Los vértices deben representarse como 5
filas y columnas de la matriz. D E
6

No Dirigido – Ponderado
Significa que no se tiene en cuenta las
direcciones de las relaciones, si A y B tiene A B C D E
una arista, quiere decir que A es accesible A 0 6 5 0 7
por B, y B es accesible por A. una relación B 6 0 0 0 4
de doble sentido.
C 5 0 0 5 9
Pero sí se tiene en cuenta el peso de las
D 0 0 5 0 6
aristas.
E 7 4 9 6 0
Se coloca 0 si no hay relación
Se coloca peso de arista si hay relación
REPRESENTACIÓN DE GRAFOS EN PROGRAMAS
6
Ejemplo de la representación de grafos A B
5
mediante matriz de adyacencia
7 4
C 9
Los vértices deben representarse como 5
filas y columnas de la matriz. D E
6

Dirigido – Ponderado
Significa que se tiene en cuenta las
direcciones de las relaciones si A y B tienen A B C D E
relación y la flecha va de A hacia B, A 0 6 5 0 7
entonces B es accesible por A, pero A no B 0 0 0 0 0
es accesible por B
C 0 0 0 5 9
Se coloca 0 si no hay relación
D 0 0 0 0 6
Se coloca peso de la arista si hay relación
E 0 4 0 0 0
GRADOS DEL GRAFO

A B D G

C E F

Grado Interno (GI): es la suma de las columnas A B C D E F G

Grado Externo (GE): es la suma de las filas A 0 1 0 0 0 0 0
Grado del Nodo (GN): es la suma del grado interno y externo
B 0 0 1 0 0 0 0
A B C D E
C 0 0 0 1 0 0 0
GI 0 GI 1 GI 2 GI 2 GI 2
D 0 0 0 0 0 0 0
GE 1 GE 1 GE 1 GE 0 GE 2
GN 1 GN 2 GN 3 GN 2 GN 4
E 0 0 1 1 0 0 0
F 0 0 0 0 1 0 1
F G
G 0 0 0 0 1 0 0
GI 0 GI 1
GE 2 GE 1
GN 2 GN 2
REPRESENTACIÓN DE GRAFOS EN PROGRAMAS

Representación mediante listas: En las listas de adyacencia lo que haremos será

guardar por cada nodo, además de la información que pueda contener el propio
nodo, una lista dinámica con los nodos a los que se puede acceder desde él.
La información de los nodos se puede guardar en un vector, al igual que antes, o
en otra lista dinámica.
La lista de adyacencia (enlazada), es el segundo método utilizado para representar
grafos, en donde se utilizan un nodo apuntador por cada vértice del grafo que tenga
adyacencia.
El grafo completo incluye dos partes: un directorio y un apuntador
 REPRESENTACIÓN DE GRAFOS EN PROGRAMAS

A B D G A 5 B 4 3 D 2 5 G 2
C E F C E F
7 6

Dirigido – No Ponderado Dirigido –

Ponderado
A B \ A B;5 \
B C \ B C;4 \
C D \ C D;3 \
D \ D \
E C D \ E C;7 D;2 \
F E G \ F E;6 G;2 \
G E \ G E;5 \
REPRESENTACIÓN DE GRAFOS EN PROGRAMAS

A B D G
C E F

No Dirigido – No Ponderado

A B \
B A C \
C B D E \
D C E \
E C D F G \
F E G \
G E F \
REPRESENTACIÓN DE GRAFOS EN PROGRAMAS

A 5 B D G
4 3 2 5 2
C 7 E 6 F

No Dirigido – Ponderado

A B;5 \
B A;5 C;4 \
C B;4 D;3 E;7 \
D C;3 E;2 \
E C;7 D;2 F;6 G;5 \
F E;6 G;2 \
G E;5 F;2 \
RECORRIDO DE UN GRAFO

Recorrer un grafo significa tratar de alcanzar todos los nodos que estén
relacionados con uno que llamaremos nodo de salida. Existen
básicamente dos técnicas para recorrer un grafo: el recorrido en anchura; y
el recorrido en profundidad.

Recorrido en anchura: El recorrido en anchura supone recorrer el grafo, a

partir de un nodo dado, en niveles, es decir, primero los que están a una
distancia de un arco del nodo de salida, después los que están a dos arcos
de distancia, y así sucesivamente hasta alcanzar todos los nodos a los que
se pudiese llegar desde el nodo salida.
Recorrido en profundidad: el recorrido en profundidad trata de buscar los
caminos que parten desde el nodo de salida hasta que ya no es posible
avanzar más. Cuando ya no puede avanzarse más sobre el camino elegido,
se vuelve atrás en busca de caminos alternativos, que no se estudiaron
previamente.
RECORRIDO DE UN GRAFO

Recorrido en profundidad
Recorrido en anchura
A A
B D B D
C C
E H E H
F G F G

I J K I J K

ABEIFCGJKHD ABCDEGHIJKF