Download Grafo dirigido

Estructuras de datos para
Grafos
Estructura de Datos
Facultad de Ciencias de la computación
BUAP.
Verano 2005
Introducción

Los grafos sirven para representar relaciones
arbitrarias (no necesariamente jerárquicas)
entre objetos de datos
PLAZA DE
CASTILLA
GUZMAN
EL BUENO
NUEVOS
MINISTERIOS
CUATRO
CAMINOS
AVDA. DE
AMÉRICA
CANAL
Estructura de Datos
GREGORIO
MARAÑÓN
Grafos - 2
Introducción: aplicaciones

Circuitos electrónicos
lab-a01
Lab-a02
Tarjetas impresas
Circuitos integrados

Redes de transporte
Autopistas
Vuelos

inf.uc3m.es
Redes de ordenadores
LANs
Internet
Web

it.uc3m.es
uc3m.es
telefonica.net
rediris.net
Bases de datos
otro.net
Diagramas entidad/relación
juan
pablo
Estructura de Datos
david
Grafos - 3
Introducción: aplicaciones(Cont.)





Modelar conectividad en computadoras y redes
de comunicaciones.
Representar un mapa como un conjunto de
localidades con distancias entre ellas; usado
para calcular las rutas más cortas entre
localidades.
Modelar capacidades de flujo en redes de
transporte.
Modelar relaciones en familias, negocios u
organizaciones militares.
Modelar algoritmos de computadora, mostrando
las transiciones del estado de un programa a
otro.
Estructura de Datos
Grafos - 4
Fundamentos: definiciones





Un grafo consiste en un conjunto de vértices o nodos y
un conjunto de arcos. Se representa con el par G = (V,A).
Un arco o arista está formado por un par de nodos u y v,
y se representa por (u,v)
Un grafo es dirigido si los pares de nodos que forman los
arcos son ordenados y se representan u  v. Un grafo no
dirigido es aquel que los arcos están formados por pares
de nodos no ordenados, se representa u  v.
Si (u,v) es una arista en A(G), entonces u y v se dice que
son vértices adyacentes.
Un arco tiene, a veces, asociado un factor de peso, en
cuyo caso se dice que es un grafo valorado o ponderado
(con pesos).
Estructura de Datos
Grafos - 5
Fundamentos: grafos dirigidos
b
Grafo no dirigido
V(G1) = {a,b,c,d}
A(G1) = {(a,b),(a,d),(b,c),(b,d)}
d
a
c
Grafo dirigido
V(G2) = {1,3,5,7,9}
A(G2) = {(1,3),(3,1),(9,1),
(3,5),(5,7)}
3
9
5
1
7
Estructura de Datos
Grafos - 6
Fundamentos

Grado de un nodo
En un grafo dirigido
—Grado de un nodo u = nº de aristas que contienen a u
En un grafo dirigido
—Grado de entrada de u = nº de arcos que llegan a u
—Grado de salida de u = nº de arcos que salen de u

Grafos conexos
Un grafo no dirigido es conexo si existe un camino
entre cualquier par de nodos que forman el grafo
Ejemplos:
grafo conexo
Estructura de Datos
grafo no conexo con dos
componentes conexas
Grafos - 7
Fundamentos: camino



Un camino P de longitud n en
el grafo G desde u0 a un es la
secuencia de n+1 vértices P =
(u0, u1, ..., un) tal que (ui,ui+1)
V
son arcos de G para 0  i  n
a
Un camino es simple si todos
d
los nodos que forman el
U
P2
camino son distintos, pudiendo
c
ser iguales los extremos del
camino
W
Ejemplo:
P1 es simple
P2 no es simple
Estructura de Datos
b
P1
X
e
h
Z
g
f
Y
Grafos - 8
Fundamentos: ciclos y bucles




