Download E - Biblioteca de la UNS

Tópicos I
Unidad I
Árboles, montículos y grafos
Semana 4
Algoritmos sobre grafos elementales, Conectividad
y Grafos ponderados
Objetivos Generales
Entender el manejo, uso de algoritmos y
estructuras de datos avanzados, haciendo
énfasis en los algoritmos de internet,
seguridad y redes.
Objetivo Específico
Implementar
algoritmos
utilizando
estructura de datos avanzadas.
Objetivo Instruccional
Implementar algoritmos fundamentales
para la solución de problemas basados
en la teoría de grafos.
Contenidos
Algoritmos sobre grafos
elementales
Conectividad
Árbol de expansión
mínimo
Grafos ponderados
Camino mas corto
Algoritmos sobre grafos elementales
Glosario
Grafo: Un grafo es una colección
de vértices y aristas. Los vértices
son objetos simples que pueden
tener
un
nombre
y
otras
propiedades; una arista es una
conexión entre dos vértices.
Camino: Un camino entre los
vértices x e y de un grafo es una
lista de vértices en la que dos
elementos
sucesivos
están
conectados por aristas del grafo.
A
B
C
D
E
G
F
A
B
G
E
F
Algoritmos sobre grafos elementales
Glosario
Grafo conexo: Un grafo es conexo
si hay un camino desde cada
nodo hacia otro nodo del grafo.
A
Grafo no conexo: Esta constituido
por componentes conexos.
A
B
D
C
E
G
F
G
B
D
E
F
Camino simple: Es un camino en el
que no se repite ningún vértice.
A
B
G
E
Ciclo: es un camino simple con la
característica de que el primero y
el ultimo vértices son el mismo.
F
A
G
E
F
Algoritmos sobre grafos elementales
Glosario
Grafo completo: Son los grafos con
todas las aristas posibles.
A
G
E
F
Grafo disperso: Tienen
relativamente pocas aristas.
A
G
E
F
Grafo denso: Les falta muy pocas
aristas de todas las posibles.
A
G
F
E
Algoritmos sobre grafos elementales
Representación
Matriz de adyacencia:
A
A
B
D
C
E
G
La
matriz
de
adyacencia solo
es satisfactoria si
los
grafos
a
procesar
son
densos.
F
Se construye un array de V*V
valores booleanos en el que a[x][y]
es igual a 1 si existe una arista
desde el vértice x al y, y a 0 en el
caso contrario.
B
C
D
E
F
G
A
1
1
1
0
0
1
1
B
1
1
0
0
0
0
0
C
1
0
1
0
0
0
0
D
0
0
0
1
1
1
0
E
0
0
0
1
1
1
1
F
1
0
0
1
1
1
0
G
1
0
0
0
1
0
1
Es de destacar que en realidad cada arista se representa con dos bits:
una arista que enlace x e y se representa con valores verdaderos tanto
en a[x][y] como en a[y][x].
Algoritmos sobre grafos elementales
Representación
Lista de adyacencia:
La lista de adyacencia se adapta mejor a lo casos en los que
los grafos a procesar no son densos.
A
F
B
C
D
E
G
A
B
C
D
E
F
G
F
A
A
E
D
A
A
F
F
D
E
G
E
B
C
G
Algoritmos sobre grafos elementales
Recorridos en un grafo
En una gran cantidad de problemas
con grafos, es necesario visitar
sistemáticamente los vértices y aristas
del grafo.
La búsqueda en PROFUNDIDAD y en
AMPLITUD,
son
dos
técnicas
importantes de recorrido del grafo.
Algoritmos sobre grafos elementales
Búsqueda en Profundidad
(BEP)
Se comienza en el vértice inicial (vértice con
índice 1) que se marca como vértice activo.
Hasta que todos los vértices hayan sido
visitados, en cada paso se avanza al vecino
con el menor índice siempre que se pueda,
pasando este a ser el vértice activo.
Cuando todos los vecinos al vértice activo
hayan sido visitados, se retrocede al vértice
X desde el que se alcanzó el vértice activo y
se prosigue siendo ahora X el vértice activo.
Algoritmos sobre grafos elementales
Búsqueda en Profundidad
a
b
a
c
b
a
c
b
c
d
e
d
e
d
e
a
b
a
b
a
b
c
d
c
e
d
c
e
d
e
La estructura utilizada para guardar los nodos a visitar en este
tipo de búsqueda es una pila o stack (de procedimiento
recursivo).
Algoritmos sobre grafos elementales
Búsqueda en Amplitud
(BEA)
Se comienza en el vértice inicial (vértice con índice 1) y
se marca como vértice activo, a diferencia con la
BEP ahora se visitan en orden creciente de índice
todos los vecinos del vértice activo antes de pasar
al siguiente. Hasta que todos los vértices hayan sido
visitados, en cada paso se van visitando en orden
creciente de índice todos los vecinos del vértice
activo. Cuando se han visitado todos los vecinos del
vértice activo, se toma como nuevo vértice activo
el primer vértice X visitado después del actual
vértice activo.
Algoritmos sobre grafos elementales
Búsqueda en Amplitud
0
1
0
a
a
b
b
1
c
c
d
1
e
d
e
1
0
a
b
1
c
1
2
d
e
En la búsqueda en
amplitud se utiliza una
cola para guardar tales
nodos a visitar.
Algoritmos sobre grafos elementales
Usos de los Recorridos

