Análisis de Algoritmo
Cecilia Laborde Gonzá[email protected]
Objetivos de la Clase
Conocer y comprender el
funcionamiento de los grafos.
¿ Que es un Grafo?
Un GRAFO es un conjunto de nodos o vértices (V)
y un conjunto de aristas (E), donde cada arista
relaciona a un par de nodos pertenecientes a V.
La estructura algebraica para los grafos es
G=(V,E). Existen dos tipos de Grafos:
Grafo dirigido
Grafo no dirigido
GRAFO DIRIGIDO
Un GRAFO DIRIGIDO G consiste de un conjunto V de
vértices y un conjunto E al conjunto de aristas del
grafo. a b
c d
V={a, b, c, d}
E={(a,c), (a,b), (b,c), (b,d), (c,d)}
GRAFO DIRIGIDO
Los vértices de un grafo dirigido pueden usarse para
representar objetos y los enlaces relaciones entre los
objetos, ejemplo de ello que los vértices pueden
representar ciudades y los enlaces vuelos aéreos
entre ciudades.
GRAFO DIRIGIDO
Un enlace es un par ordenado de vértices (v, w),
donde v es la cola y w corresponde a la cabeza del
enlace.
v w
GRAFO NO DIRIGIDO
Sea G un Grafo no Dirigido, donde G=(V,E), V corresponde al
conjunto de vértices y E al conjunto de aristas del grafo.
Un Grafo no Dirigido se diferencia de un Grafo Dirigido debido a
que cada arista en E es un par no ordenado de vértices. Si
(v,w) es una arista no dirigida (v,w) = (w,v).
a b
c d
V={a, b, c, d}
E={(a,c),(c,a),(a,b),(b,a) (b,c),(c,b),(b,d),(d,b), (c,d),(d,c)}
COSTOS
Los enlaces tanto para los grafos Dirigidos como No Dirigidos
tienen un costo (valor), por lo tanto son grafos etiquetados
a b
c d
a b
c d
20
3025
15
40 40
a b
c d
a b
c d
20
3025
15Grafo Dirigido
Etiquetado Grafo No Dirigido Etiquetado
REPRESENTACION LOS GRAFOS
Un grafo Dirigido o No-Dirigido se puede representar mediante: Matriz de Adyacencia Lista de Adyacencia Arreglos para la Lista de Adyacencia.
Sea el siguiente Grafo Dirigido:
Donde:
V={1,2,3,4}
E={(1,2),(2,3), (,3,1), ((4,2),(3,4)}
2
1
3
4
MATRIZ ADYACENTE
La Matriz Adyacente A de un Grafo G=(V,E) tiene V*V
elementos y se define como:
2
1
3
4
casootroen
Ejisijia
0
),( 1],[
Sea: E={( 1 , 2 ), ( 2 , 3), (3 , 1 ), ( 4 ,2),( 3 , 4 )}
0010
1001
0100
0010
a
Fila Columna
VENTAJAS Y DESVENTAJAS DE LA MATRIZ DE ADYACENCIA
VENTAJAS:Se puede determinar en un tiempo fijo y constante si un enlace(arco) pertenece o no al grafo.
Es fácil determinar si existe o no un arco o enlace, solo se debe posicionar en la matriz.
Es fácil determinar si existe un ciclo en el grafo, basta multiplicar la matriz por ella misma n veces hasta obtener la matriz nula(no hay ciclos) o bien una sucesión periódica de matrices(hay ciclo)
DESVENTAJAS:
Se requiere un almacenamiento |v|
*|v|. Es decir O(n2).
Solo al leer o examinar la matriz
puede llevar un tiempo de O(n2).
LISTA ADYACENTE
La lista de adyacencia para un vértice V es una lista enlazada de
todos los vértices W adyacentes a V. Un grafo puede ser
representado por |V| listas de adyacencias, una para cada vértice.
21
3 4
Lista de
AdyacenciaGrafos
Vértices
VENTAJAS Y DESVENTAJAS DE LAS LISTAS DE ADYACENCIA
VENTAJAS:
La lista de adyacencia requiere
un espacio proporcional a la
suma del número de vértices
más el número de
enlaces(arcos). Hace buen uso
de la memoria.
Se utiliza bastante cuando el
número de enlaces es mucho
menor que O(n2)
DESVENTAJAS:
La representación con lista de
adyacencia es que puede llevar
un tiempo O(n) determinar si
existe un arco del vértice i al
vértice j, ya que pueden haber
O(n) vértices en la lista de
adyacencia. Para el vértice i.
UTILIZACION DE ARREGLOS PARA LA LISTA DE ADYACENCIA
VENTAJAS:
Se utilizan los arreglos para implementar la Lista de Adyacencia:
21
3 4
Grafos
1
2
4
3
Vertices
230
4
0
2
0
3
0
Arreglo deLista
Adyacente