Un ciclo es un camino
simple cerrado con u0=un,
compuesto al menos por
tres nodos
Un ciclo es simple si todos
sus vértices y arcos son
distintos
Un arco que va desde un
vértice a sí mismo (u,u) se
denomina bucle
Ejemplo
a
U
c
V
b
d
C2
X
e
C1
g
W
f
h
Z
Y
C1 es un ciclo simple
C2 es un ciclo no simple
Estructura de Datos
Grafos - 9
TAD GRAFO: Operaciones
Creación del grafo
crearGrafo (grafo)
Inclusión de vértices
insertarVertice(grafo, vertice)
Eliminación de vértices
borrarVertice(grafo, referenciaVertice)
Inclusión de aristas
insertarArista(grafo, vertice1, vertice2)
Borrar aristas
borrarArista(grafo,arista)
Recorrido del grafo
recorrer(grafo,tipoRecorrido)
Estructura de Datos
Grafos - 10
TAD GRAFO: Operaciones
Acceso a los vertices
Modificación de vertices
Acceso a las aristas
Modificación de aristas
Estructura de Datos
info(referenciaVertice)  Informacion
grado(referenciaVertice)  Entero
gradoEntrante(referenciaVertice)  Entero
gradoSaliente(referenciaVertice)  Entero
adyacentes(referenciaVertice)  {referenciaVertice}
incidentes{referenciaVertice)  {referenciaVertice}
esAdyacente(refenciaVertice1, referenciaVertice2) 
Boolean
asignarInfo(referenciaVertice, valorInformacion)
vertices(referenciaArista)  (refVertice,
refVertice)
destino(referenciaArista)  refVertice
origen(referenciaArista)  refVertice
etiqueta((referenciaArista)  etiqueta
asignarEtiqueta(referenciaArista, valorEtiqueta)
Grafos - 11
Representación: matriz de adyacencia

Matriz de adyacencias
Sea G = (V,A) un grafo de n nodos, suponemos
que los nodos V = {u1,...,un} están ordenados y
podemos representarlos por sus ordinales
{1,2,...,n}.
La representación de los arcos se hace con una
matriz A de nxn elementos aij definida:
1 si hay arco (ui,uj)
aij
0 si no hay arco (ui,uj)
Estructura de Datos
Grafos - 12
Representación: matriz de adyacencia
3
1
1
3
5
1
4
2
2
2
4
0
0
0
0
0
1
0
1
0
0
Estructura de Datos
0
1
0
0
0
0
0
0
0
1
1
3
0
0
1
0
0
5
6
1
2
2
0
1
1
1
1
0
0
1
1
0
0
0
4
1
1
0
0
0
0
0
0
0
1
0
6
0
0
0
2
0
0
0
0
0
0
0
1
0
0
2
0
0
Grafos - 13
Representación

Matriz de adyacencia
Poco eficiente si el nº de vértices varía a lo largo del
tiempo de vida del grafo
Puede darse el caso de que el nº de vértices sea mayor
del previsto inicialmente
Poco eficiente cuando el grafo tiene pocos arcos (la
matriz es “dispersa”)

Listas de adyacencia
Representar una lista de todos los vértices
Cada objeto vértice guarda una lista de adyacencia con
un objeto arista para cada vértice alcanzable desde él
Estructura de Datos
Grafos - 14
Representación: listas de adyacencia

Ejemplo
1
3
2
3
3
1
4
3
2
1
5
4
4
5
Estructura de Datos
1
2
4
Grafos - 15
Representación de Grafos
Estructura de Datos
Grafos - 16
Recorridos

Primero en profundidad
Visitar vértice inicial vi
Visitar vértice adyacente
a vi
... proceder así hasta
encontrar uno ya
visitado...
Volver atrás hasta llegar a
un vértice con adyacentes
sin visitar
El recorrido termina
cuando volviendo atrás
llegamos al vértice innicial
vi y no quedan
adyacentes por recorrer
Estructura de Datos

Primero en anchura
Visitar vértice inicial vi
Visitar todos los vértices
adyacentes a vi
Al terminar, comenzar a
visitar los adyacentes a
los adyacentes a vi
... proceder así hasta que no
queden vértices por
visitar
Grafos - 17
Recorridos

Profundidad
RPP(vi)
{
marcar vi como visitado
para cada vk adyacente a v
si vk no visitado
entonces RPP(vk)
}
Estructura de Datos

Anchura
RPA(vi)
{
marcar vi como visitado
meter vi en cola q
mientras cola q no vacía
sacar v de cola q
para cada vk adyacente a v
si vk no visitado
entonces
marcar vk visitado
meter vk en cola q
}
Grafos - 18
Recorridos: operaciones auxiliares

Marcar vértice como visitado
Si los vértices están identificados por algún tipo ordinal,
emplear un conjunto que contenga los identificadores
de los vértices visitados

Encontrar los vértices adyacentes
Con matrices de adyacencia: recorrer la fila
correspondiente al vértice, buscando columnas a TRUE
Con listas de adyacencia: recorrer la lista

Cola de vértices visitados en anchura
Operaciones del TAD Cola
Estructura de Datos
Grafos - 19
Recorrido primero en profundidad
2
3
1
6
3
1
7
10
4
11
9
2
10
4
11
12
13
8
8
5
5
7
9
6
12
1, 3, 6, 10, 13, 12, 9, 5, 2, 4, 7, 8, 11
Estructura de Datos
Grafos - 20
Recorrido primero en profundidad
1
2
3
4
5
6
7
8
9
10
11
12
13
Estructura de Datos
1
2
3
4
5
6
7
8
9 10 11 12 13
0
1
1
1
0
0
0
0
0
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
0
0
1
0
0
1
0
1
1
0
0
0
0
0
0
1
1
1
0
0
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
0
0
1
0
1
0
0
0
0
0
0
0
1
1
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
1
0
1
2
4
3
6
10
7
11
8
5
9
12
13
Grafos - 21
Recorrido primero en anchura
4
3
1
1
5
6
8
10
7
2
4
3
6
11
9
11
13
8
2
7
5
10
9
12
12
1, 3, 4, 2, 6, 7, 8, 5, 10, 11, 9, 13, 12
Estructura de Datos
Grafos - 22
Recorrido primero en anchura
1
2
3
4
5
6
7
8
9
10
11
12
13
Estructura de Datos
1
2
3
4
5
6
7
8
9 10 11 12 13
0
1
1
1
0
0
0
0
0
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
0
0
1
0
0
1
0
1
1
0
0
0
0
0
0
1
1
1
0
0
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
0
0
1
0
1
0
0
0
0
0
0
0
1
1
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
Grafos - 23
Árbol reducido/de expansión


Un árbol puede verse como un
caso particular de un grafo: un
grafo conexo acíclico
Para obtener el árbol
reducido de un grafo hay que
eliminar todas las aristas que
producen ciclos, pero
manteniéndolo conexo
grafo
Aplicación: encaminamiento
en redes de comunicaciones


No existe un único árbol
reducido de un grafo, pues
dependerá del nodo de partida
y de la forma de recorrerlo
Cuando el grafo es valorado,
puede calcularse el árbol de
expansión de coste mínimo
Estructura de Datos
Árbol de
expansión
Grafos - 24
Árbol reducido (anchura)
6
3
1
10
7
4
11
13
8
2
5
9
Estructura de Datos
12
Grafos - 25
Árbol reducido (profundidad)
6
3
1
10
7
4
11
13
8
2
5
9
Estructura de Datos
12
Grafos - 26
Árbol reducido: Kruskal

Algoritmo de Kruskal
Para grafos no dirigidos,
valorados, de n vértices
El árbol reducido tiene n1 aristas

Obtención:
Partir de un grafo G sin
aristas y añadir una cada
vez, hasta tener n-1
aristas
Ir suprimiendo aristas del
grafo de forma que no
contenga ningún ciclo y
siga siendo conexo
Seleccionar cada vez la
de menor peso
Estructura de Datos

Algoritmo:
Inicializar arbol(A)
para cada vi  G
Incluir vértice vi en A
mientras Nº aristas(A) < n-1
Seleccionar arista a de G
con menos peso;
Eliminar arista a de G;
si a no forma ciclo en A
entonces
Incluir arista a en A;
Grafos - 27
Caminos de longitud mínima: Dijkstra

Algoritmo de Dijkstra
Determina el camino de longitud mínima entre un vértice
origen y todos los posibles destinos
Válido para grafos dirigidos y no dirigidos

Descripción
Asigna etiquetas temporales a cada vértice, que son cotas
superiores de las distancias mínimas del vértice origen a cada
uno de los demás
Las etiquetas temporales se van convirtiendo en
permanentes en cada iteración, representando entonces la
distancia mínima del origen a cada vértice
Comienza con etiqueta permanente = 0 para el vértice origen
y etiquetas temporales = distancia directa desde el origen al
resto
Si no existe arco directo desde el origen, su distancia es 
Estructura de Datos
Grafos - 28
Caminos de longitud mínima: Dijkstra

Algoritmo:
1. Asignar etiqueta permanente = 0 al vértice origen
2. Asignar etiquetas temporales a los n-1 vértices
restantes igual a
dij si  conexión directa
 si no  conexión directa
3. Hacer permanente la mínima de las etiquetas
temporales. Si hay varias, elegir una arbitraria
4. Sea j el vértice que ha recibido la etiqueta permanente
en el paso anterior. La nueva etiqueta temporal de
cada vértice i será = min(etiquetai, etiquetaj + dij)
5. Hacer permanente la mínima de todas las etiquetas
temporales. Si hay varias, elegir una arbitraria. Si la
elegida es la del vértice destino, parar. Si no, volver al
paso 4.
Estructura de Datos
Grafos - 29