Ambos recorridos se pueden usar para resolver los
siguientes problemas:
–
–
–
–

Probar que G es conectado.
Obtener un árbol de expansión de G.
Obtener los componentes conectados de G.
Obtener un camino entre dos vértices dados de G, o
indicar que no existe tal camino.
El recorrido BEP se usa para:
– Obtener un ciclo en G, o indicar que G no tiene ciclos.

El recorrido BEA se usa para:
– Obtener para cada vértice v de G, el número mínimo de
aristas de cualquier camino entre s y v.
Algoritmos sobre grafos elementales
Laberintos
La búsqueda en profundidad fue expuesta
formalmente como un método para
recorrer laberintos.
El grafo se construye colocando un
vértice en cada punto en el que existe
mas de un camino a tomar y a conectar
a continuación los vértices de acuerdo
con esos caminos.
“La búsqueda en profundidad es apropiada para la búsqueda de un
elemento en el laberinto por una sola persona, dado que el “siguiente
lugar a visitar” esta siempre próximo; la búsqueda es amplitud es mas
apropiada par un grupo de personas que buscan el mismo elemento
desplazándose en todas las direcciones a la vez”
Conectividad
Problemática
Se examinara una generalización de la conectividad
denominada biconectividad, cuyo interés reside en
conocer si hay mas de un medio de pasar de un vértice
de un grafo a otro.
Grafo biconexo: Un grafo es
biconexo, si solo si, existen al menos
dos caminos diferentes que conecten
cada par de vértices. De esta forma
si se suprime un vértice y todas las
aristas que inciden en el, el grafo
permanece conexo.
A
G
F
E
“Si para algunas aplicaciones es importante que un grafo sea
conexo, es también importante que permanezca conexo”
Conectividad
Problemática
Una versión particular del problema de la conectividad,
que con frecuencia concierne a la situación dinámica
en las que las aristas se añaden al grafo una a una,
intercalando preguntas sobre si dos
vértices
determinados pertenecen (o no) a la misma
componente conexa.
El problema se denomina a veces como “uniónpertenencia”.
Componentes conexas
Conectividad
• De un grafo no dirigido
– Se pude saber si es conexo
Componentes conexas:
entre ellas son conexas
• Si no lo es se pueden conocer sus
– Componentes Conexas
• Conjunto W, de vértices del grafo
• En el cual hay camino desde cualquier V1 a cualquier V2
• Donde V1 y V2 pertenecen a W
CONEXO
A
B
C
E
D
A
B
C
E
D
No CONEXO
Conectividad
Biconectividad
A veces es útil diseñar mas de una ruta entre puntos de
un grafo, aunque solo sea para identificar posibles fallos
en los puntos de conexión (vértices). Esto nos permitiría
tener recorridos alternativos por ejemplo para llegar de
una ciudad a otra.
A
G
F
E
Conectividad
Puntos de articulación
Un punto de articulación en un grafo conexo es un
vértice que si se suprime romperá el grafo en dos o
mas piezas.
En un grafo no dirigido conexo:
• Existen vértices que si se eliminan
– “Desconectan” al Grafo
– Lo dividen en componentes conexas
• Estos vértices “clave” son puntos de articulación
• Si un grafo no tiene Punto de Articulación
– Es biconexo
• La conectividad de un grafo
– Es el numero de nodos que se necesitan eliminar para dejar a
un grafo “desconectado”
Puntos de articulación
Conectividad
Ejemplo
A
B
C
D
Puntos de
Articulación
E
F
Conectividad
Árbol de expansión
Definición: Un árbol T es
un árbol de expansión
de un grafo G si T es un
subgrafo que contiene a
todos los vértices de G.
Árbol de expansión
• Para poder calcular los Puntos de Articulación de un grafo
Conectividad
– Hay que obtener el árbol de expansión
A
• Este se obtiene
– A partir del Recorrido en Profundidad
D
C
Ejemplo:
F
A
B
C
D
E
E
F
B
Arco en Retroceso:
Cuando se quiere
visitar un nodo que
ya ha sido visitado y
no es el padre
Como representar el árbol de
expansión
Conectividad
• Un árbol en expansión
– No es un árbol binario
– Cada Vértice puede tener 0, 1 o n hijos
• Si no tomamos en cuenta los arcos en
retroceso, la representación depende del Grafo
– Matriz de Adyacencia -> Usar un arreglo
– Lista de Adyacencia -> Una lista
• La representación mostrará quien es el padre de
cada nodo
Árbol de expansión con matriz
de adyacencia
Conectividad
• Los vértices del grafo
– Se encuentran en un arreglo
A
B
– Cada índice del arreglo
• Representa un vértice
C
• Ej: A – 0, B – 1, etc.
• Al representar el árbol de expansión
– El padre(índice) de cada nodo
puede almacenarse en un arreglo
• Que también represente a los vértices
typedef struct TVertices{
Generico V[MAX];
int Padres[MAX];
int nvertices;
}Vertices;
D
E
F
040052
0 1 2 3 4 5
A B C D E F
Árbol de expansión con lista de
adyacencia
B
A
Conectividad
• Los vértices del grafo
– Se encuentran en una lista
– Cada nodo representa un vértice
D
• Al representar el árbol de expansión
C
E
F
– De cada nodo de esta lista solo nos interesa
conocer al padre
A
– Se puede añadir un dato al nodo vértice
B
• Un enlace con el padre
C
D
typedef struct Vertice{
Generico Informacion;
Vertice *padre;
Lista *LArcos;
}Vertice;
E
F
Conectividad
Unión - Pertenencia
En algunas aplicaciones se desea simplemente
conocer si un vértice x esta o no conectado a un
vértice y de un grafo, sin que sea importante el
camino que los conecta.
Los grafos se corresponden de forma natural con los
conjuntos (colecciones de objetos): los vértices representan
a los objetos y las aristas significan “esta en el mismo
conjunto que”.
C
B
A
D
F
E
G
Conjuntos
ó clases de
equivalencia
{A F D E}
{B C G}
Cada componente conexa
corresponde a una clase de
equivalencia diferente
Unión - Pertenencia
Conectividad
El añadir una arista se corresponde con la
combinación de las clases de equivalencia
representadas por los vértices a conectar.
El interés se centra en la pregunta fundamental “x es
equivalente a y” ó “¿está x en el mismo conjunto
que y?”. Esto se corresponde claramente con la
pregunta fundamental de los grafos “¿está el vértice
x conectado al vértice y?”
“Dado un conjunto de aristas, se puede construir una
representación por lista de adyacencia que corresponda al
grafo y utilizar la búsqueda en profundidad para asignar a
cada vértice el índice de su correspondiente conexa y
responder a las preguntas antes planteada con tal solo dos
accesos a arrays y una comparación”
Conectividad
Unión - Pertenencia
Por correspondencia con el problema de los
conjuntos, la adición de una
nueva arista se
denomina una operación de unión, y las preguntas
se denominan operaciones de pertenencia.
El objetivo es escribir una función que pueda verificar
si dos vértices x e y pertenecen al mismo conjunto (o,
en representación de grafos, a la misma componente conexa) y, en
caso de que sea así, que pueda unirlos en el mismo
conjunto (colocando una arista entre ellos y el grafo).
En lugar de construir una lista de adyacencia directa o
cualquier otra representación de los grafos, es mas eficaz utilizar
una estructura interna orientada específicamente a la
realización de las operaciones unión y pertenencia.
Unión - Pertenencia
Conectividad
Esta estructura interna es un bosque de arboles, uno
por cada componente conexa.
Se necesita poder encontrar si dos vértices
pertenecen al mismo árbol y combinar dos arboles
en uno.
Conectividad
Unión - Pertenencia
Para ilustrar como trabaja este algoritmo, vamos a
ver el bosque construido por los siguientes vértices
(A-B-C-D-E-F-G-H-I-J-K-L-M) cuando se le insertan
estas aristas en el siguiente orden: AG - AB - AC - LM
- JM - JL - JK - ED - FD - HI - FE - AF - GE - GC - GH JG - LG. Inicialmente todos los nodos están en
árboles separados (cada vértice es un árbol).
A
B
C
D
E
F
G
H
I
J
K
L
M
Conectividad
Unión - Pertenencia
Luego la arista AG crea un árbol de dos nodos con
A como raíz (esta decisión es arbitraria, porque tranquilamente
podríamos haber puesto G como raíz).
Las aristas AB y AC agregan B y C al árbol de la
misma forma.
Conectividad
Unión - Pertenencia
Proceso
culminado
Conectividad
Unión - Pertenencia
Es necesario recalcar que, al contrario que en los
árboles de búsqueda primero en profundidad, la única
relación entre estos árboles de unión y el grafo original
con las aristas dadas es que dividen a los vértices en
grupos de la misma forma. Por ejemplo, no hay ninguna
correspondencia entre los caminos que conectan
nodos en los árboles y los caminos que conectan nodos
en el grafo.
Para representar estos árboles es apropiado usar la
representación “enlace padre" porque siempre se viaja
hacia arriba en los árboles, nunca hacia abajo.
Específicamente, mantenemos un array padre que
contiene, para cada vértice, el índice de su padre (0 si es
la raíz de algún árbol), como se especifica en la próxima
declaración de la clase:
Conectividad
Unión - Pertenencia
class EQ
{
private:
int *dad;
public:
EQ(int size);
Int find(int x, int y, int doit);
};
El constructor reserva el espacio para el array dad y setea todos sus
valores inicialmente a cero (se omite el código). Se usa un solo
procedimiento find para implementar ambos, la unión y la
búsqueda. Si el tercer argumento es 0 se hace una búsqueda, si no
es 0, se hace una unión. Para encontrar al padre del vértice j,
simplemente se hace j = dad[j], y para encontrar la raíz del árbol al
que pertenece j se repite esta operación hasta que se llega a 0.
Unión - Pertenencia
Conectividad
Esto nos lleva a la siguiente implementación del procedimiento:
Int EQ::find(int x, int y, int doit)
{
int i=x, j=y;
while (dad[i] >0) i = dad[i];
while (dad[j] > 0) j=dad[j];
if (doit && (i != j)) dad[j]=i;
return (i != j);
}
La función find retorna 0 si los dos vértices dados están en el mismo
componente. Si no lo están y el flag doit esta seteado, son puestos
en el mismo componente. El método es simple. Usar el array dad
para llegar a la raíz del árbol que contiene cada vértice, luego
chequear si las raíces son las mismas. Para mezclar el árbol con raíz
j con el árbol de raíz i simplemente se setea dad[j] = i.
Conectividad
Unión - Pertenencia
Contenido de la estructura de datos union-pertenencia durante el
proceso
Conectividad
Unión - Pertenencia
El algoritmo descrito anteriormente tiene un
mal desempeño para su peor caso porque los
árboles formados pueden ser degenerados.
Por ejemplo, tomando en orden las aristas AB
BC CD DE EF FG GH HI IJ… YZ se produce una
larga cadena con Z apuntando a Y, Y
apuntando a X, etc. Este tipo de estructura
toma un tiempo proporcional a V2 para
construirse y tiene un tiempo proporcional a V
para una prueba promedio de equivalencia.
Conectividad
Unión - Pertenencia
Varios métodos han sido sugeridos para lidiar
con esta dificultad. Un método natural es
tratar de hacer lo correcto para mezclar dos
árboles, en lugar de hacer arbitrariamente
dad[ j ] = i. Cuando un árbol con raíz en i va a
ser mezclado con otro con raíz en j, uno de
los nodos debe mantenerse como raíz y el
otro (y todos sus descendientes) deben ir un nivel más
abajo en el árbol.
Para minimizar la distancia a la raíz de la
mayoría de los nodos tiene sentido elegir
como raíz el nodo con más descendientes.
Conectividad
Unión - Pertenencia
Esta idea, llamada equilibrado de peso, es
fácilmente implementable manteniendo el
tamaño de cada árbol (cantidad de descendientes
de la raíz) en el array dad para cada nodo raíz,
codificado como un número no positivo de
tal modo que el nodo raíz pueda ser
detectado cuando se viaja hacia arriba en el
árbol con find.
Conectividad
Unión - Pertenencia
Idealmente se desearía que cada nodo apuntara
directamente a la raíz de su árbol. Sin importar que
estrategia se use, para lograr este objetivo se necesita
examinar al menos todos los nodos en uno de los dos
árboles a mezclar y esto puede ser demasiado
comparado con los pocos nodos en el camino a la raíz
que find generalmente examina. Sin embargo
podemos aproximarnos a este ideal haciendo que
todos los nodos que sí se examinan apunten a la raíz.
Este método, conocido como compresión de
caminos, se implementa fácilmente haciendo otra
pasada por cada árbol, después de que la raíz fue
encontrada, y seteando la entrada dad de cada
vértice encontrado a lo largo del camino para que
apunte a la raíz.
Conectividad
Unión - Pertenencia
La combinación de compresión de caminos y equilibrado de
peso nos aseguran que los algoritmos van a correr muy rápido. La
siguiente implementación muestra que el código extra necesario
es un pequeño precio a pagar para protegernos de los casos
degenerados.
int EQ::find(int x, int y, int doit)
{
int t, i=x, j=y;
while (dad[i] > 0)
i=dad[i];
while (dad[j] > 0)
j=dad[j];
while (dad[x]>0)
{ t=x; x=dad[x]; dad[t]=i; }
while (dad[y]>0)
{ t=y; y=dad[y]; dad[t]=j; }
if (doit && (i != j))
if (dad[j] < dad[i])
{ dad[j]+=dad[i] - 1; dad[i]=j; }
else
{ dad[i]+=dad[j] - 1; dad[j]=i; }
return (i !=j );
}
Conectividad
Unión - Pertenencia
Proceso
culminado al
aplicar el
método,
equilibrado, con
compresión de
caminos
Conectividad
Unión - Pertenencia
Contenido de la estructura de datos union-pertenencia durante el
proceso con el método equilibrado, con compresión de caminos
Grafos ponderados
Problemática
Con frecuencia se desea modelar problemas
prácticos utilizando grafos en los que se asocia a las
aristas unos pesos o costes.
En un mapa de líneas aéreas, en el que las aristas
representan rutas de vuelo, los pesos pueden
representar distancias o tarifas. Estas situaciones
hacen aparecer de forma natural cuestiones como
el minimizar costes.
Grafos ponderados
Problemática
Se examinara los algoritmos de dos de estos
problemas:
1. Encontrar la forma de conectar todos los puntos
al menor coste (problema del árbol de expansión
mínima).
2. Encontrar el camino de menor coste entre dos
puntos dados (problema del camino mas corto).
La forma de representar a los grafos ponderados es obvia. En la
representación por matriz de adyacencia, la matriz puede contener
pesos de aristas en lugar de valores booleanos y en la representación
por listas de adyacencia se puede añadir un campo a cada
elemento de la lista, a manera de peso.
Grafos ponderados - AEM
Árbol de expansión mínimo
Un árbol de expansión
mínimo de un grafo
ponderado es una
colección de aristas
que conectan todos
los vértices y en el que
la suma de los pesos
de las aristas es al
menos inferior a la
suma de los pesos de
cualquier
otra
colección de aristas
que conecten todos
los vértices.
Grafos ponderados - AEM
Algoritmo genérico
Se puede construir el árbol de expansión
mínimo comenzando en cualquier vértice y
tomando siempre el vértice mas próximo de
todos los que se hayan elegido.
En otras palabras, se busca la arista de
menor peso entre todas las que conectan
vértices que ya están en el árbol con vértices
que no lo están todavía, y después se añade
al árbol la arista y el vértice a los que
conduce la anterior.
Grafos ponderados - AEM
Algoritmo de Kruskal
Se puede construir el árbol de expansión
mínimo comenzando en cualquier vértice y
tomando siempre el vértice mas próximo de
todos los que se hayan elegido.
En otras palabras, se busca la arista de
menor peso entre todas las que conectan
vértices que ya están en el árbol con vértices
que no lo están todavía, y después se añade
al árbol la arista y el vértice a los que
conduce la anterior.
Grafos ponderados - AEM
Algoritmo de Kruskal – paso
a paso
Tengamos el siguiente grafo no dirigido.
Grafos ponderados - AEM
Algoritmo de Kruskal – paso
a paso
En primer lugar usaremos el método MakeSet de
unión-find (revisar) para inicializar cada componente,
obteniendo las siguientes componentes conexas
iniciales:
Grafos ponderados - AEM
Algoritmo de Kruskal – paso
a paso
Ahora el siguiente paso es ordenar las aristas del
grafo en orden ascendente:
Grafos ponderados - AEM
Algoritmo de Kruskal – paso
a paso
Lo siguiente será recorrer todas las aristas ya ordenadas y verificar si sus
vértices están o no en la misma componente.
La primera arista a verificar es la que une a los vértices 8 y 7, verificamos
si están en la misma componente, para ello hacemos Find(8) , Find(7):
Grafos ponderados - AEM
Algoritmo de Kruskal – paso
a paso
Como podemos observar en la tabla y en la misma imagen no están
en la misma componente conexa, por tanto esta arista es valida para
el árbol de expansión mínima (MST) así que unimos los vértices por el
método de Union( 8 , 7 ).
Grafos ponderados - AEM
Algoritmo de Kruskal – paso
a paso
Continuamos con la siguiente arista:
Grafos ponderados - AEM
Algoritmo de Kruskal – paso
a paso
Observamos la tabla de Union-Find y vemos que Find(3) != Find(9).
Entonces es posible realizar la unión de ambas componentes:
Grafos ponderados - AEM
Algoritmo de Kruskal – paso
a paso
Continuamos con la siguiente arista:
Grafos ponderados - AEM
Algoritmo de Kruskal – paso
a paso
En la imagen podemos observar que ambos vértices no están en la
misma componente, por tanto realizamos la Union( 6 , 7 ):
Grafos ponderados - AEM
Algoritmo de Kruskal – paso
a paso
Continuamos con la siguiente arista, los vértices 1 y 2 no están en la
misma componente conexa:
Grafos ponderados - AEM
Algoritmo de Kruskal – paso
a paso
Realizamos la Union(1,2):
Grafos ponderados - AEM
Algoritmo de Kruskal – paso
a paso
Continuamos con la siguiente arista:
Grafos ponderados - AEM
Algoritmo de Kruskal – paso
a paso
Al observar la imagen los vértices 3 y 6 están en distinta componentes
conexas. Entonces realizamos la Union(3,6) y actualizamos la tabla de
Union-Find.
Grafos ponderados - AEM
Algoritmo de Kruskal – paso
a paso
Continuamos con la siguiente arista:
En
este
caso
si
observamos la imagen los
vértices 7 y 9 están en la
misma
componente
conexa; asimismo en la
tabla de Union-Find el
elemento raíz del vértice
7 es el mismo que el del
vértice
9
por
ello
afirmamos que están el a
misma
componente
conexa, por lo tanto no
habrá que realizar la
unión de ambos vértices.
Con esto evitamos tener
ciclos en el árbol de
expansión mínima.
Grafos ponderados - AEM
Algoritmo de Kruskal – paso
a paso
Continuamos con la siguiente arista:
Grafos ponderados - AEM
Algoritmo de Kruskal – paso
a paso
Al observar la imagen los vértices 3 y 4 no están en la misma
componente conexa por lo tanto realizamos la Union(3,4) en el grafo:
Grafos ponderados - AEM
Algoritmo de Kruskal – paso
a paso
Continuamos con la siguiente arista:
Grafos ponderados - AEM
Algoritmo de Kruskal – paso
a paso
Los vértices 8 y 9 están en la misma componente conexa por lo tanto
no realizamos Unión de vértices. Continuemos con la siguiente arista:
Grafos ponderados - AEM
Algoritmo de Kruskal – paso
a paso
Los vértices 1 y 8 están diferentes componentes. Realizamos la
Union(1,8) en el grafo:
Grafos ponderados - AEM
Algoritmo de Kruskal – paso
a paso
Continuamos con la siguiente arista:
Grafos ponderados - AEM
Algoritmo de Kruskal – paso
a paso
Los vértices 2 y 3 están en la misma componente conexa por lo tanto
no realizamos Union de componentes. Continuamos con la siguiente
arista:
Grafos ponderados - AEM
Algoritmo de Kruskal – paso
a paso
Los vértices 4 y 7 no están en la misma componente conexa,
realizamos Union(4,5) en el grafo:
Grafos ponderados - AEM
Algoritmo de Kruskal – paso
a paso
Como podemos observar ya están todos los vértices del grafo
conectados así que al momento de continuar viendo las demás
aristas ordenadas siempre tendremos e l caso de que ya están en la
misma componente conexa por lo tanto el Árbol de Expansión Mínima
para el grafo es el siguiente:
El peso total del árbol de expansión mínima para el grafo mostrado
es 39.
Grafos ponderados - AEM
Verificación del árbol de
expansión mínima (MST)
Para que sea un MST válido, el número de aristas debe ser igual
al número de vértices – 1. Esto se cumple debido a que el MST
debe poseer todos los vértices del grafo ingresado y además
no deben existir ciclos. Si vemos el ejemplo antes explicado
tenemos en el MST:
Número de Aristas = 8
Número de Vértices = 9
Cumple con lo dicho -> 9 – 1 = 8
por tanto tenemos un MST válido
Grafos ponderados - AEM
Union - Find
Union Find es una estructura de datos que modela una
colección de conjuntos disjuntos (disjoint-sets) y esta basado en
2 operaciones:
• Find( A ): Determina a cual conjunto pertenece el elemento A.
Esta operación puede ser usada para determinar si 2
elementos están o no en el mismo conjunto.
• Union( A, B ): Une todo el conjunto al que pertenece A con
todo el conjunto al que pertenece B, dando como resultado
un nuevo conjunto basado en los elementos tanto de A como
de B.
Estas operaciones servirán para la implementación del
algoritmo
de
Kruskal
o
problemas
que
involucran
particionamiento como encontrar las componentes conexas en
un grafo.
Grafos ponderados - AEM
Union - Find
Bosques de Conjuntos Disjuntos
En esta implementación representamos los conjuntos
como un árbol, donde cada nodo mantiene la
información de su nodo padre, la raíz del árbol será
el elemento representativo de todo el conjunto. Por
lo tanto basta con declarar un arreglo que contenga
los elementos del padre de un determinado
elemento.
Grafos ponderados - AEM
Union - Find
Método MakeSet
Es un método que inicializa los conjuntos.
Tengamos por ejemplo 9 vértices, inicializamos por medio de
MakeSet:
Una
vez
inicializado
podemos
unir
dos
componentes conexas o
preguntar con el método
find si un determinado
vértice pertenece a la
misma
componente
conexa de otro vértice.
Grafos ponderados - AEM
Union - Find
Método Find
Este método determina a cual componente conexa pertenece
un vértice X determinado, ello lo hace retornando el vértice raíz
del árbol en el que se encuentra el vértice X.
Por ejemplo tengamos las siguientes componentes conexas
vistas como arboles:
Deseo saber la
raíz
de
la
componente
conexa a la
que pertenece
el vértice 3.
Grafos ponderados - AEM
Union - Find
Al hacer Find( 3 ) partimos del vértice 3 y subimos hasta la raíz
viendo su padre, en este caso el padre[ 3 ] = 1 por lo tanto:
Grafos ponderados - AEM
Union - Find
El vértice actual ahora es el vértice 1 y hacemos lo mismo que
antes, padre[ 1 ] = 0.
Grafos ponderados - AEM
Union - Find
Ahora estamos en vértice 0, como el padre[ 0 ] = 0 entonces
estamos en la raíz y la retornamos.
Grafos ponderados - AEM
Union - Find
Método Union
Este método permite unir 2 componentes conexas,
ello se realiza por lo siguiente:
• Obtenemos la raíz del vértice x.
• Obtenemos la raíz del vértice y.
Actualizamos el padre de alguna de las raíces,
asignándole como nuevo padre la otra raíz.
Grafos ponderados - AEM
Union - Find
Por ejemplo:
Grafos ponderados - AEM
Union - Find
Como se pudo observar primero realizamos los pasos 1 y 2 para hallar
las raíces de ambos vértices y finalmente el paso 3 para actualizar el
padre de una de las componentes conexas, en este caso se
actualizará el padre de la componente conexa X. Continuemos:
Grafos ponderados - AEM
Union - Find
Al igual que el caso anterior el nuevo padre del vértice 7 es el vértice 0.
Grafos ponderados - AEM
Union - Find
En este caso hemos realizado Union( 3 , 1 ), entonces el nuevo padre
del vértice 3 es el vértice 1. Hasta el momento tenemos 6 componentes
conexas.
Grafos ponderados - AEM
Union - Find
En este caso estamos uniendo dos componentes con más vértices y
como se puede observar solo es necesario actualizar el puntero de la
raíz de una de las componentes.
Grafos ponderados - AEM
Union - Find
En la imagen anterior se hizo Union( 6 , 4 ) -> Union( 8 , 4 ) -> Union( 4 , 5 )
en ese orden.
En esta última imagen hemos unido todos los nodos obteniendo
una componente conexa.
Grafos ponderados - CMC
Camino mas corto
El problema del camino mas corto consiste en
encontrar entre todos los caminos que conectan a
dos vértices x e y dados de un grafo ponderado el
que cumple con la propiedad de que la suma de
las ponderaciones de todas las aristas sea mínima.
Si las ponderaciones son todas iguales a 1, entonces
el problema sigue siendo interesante: ahora consiste
en encontrar el camino que contenga al mínimo de
aristas que conecten a x e y.
Grafos ponderados - CMC
Algoritmo de Dijkstra
El algoritmo de Dijkstra determina la ruta más corta
desde un nodo origen hacia los demás nodos para
ello es requerido como entrada un grafo cuyas
aristas posean pesos.
Algunas consideraciones:
• Si los pesos de las aristas son de valor 1, entonces
bastará con usar el algoritmo de BFS.
• Si los pesos de las aristas son negativos no puedo
usar el algoritmo de dijsktra, para pesos negativos
tenemos otro algoritmo llamado Algoritmo de
Bellmand-Ford.
Grafos ponderados - CMC
Algoritmo de Dijkstra
Como trabaja:
Primero marcamos todos los vértices como no
utilizados. El algoritmo parte de un vértice
origen que será ingresado, a partir de ese
vértices evaluaremos sus adyacentes, como
dijkstra usa una técnica greedy -La técnica
greedy utiliza el principio de que para que un
camino sea óptimo, todos los caminos que
contiene también deben ser óptimos- entre
todos los vértices adyacentes, buscamos el
que esté más cerca de nuestro punto origen, lo
tomamos como punto intermedio y vemos si
podemos llegar más rápido a través de este
vértice a los demás. Después escogemos al
siguiente más cercano (con las distancias ya
actualizadas) y repetimos el proceso. Esto lo
hacemos hasta que el vértice no utilizado más
cercano sea nuestro destino. Al proceso de
actualizar las distancias tomando como punto
intermedio al nuevo vértice se le conoce como
relajación (relaxation).
Grafos ponderados - CMC
Algoritmo de Dijkstra
Pseudo-codigo:
Considerar
distancia[ i ]
como la
distancia
mas corta
del vértice
origen
ingresado al
vértice i.
1 método Dijkstra(Grafo,origen):
2
creamos una cola de prioridad Q
3
agregamos origen a la cola de prioridad Q
4
mientras Q no este vacío:
5
sacamos un elemento de la cola Q llamado u
6
si u ya fue visitado continuo sacando elementos de Q
7
marcamos como visitado u
8
para cada vértice v adyacente a u en el Grafo:
9
sea w el peso entre vértices ( u , v )
10
si v no ah sido visitado:
11
Relajacion( u , v , w )
1 método Relajacion( actual , adyacente , peso ):
2
si distancia[ actual ] + peso < distancia[ adyacente ]
3
distancia[ adyacente ] = distancia[ actual ] + peso
4
agregamos adyacente a la cola de prioridad Q
Grafos ponderados - CMC
Algoritmo de Dijkstra – paso
a paso
Tengamos el siguiente grafo, cuyos ID están en color negro encima de
cada vértice, los pesos esta en color azul y la distancia inicial en cada
vértice es infinito.
Grafos ponderados - CMC
Algoritmo de Dijkstra – paso
a paso
Inicializamos los valores de nuestros arreglos.
Donde:
•
•
•
•
Vértices: ID de los vértices.
Distancia[ u ]: Distancia mas corta desde vértice inicial a vértice con ID = u.
Visitado[ u ]: 0 si el vértice con ID = u no fue visitado y 1 si ya fue visitado.
Previo[ u ]: Almacenara el ID del vértice anterior al vértice con ID = u, me
servirá para impresión del camino mas corto.
Grafos ponderados - CMC
Algoritmo de Dijkstra – paso
a paso
De acuerdo al vértice inicial que elijamos cambiara la distancia inicial,
por ejemplo la ruta más corta partiendo del vértice 1 a todos los demás
vértices:
El vértice 1 es visitado, la distancia de vértice 1 -> vértice 1 es 0
por estar en el mismo lugar.
Grafos ponderados - CMC
Algoritmo de Dijkstra – paso
a paso
Hasta este momento la tabla quedaría de la siguiente manera.
Ahora vemos sus adyacentes
que no hayan sido visitados.
Tendríamos 2 y 4.
Grafos ponderados - CMC
Algoritmo de Dijkstra – paso
a paso
Evaluamos primero para vértice 2
Vemos que la distancia actual desde el vértice inicial a 2 es ∞,
verifiquemos el paso de relajación:
distancia[ 1 ] + 7 < distancia[ 2 ]
->
0+7<∞
->
7<∞
Grafos ponderados - CMC
Algoritmo de Dijkstra – paso
a paso
El paso de relajación es posible realizarlo entonces actualizamos la
distancia en el vértice 2 y agregando el vértice en la cola de prioridad
con nueva distancia quedando:
Grafos ponderados - CMC
Algoritmo de Dijkstra – paso
a paso
Ahora evaluamos al siguiente adyacente que es el vértice 4:
De manera similar al anterior vemos que la distancia actual desde el
vértice inicial a 4 es ∞, verifiquemos el paso de relajación:
distancia[ 1 ] + 2 < distancia[ 4 ]
->
0+2<∞
->
2<∞
Grafos ponderados - CMC
Algoritmo de Dijkstra – paso
a paso
El paso de relajación es posible realizarlo entonces actualizamos la
distancia en el vértice 4 quedando:
En cuanto a la cola de prioridad como tenemos un vértice con
menor peso este nuevo vértice ira en el tope de la cola:
Grafos ponderados - CMC
Algoritmo de Dijkstra – paso
a paso
Revisamos sus adyacentes no visitados que serian vértices 2, 3 y 5.
Grafos ponderados - CMC
Algoritmo de Dijkstra – paso
a paso
Evaluamos primero para vértice 2
Ahora vemos que la distancia actual del vértice inicial al vértice 2 es
7, verifiquemos el paso de relajación:
distancia[ 4 ] + 3 < distancia[ 2 ]
->
2+3<7
->
5<7
Grafos ponderados - CMC
Algoritmo de Dijkstra – paso
a paso
En esta oportunidad hemos encontrado una ruta mas corta partiendo
desde el vértice inicial al vértice 2, actualizamos la distancia en el
vértice 2 y actualizamos el vértice previo al actual quedando:
En cuanto a la cola de
prioridad como tenemos un
vértice con menor peso este
nuevo vértice ira en el tope de
la cola, podemos ver que
tenemos 2 veces el mismo
vértice pero como usamos una
técnica greedy siempre
usaremos el valor óptimo:
Grafos ponderados - CMC
Algoritmo de Dijkstra – paso
a paso
Continuamos con los Vértices 3 y 5 como tienen valor ? si será posible
relajarlos por lo que sería similar a los pasos iniciales solo que en los
pasos iniciales distancia[ 1 ] era 0 en este caso distancia[ 4 ] es 2,
quedando:
Grafos ponderados - CMC
Algoritmo de Dijkstra – paso
a paso
Hemos terminado de evaluar al vértice 4, continuamos con el tope de
la cola que es vértice 2, el cual marcamos como visitado.
Grafos ponderados - CMC
Algoritmo de Dijkstra – paso
a paso
Los adyacentes no visitados del vértice 2 son los vértices 3 y 5.
Comencemos con el vértice 3.
Ahora vemos que la distancia actual del vértice inicial al vértice 3 es
10, verifiquemos el paso de relajación:
distancia[ 2 ] + 1 < distancia[ 3 ]
->
5 + 1 < 10
->
6 < 10
Grafos ponderados - CMC
Algoritmo de Dijkstra – paso
a paso
En esta oportunidad hemos encontrado una ruta mas corta partiendo
desde el vértice inicial al vértice 3, dicha ruta sería 1 -> 4 -> 2 -> 3 cuyo
peso es 6 que es mucho menor que la ruta 1 – > 4 -> 3 cuyo peso es 10,
actualizamos la distancia en el vértice 3 quedando:
Grafos ponderados - CMC
Algoritmo de Dijkstra – paso
a paso
El siguiente vértice de la cola de prioridad es el vértice 3 y su único
adyacente no visitado es el vértice 5.
Vemos que la distancia actual del vértice inicial al vértice 5 es 7,
verifiquemos el paso de relajación:
distancia[ 3 ] + 5 < distancia[ 5 ]
->
6+5<7
->
11 < 7
Grafos ponderados - CMC
Algoritmo de Dijkstra – paso
a paso
En esta oportunidad se no cumple por lo que no relajamos el vértice 5,
por lo que la tabla en cuanto a distancias no sufre modificaciones y no
agregamos vértices a la cola:
Grafos ponderados - CMC
Algoritmo de Dijkstra – paso
a paso
Ahora tocaría el vértice 2 pero como ya fue visitado seguimos
extrayendo elementos de la cola, el siguiente vértice será el 5.
Grafos ponderados - CMC
Algoritmo de Dijkstra – paso
a paso
Al ser el ultimo vértice a evaluar no posee adyacentes sin visitar por lo
tanto hemos terminado el algoritmo. En el grafico anterior observamos
que 2 aristas no fueron usadas para la relajación, las demás si fueron
usadas. La tabla final quedaría de la siguiente manera:
De la tabla si deseo saber la distancia mas corta del
vértice 1 al vértice 5, solo tengo que acceder al valor
del arreglo en su índice respectivo (distancia[ 5 ]).
Grafos ponderados - CMC
Algoritmo de Dijkstra –
Impresión camino encontrado
En el proceso anterior usábamos el arreglo previo[ u ] para almacenar
el ID del vértice previo al vértice con ID = u, ello me sirve para formar el
árbol de la ruta mas corta y además me sirve para imprimir caminos de
la ruta mas corta.
Grafos ponderados - CMC
Algoritmo de Dijkstra –
Impresión camino encontrado
Para imprimir el camino mas corto deseado usamos el arreglo previo[ u ],
donde u tendrá el ID del vértice destino, o sea si quiero imprimir el
camino mas corto desde vértice 1 -> vértice 3 partiré desde previo[ 3 ]
hasta el previo[ 1 ].
Veamos gráficamente el funcionamiento, desde el grafo comenzamos
en 3
Grafos ponderados - CMC
Algoritmo de Dijkstra –
Impresión camino encontrado
El previo de 3 es el vértice 2, por lo tanto ahora evaluó 2:
Grafos ponderados - CMC
Algoritmo de Dijkstra –
Impresión camino encontrado
Ahora el previo de 2 es el vértice 4:
Grafos ponderados - CMC
Algoritmo de Dijkstra –
Impresión camino encontrado
El previo de 4 es el vértice inicial 1
Como el previo de 1 es -1 terminamos el recorrido, ahora en el
retorno de las llamadas recursivas imprimo el camino: 1 4 2 3
Tópicos I
Unidad I
Árboles, montículos y grafos
Semana 4
Algoritmos sobre grafos elementales, Conectividad
y Grafos ponderados