Tópicos I Unidad I Algoritmos sobre grafos elementales, Conectividad y Grafos ponderados Semana 4 Árboles, montículos y grafos.

  • Published on
    02-Feb-2016

  • View
    261

  • Download
    0

Transcript

  • Tpicos IAlgoritmos sobre grafos elementales, Conectividad y Grafos ponderadosSemana 4rboles, montculos y grafos

  • Objetivos GeneralesEntender el manejo, uso de algoritmos y estructuras de datos avanzados, haciendo nfasis en los algoritmos de internet, seguridad y redes.

  • Objetivo EspecficoImplementar algoritmos utilizando estructura de datos avanzadas.

  • Objetivo InstruccionalImplementar algoritmos fundamentales para la solucin de problemas basados en la teora de grafos.

  • GlosarioGrafo: Un grafo es una coleccin de vrtices y aristas. Los vrtices son objetos simples que pueden tener un nombre y otras propiedades; una arista es una conexin entre dos vrtices.

    Camino: Un camino entre los vrtices x e y de un grafo es una lista de vrtices en la que dos elementos sucesivos estn conectados por aristas del grafo.

  • GlosarioGrafo conexo: Un grafo es conexo si hay un camino desde cada nodo hacia otro nodo del grafo.

    Grafo no conexo: Esta constituido por componentes conexos.

    Camino simple: Es un camino en el que no se repite ningn vrtice.

    Ciclo: es un camino simple con la caracterstica de que el primero y el ultimo vrtices son el mismo.

  • GlosarioGrafo completo: Son los grafos con todas las aristas posibles.

    Grafo disperso: Tienen relativamente pocas aristas.

    Grafo denso: Les falta muy pocas aristas de todas las posibles.

  • RepresentacinMatriz de adyacencia:

    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 vrtice x al y, y a 0 en el caso contrario.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].La matriz de adyacencia solo es satisfactoria si los grafos a procesar son densos.

    ABCDEFGA1110011B1100000C1010000D0001110E0001111F1001110G1000101

  • RepresentacinLista de adyacencia:

    La lista de adyacencia se adapta mejor a lo casos en los que los grafos a procesar no son densos.FAAAABCGEFDDFGEE

    ABCDEFG

  • Recorridos en un grafoEn una gran cantidad de problemas con grafos, es necesario visitar sistemticamente los vrtices y aristas del grafo.

    La bsqueda en PROFUNDIDAD y en AMPLITUD, son dos tcnicas importantes de recorrido del grafo.

  • Bsqueda en Profundidad (BEP)Se comienza en el vrtice inicial (vrtice con ndice 1) que se marca como vrtice activo. Hasta que todos los vrtices hayan sido visitados, en cada paso se avanza al vecino con el menor ndice siempre que se pueda, pasando este a ser el vrtice activo. Cuando todos los vecinos al vrtice activo hayan sido visitados, se retrocede al vrtice X desde el que se alcanz el vrtice activo y se prosigue siendo ahora X el vrtice activo.

  • Bsqueda en ProfundidadLa estructura utilizada para guardar los nodos a visitar en este tipo de bsqueda es una pila o stack (de procedimiento recursivo).

  • Bsqueda en Amplitud (BEA)Se comienza en el vrtice inicial (vrtice con ndice 1) y se marca como vrtice activo, a diferencia con la BEP ahora se visitan en orden creciente de ndice todos los vecinos del vrtice activo antes de pasar al siguiente. Hasta que todos los vrtices hayan sido visitados, en cada paso se van visitando en orden creciente de ndice todos los vecinos del vrtice activo. Cuando se han visitado todos los vecinos del vrtice activo, se toma como nuevo vrtice activo el primer vrtice X visitado despus del actual vrtice activo.

  • Bsqueda en AmplitudEn la bsqueda en amplitud se utiliza una cola para guardar tales nodos a visitar.

  • Usos de los RecorridosAmbos recorridos se pueden usar para resolver los siguientes problemas:Probar que G es conectado.Obtener un rbol de expansin de G.Obtener los componentes conectados de G.Obtener un camino entre dos vrtices 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 vrtice v de G, el nmero mnimo de aristas de cualquier camino entre s y v.

  • LaberintosLa bsqueda en profundidad fue expuesta formalmente como un mtodo para recorrer laberintos.El grafo se construye colocando un vrtice en cada punto en el que existe mas de un camino a tomar y a conectar a continuacin los vrtices de acuerdo con esos caminos.La bsqueda en profundidad es apropiada para la bsqueda de un elemento en el laberinto por una sola persona, dado que el siguiente lugar a visitar esta siempre prximo; la bsqueda es amplitud es mas apropiada par un grupo de personas que buscan el mismo elemento desplazndose en todas las direcciones a la vez

  • ProblemticaSe examinara una generalizacin de la conectividad denominada biconectividad, cuyo inters reside en conocer si hay mas de un medio de pasar de un vrtice 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 vrtices. De esta forma si se suprime un vrtice y todas las aristas que inciden en el, el grafo permanece conexo.Si para algunas aplicaciones es importante que un grafo sea conexo, es tambin importante que permanezca conexo

  • ProblemticaUna versin particular del problema de la conectividad, que con frecuencia concierne a la situacin dinmica en las que las aristas se aaden al grafo una a una, intercalando preguntas sobre si dos vrtices determinados pertenecen (o no) a la misma componente conexa.

    El problema se denomina a veces como unin-pertenencia.

  • Componentes conexasDe un grafo no dirigidoSe pude saber si es conexoSi no lo es se pueden conocer sus Componentes ConexasConjunto W, de vrtices del grafoEn el cual hay camino desde cualquier V1 a cualquier V2 Donde V1 y V2 pertenecen a W

    CONEXONo CONEXOComponentes conexas: entre ellas son conexas

  • BiconectividadA veces es til disear mas de una ruta entre puntos de un grafo, aunque solo sea para identificar posibles fallos en los puntos de conexin (vrtices). Esto nos permitira tener recorridos alternativos por ejemplo para llegar de una ciudad a otra.

  • Puntos de articulacinEn un grafo no dirigido conexo:Existen vrtices que si se eliminanDesconectan al GrafoLo dividen en componentes conexasEstos vrtices clave son puntos de articulacinSi un grafo no tiene Punto de ArticulacinEs biconexoLa conectividad de un grafoEs el numero de nodos que se necesitan eliminar para dejar a un grafo desconectadoUn punto de articulacin en un grafo conexo es un vrtice que si se suprime romper el grafo en dos o mas piezas.

  • EjemploPuntos de ArticulacinPuntos de articulacin

  • rbol de expansinDefinicin: Un rbol T es un rbol de expansin de un grafo G si T es un subgrafo que contiene a todos los vrtices de G.

  • rbol de expansinPara poder calcular los Puntos de Articulacin de un grafoHay que obtener el rbol de expansinEste se obtieneA partir del Recorrido en Profundidad

    Ejemplo:

    Arco en Retroceso: Cuando se quiere visitar un nodo que ya ha sido visitado y no es el padre

  • Como representar el rbol de expansinUn rbol en expansinNo es un rbol binarioCada Vrtice puede tener 0, 1 o n hijos

    Si no tomamos en cuenta los arcos en retroceso, la representacin depende del GrafoMatriz de Adyacencia -> Usar un arreglo Lista de Adyacencia -> Una lista

    La representacin mostrar quien es el padre de cada nodo

  • rbol de expansin con matriz de adyacenciaLos vrtices del grafoSe encuentran en un arregloCada ndice del arregloRepresenta un vrticeEj: A 0, B 1, etc.Al representar el rbol de expansinEl padre(ndice) de cada nodo puede almacenarse en un arregloQue tambin represente a los vrtices

    0400520A1B2C3D4E5Ftypedef struct TVertices{Generico V[MAX];int Padres[MAX];int nvertices;}Vertices;

  • rbol de expansin con lista de adyacenciaLos vrtices del grafoSe encuentran en una listaCada nodo representa un vrticeAl representar el rbol de expansinDe cada nodo de esta lista solo nos interesa conocer al padreSe puede aadir un dato al nodo vrticeUn enlace con el padreADCBEFtypedef struct Vertice{ Generico Informacion; Vertice *padre; Lista *LArcos;}Vertice;

  • Unin - PertenenciaEn algunas aplicaciones se desea simplemente conocer si un vrtice x esta o no conectado a un vrtice 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 vrtices representan a los objetos y las aristas significan esta en el mismo conjunto que.

    ABCGDEF{A F D E} {B C G}Conjuntos clases de equivalenciaCada componente conexa corresponde a una clase de equivalencia diferente

  • Unin - PertenenciaEl aadir una arista se corresponde con la combinacin de las clases de equivalencia representadas por los vrtices a conectar.

    El inters 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 vrtice x conectado al vrtice y?

    Dado un conjunto de aristas, se puede construir una representacin por lista de adyacencia que corresponda al grafo y utilizar la bsqueda en profundidad para asignar a cada vrtice el ndice de su correspondiente conexa y responder a las preguntas antes planteada con tal solo dos accesos a arrays y una comparacin

  • Unin - PertenenciaPor correspondencia con el problema de los conjuntos, la adicin de una nueva arista se denomina una operacin de unin, y las preguntas se denominan operaciones de pertenencia.

    El objetivo es escribir una funcin que pueda verificar si dos vrtices x e y pertenecen al mismo conjunto (o, en representacin 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 representacin de los grafos, es mas eficaz utilizar una estructura interna orientada especficamente a la realizacin de las operaciones unin y pertenencia.

  • Unin - PertenenciaEsta estructura interna es un bosque de arboles, uno por cada componente conexa.

    Se necesita poder encontrar si dos vrtices pertenecen al mismo rbol y combinar dos arboles en uno.

  • Unin - PertenenciaPara ilustrar como trabaja este algoritmo, vamos a ver el bosque construido por los siguientes vrtices (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 estn en rboles separados (cada vrtice es un rbol). ABCDEFGHIJKLM

  • Unin - PertenenciaLuego la arista AG crea un rbol de dos nodos con A como raz (esta decisin es arbitraria, porque tranquilamente podramos haber puesto G como raz). Las aristas AB y AC agregan B y C al rbol de la misma forma.

  • Unin - PertenenciaProceso culminado

  • Unin - PertenenciaEs necesario recalcar que, al contrario que en los rboles de bsqueda primero en profundidad, la nica relacin entre estos rboles de unin y el grafo original con las aristas dadas es que dividen a los vrtices 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 representacin enlace padre" porque siempre se viaja hacia arriba en los rboles, nunca hacia abajo. Especficamente, mantenemos un array padre que contiene, para cada vrtice, el ndice de su padre (0 si es la raz de algn rbol), como se especifica en la prxima declaracin de la clase:

  • Unin - Pertenenciaclass 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 cdigo). Se usa un solo procedimiento find para implementar ambos, la unin y la bsqueda. Si el tercer argumento es 0 se hace una bsqueda, si no es 0, se hace una unin. Para encontrar al padre del vrtice j, simplemente se hace j = dad[j], y para encontrar la raz del rbol al que pertenece j se repite esta operacin hasta que se llega a 0.

  • Unin - PertenenciaEsto nos lleva a la siguiente implementacin 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 funcin find retorna 0 si los dos vrtices dados estn en el mismo componente. Si no lo estn y el flag doit esta seteado, son puestos en el mismo componente. El mtodo es simple. Usar el array dad para llegar a la raz del rbol que contiene cada vrtice, luego chequear si las races son las mismas. Para mezclar el rbol con raz j con el rbol de raz i simplemente se setea dad[j] = i.

  • Unin - PertenenciaContenido de la estructura de datos union-pertenencia durante el proceso

  • Unin - PertenenciaEl algoritmo descrito anteriormente tiene un mal desempeo 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.

  • Unin - PertenenciaVarios mtodos han sido sugeridos para lidiar con esta dificultad. Un mtodo natural es tratar de hacer lo correcto para mezclar dos rboles, en lugar de hacer arbitrariamente dad[ j ] = i. Cuando un rbol con raz en i va a ser mezclado con otro con raz en j, uno de los nodos debe mantenerse como raz y el otro (y todos sus descendientes) deben ir un nivel ms abajo en el rbol.

    Para minimizar la distancia a la raz de la mayora de los nodos tiene sentido elegir como raz el nodo con ms descendientes.

  • Unin - PertenenciaEsta idea, llamada equilibrado de peso, es fcilmente implementable manteniendo el tamao de cada rbol (cantidad de descendientes de la raz) en el array dad para cada nodo raz, codificado como un nmero no positivo de tal modo que el nodo raz pueda ser detectado cuando se viaja hacia arriba en el rbol con find.

  • Unin - PertenenciaIdealmente se deseara que cada nodo apuntara directamente a la raz 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 raz que find generalmente examina. Sin embargo podemos aproximarnos a este ideal haciendo que todos los nodos que s se examinan apunten a la raz. Este mtodo, conocido como compresin de caminos, se implementa fcilmente haciendo otra pasada por cada rbol, despus de que la raz fue encontrada, y seteando la entrada dad de cada vrtice encontrado a lo largo del camino para que apunte a la raz.

  • Unin - PertenenciaLa combinacin de compresin de caminos y equilibrado de peso nos aseguran que los algoritmos van a correr muy rpido. La siguiente implementacin muestra que el cdigo extra necesario es un pequeo 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 );}

  • Unin - PertenenciaProceso culminado al aplicar el mtodo, equilibrado, con compresin de caminos

  • Unin - PertenenciaContenido de la estructura de datos union-pertenencia durante el proceso con el mtodo equilibrado, con compresin de caminos

  • ProblemticaCon frecuencia se desea modelar problemas prcticos utilizando grafos en los que se asocia a las aristas unos pesos o costes.En un mapa de lneas areas, 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.

  • ProblemticaSe examinara los algoritmos de dos de estos problemas:

    Encontrar la forma de conectar todos los puntos al menor coste (problema del rbol de expansin mnima).

    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 representacin por matriz de adyacencia, la matriz puede contener pesos de aristas en lugar de valores booleanos y en la representacin por listas de adyacencia se puede aadir un campo a cada elemento de la lista, a manera de peso.

  • rbol de expansin mnimoUn rbol de expansin mnimo de un grafo ponderado es una coleccin de aristas que conectan todos los vrtices 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 coleccin de aristas que conecten todos los vrtices.

  • Algoritmo genricoSe puede construir el rbol de expansin mnimo comenzando en cualquier vrtice y tomando siempre el vrtice mas prximo de todos los que se hayan elegido.

    En otras palabras, se busca la arista de menor peso entre todas las que conectan vrtices que ya estn en el rbol con vrtices que no lo estn todava, y despus se aade al rbol la arista y el vrtice a los que conduce la anterior.

  • Algoritmo de KruskalSe puede construir el rbol de expansin mnimo comenzando en cualquier vrtice y tomando siempre el vrtice mas prximo de todos los que se hayan elegido.

    En otras palabras, se busca la arista de menor peso entre todas las que conectan vrtices que ya estn en el rbol con vrtices que no lo estn todava, y despus se aade al rbol la arista y el vrtice a los que conduce la anterior.

  • Algoritmo de Kruskal paso a pasoTengamos el siguiente grafo no dirigido.

  • Algoritmo de Kruskal paso a pasoEn primer lugar usaremos el mtodo MakeSet de unin-find (revisar) para inicializar cada componente, obteniendo las siguientes componentes conexas iniciales:

  • Algoritmo de Kruskal paso a pasoAhora el siguiente paso es ordenar las aristas del grafo en orden ascendente:

  • Algoritmo de Kruskal paso a pasoLo siguiente ser recorrer todas las aristas ya ordenadas y verificar si sus vrtices estn o no en la misma componente.

    La primera arista a verificar es la que une a los vrtices 8 y 7, verificamos si estn en la misma componente, para ello hacemos Find(8) , Find(7):

  • Algoritmo de Kruskal paso a pasoComo podemos observar en la tabla y en la misma imagen no estn en la misma componente conexa, por tanto esta arista es valida para el rbol de expansin mnima (MST) as que unimos los vrtices por el mtodo de Union( 8 , 7 ).

  • Algoritmo de Kruskal paso a pasoContinuamos con la siguiente arista:

  • Algoritmo de Kruskal paso a pasoObservamos la tabla de Union-Find y vemos que Find(3) != Find(9). Entonces es posible realizar la unin de ambas componentes:

  • Algoritmo de Kruskal paso a pasoContinuamos con la siguiente arista:

  • Algoritmo de Kruskal paso a pasoEn la imagen podemos observar que ambos vrtices no estn en la misma componente, por tanto realizamos la Union( 6 , 7 ):

  • Algoritmo de Kruskal paso a pasoContinuamos con la siguiente arista, los vrtices 1 y 2 no estn en la misma componente conexa:

  • Algoritmo de Kruskal paso a pasoRealizamos la Union(1,2):

  • Algoritmo de Kruskal paso a pasoContinuamos con la siguiente arista:

  • Algoritmo de Kruskal paso a pasoAl observar la imagen los vrtices 3 y 6 estn en distinta componentes conexas. Entonces realizamos la Union(3,6) y actualizamos la tabla de Union-Find.

  • Algoritmo de Kruskal paso a pasoContinuamos con la siguiente arista:En este caso si observamos la imagen los vrtices 7 y 9 estn en la misma componente conexa; asimismo en la tabla de Union-Find el elemento raz del vrtice 7 es el mismo que el del vrtice 9 por ello afirmamos que estn el a misma componente conexa, por lo tanto no habr que realizar la unin de ambos vrtices. Con esto evitamos tener ciclos en el rbol de expansin mnima.

  • Algoritmo de Kruskal paso a pasoContinuamos con la siguiente arista:

  • Algoritmo de Kruskal paso a pasoAl observar la imagen los vrtices 3 y 4 no estn en la misma componente conexa por lo tanto realizamos la Union(3,4) en el grafo:

  • Algoritmo de Kruskal paso a pasoContinuamos con la siguiente arista:

  • Algoritmo de Kruskal paso a pasoLos vrtices 8 y 9 estn en la misma componente conexa por lo tanto no realizamos Unin de vrtices. Continuemos con la siguiente arista:

  • Algoritmo de Kruskal paso a pasoLos vrtices 1 y 8 estn diferentes componentes. Realizamos la Union(1,8) en el grafo:

  • Algoritmo de Kruskal paso a pasoContinuamos con la siguiente arista:

  • Algoritmo de Kruskal paso a pasoLos vrtices 2 y 3 estn en la misma componente conexa por lo tanto no realizamos Union de componentes. Continuamos con la siguiente arista:

  • Algoritmo de Kruskal paso a pasoLos vrtices 4 y 7 no estn en la misma componente conexa, realizamos Union(4,5) en el grafo:

  • Algoritmo de Kruskal paso a pasoComo podemos observar ya estn todos los vrtices del grafo conectados as que al momento de continuar viendo las dems aristas ordenadas siempre tendremos e l caso de que ya estn en la misma componente conexa por lo tanto el rbol de Expansin Mnima para el grafo es el siguiente:El peso total del rbol de expansin mnima para el grafo mostrado es 39.

  • Verificacin del rbol de expansin mnima (MST)Para que sea un MST vlido, el nmero de aristas debe ser igual al nmero de vrtices 1. Esto se cumple debido a que el MST debe poseer todos los vrtices del grafo ingresado y adems no deben existir ciclos. Si vemos el ejemplo antes explicado tenemos en el MST:

    Nmero de Aristas = 8 Nmero de Vrtices = 9Cumple con lo dicho -> 9 1 = 8 por tanto tenemos un MST vlido

  • Union - FindUnion Find es una estructura de datos que modela una coleccin de conjuntos disjuntos (disjoint-sets) y esta basado en 2 operaciones:

    Find( A ): Determina a cual conjunto pertenece el elemento A. Esta operacin puede ser usada para determinar si 2 elementos estn 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 servirn para la implementacin del algoritmo de Kruskal o problemas que involucran particionamiento como encontrar las componentes conexas en un grafo.

  • Union - FindBosques de Conjuntos Disjuntos

    En esta implementacin representamos los conjuntos como un rbol, donde cada nodo mantiene la informacin de su nodo padre, la raz 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.

  • Union - FindMtodo MakeSet

    Es un mtodo que inicializa los conjuntos.Tengamos por ejemplo 9 vrtices, inicializamos por medio de MakeSet:Una vez inicializado podemos unir dos componentes conexas o preguntar con el mtodo find si un determinado vrtice pertenece a la misma componente conexa de otro vrtice.

  • Union - FindMtodo Find

    Este mtodo determina a cual componente conexa pertenece un vrtice X determinado, ello lo hace retornando el vrtice raz del rbol en el que se encuentra el vrtice X.Por ejemplo tengamos las siguientes componentes conexas vistas como arboles:Deseo saber la raz de la componente conexa a la que pertenece el vrtice 3.

  • Union - FindAl hacer Find( 3 ) partimos del vrtice 3 y subimos hasta la raz viendo su padre, en este caso el padre[ 3 ] = 1 por lo tanto:

  • Union - FindEl vrtice actual ahora es el vrtice 1 y hacemos lo mismo que antes, padre[ 1 ] = 0.

  • Union - FindAhora estamos en vrtice 0, como el padre[ 0 ] = 0 entonces estamos en la raz y la retornamos.

  • Union - FindMtodo Union

    Este mtodo permite unir 2 componentes conexas, ello se realiza por lo siguiente:

    Obtenemos la raz del vrtice x.Obtenemos la raz del vrtice y.

    Actualizamos el padre de alguna de las races, asignndole como nuevo padre la otra raz.

  • Union - FindPor ejemplo:

  • Union - FindComo se pudo observar primero realizamos los pasos 1 y 2 para hallar las races de ambos vrtices 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:

  • Union - FindAl igual que el caso anterior el nuevo padre del vrtice 7 es el vrtice 0.

  • Union - FindEn este caso hemos realizado Union( 3 , 1 ), entonces el nuevo padre del vrtice 3 es el vrtice 1. Hasta el momento tenemos 6 componentes conexas.

  • Union - FindEn este caso estamos uniendo dos componentes con ms vrtices y como se puede observar solo es necesario actualizar el puntero de la raz de una de las componentes.

  • Union - FindEn 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.

  • Camino mas cortoEl problema del camino mas corto consiste en encontrar entre todos los caminos que conectan a dos vrtices 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 mnima.

    Si las ponderaciones son todas iguales a 1, entonces el problema sigue siendo interesante: ahora consiste en encontrar el camino que contenga al mnimo de aristas que conecten a x e y.

  • Algoritmo de DijkstraEl algoritmo de Dijkstra determina la ruta ms corta desde un nodo origen hacia los dems 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.

  • Algoritmo de DijkstraComo trabaja:Primero marcamos todos los vrtices como no utilizados. El algoritmo parte de un vrtice origen que ser ingresado, a partir de ese vrtices evaluaremos sus adyacentes, como dijkstra usa una tcnica greedy -La tcnica greedy utiliza el principio de que para que un camino sea ptimo, todos los caminos que contiene tambin deben ser ptimos- entre todos los vrtices adyacentes, buscamos el que est ms cerca de nuestro punto origen, lo tomamos como punto intermedio y vemos si podemos llegar ms rpido a travs de este vrtice a los dems. Despus escogemos al siguiente ms cercano (con las distancias ya actualizadas) y repetimos el proceso. Esto lo hacemos hasta que el vrtice no utilizado ms cercano sea nuestro destino. Al proceso de actualizar las distancias tomando como punto intermedio al nuevo vrtice se le conoce como relajacin (relaxation).

  • Algoritmo de DijkstraPseudo-codigo:Considerar distancia[ i ] como la distancia mas corta del vrtice origen ingresado al vrtice i.1 mtodo Dijkstra(Grafo,origen):2 creamos una cola de prioridad Q3 agregamos origen a la cola de prioridad Q4 mientras Q no este vaco:5 sacamos un elemento de la cola Q llamado u6 si u ya fue visitado continuo sacando elementos de Q 7 marcamos como visitado u8 para cada vrtice v adyacente a u en el Grafo:9 sea w el peso entre vrtices ( u , v ) 10 si v no ah sido visitado:11 Relajacion( u , v , w )

    1 mtodo Relajacion( actual , adyacente , peso ):2 si distancia[ actual ] + peso < distancia[ adyacente ]3 distancia[ adyacente ] = distancia[ actual ] + peso4 agregamos adyacente a la cola de prioridad Q

  • Algoritmo de Dijkstra paso a pasoTengamos el siguiente grafo, cuyos ID estn en color negro encima de cada vrtice, los pesos esta en color azul y la distancia inicial en cada vrtice es infinito.

  • Algoritmo de Dijkstra paso a pasoInicializamos los valores de nuestros arreglos.Donde:

    Vrtices: ID de los vrtices.Distancia[ u ]: Distancia mas corta desde vrtice inicial a vrtice con ID = u.Visitado[ u ]: 0 si el vrtice con ID = u no fue visitado y 1 si ya fue visitado.Previo[ u ]: Almacenara el ID del vrtice anterior al vrtice con ID = u, me servir para impresin del camino mas corto.

  • Algoritmo de Dijkstra paso a pasoDe acuerdo al vrtice inicial que elijamos cambiara la distancia inicial, por ejemplo la ruta ms corta partiendo del vrtice 1 a todos los dems vrtices:El vrtice 1 es visitado, la distancia de vrtice 1 -> vrtice 1 es 0 por estar en el mismo lugar.

  • Algoritmo de Dijkstra paso a pasoHasta este momento la tabla quedara de la siguiente manera.Ahora vemos sus adyacentes que no hayan sido visitados. Tendramos 2 y 4.

  • Algoritmo de Dijkstra paso a pasoEvaluamos primero para vrtice 2Vemos que la distancia actual desde el vrtice inicial a 2 es , verifiquemos el paso de relajacin:

    distancia[ 1 ] + 7 < distancia[ 2 ] -> 0 + 7 < -> 7 <

  • Algoritmo de Dijkstra paso a pasoEl paso de relajacin es posible realizarlo entonces actualizamos la distancia en el vrtice 2 y agregando el vrtice en la cola de prioridad con nueva distancia quedando:

  • Algoritmo de Dijkstra paso a pasoAhora evaluamos al siguiente adyacente que es el vrtice 4:De manera similar al anterior vemos que la distancia actual desde el vrtice inicial a 4 es , verifiquemos el paso de relajacin:

    distancia[ 1 ] + 2 < distancia[ 4 ] -> 0 + 2 < -> 2 <

  • Algoritmo de Dijkstra paso a pasoEl paso de relajacin es posible realizarlo entonces actualizamos la distancia en el vrtice 4 quedando:En cuanto a la cola de prioridad como tenemos un vrtice con menor peso este nuevo vrtice ira en el tope de la cola:

  • Algoritmo de Dijkstra paso a pasoRevisamos sus adyacentes no visitados que serian vrtices 2, 3 y 5.

  • Algoritmo de Dijkstra paso a pasoEvaluamos primero para vrtice 2Ahora vemos que la distancia actual del vrtice inicial al vrtice 2 es 7, verifiquemos el paso de relajacin:

    distancia[ 4 ] + 3 < distancia[ 2 ] -> 2 + 3 < 7 -> 5 < 7

  • Algoritmo de Dijkstra paso a pasoEn esta oportunidad hemos encontrado una ruta mas corta partiendo desde el vrtice inicial al vrtice 2, actualizamos la distancia en el vrtice 2 y actualizamos el vrtice previo al actual quedando:En cuanto a la cola de prioridad como tenemos un vrtice con menor peso este nuevo vrtice ira en el tope de la cola, podemos ver que tenemos 2 veces el mismo vrtice pero como usamos una tcnica greedy siempre usaremos el valor ptimo:

  • Algoritmo de Dijkstra paso a pasoContinuamos con los Vrtices 3 y 5 como tienen valor ? si ser posible relajarlos por lo que sera similar a los pasos iniciales solo que en los pasos iniciales distancia[ 1 ] era 0 en este caso distancia[ 4 ] es 2, quedando:

  • Algoritmo de Dijkstra paso a pasoHemos terminado de evaluar al vrtice 4, continuamos con el tope de la cola que es vrtice 2, el cual marcamos como visitado.

  • Algoritmo de Dijkstra paso a pasoLos adyacentes no visitados del vrtice 2 son los vrtices 3 y 5. Comencemos con el vrtice 3.Ahora vemos que la distancia actual del vrtice inicial al vrtice 3 es 10, verifiquemos el paso de relajacin:

    distancia[ 2 ] + 1 < distancia[ 3 ] -> 5 + 1 < 10 -> 6 < 10

  • Algoritmo de Dijkstra paso a pasoEn esta oportunidad hemos encontrado una ruta mas corta partiendo desde el vrtice inicial al vrtice 3, dicha ruta sera 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 vrtice 3 quedando:

  • Algoritmo de Dijkstra paso a pasoEl siguiente vrtice de la cola de prioridad es el vrtice 3 y su nico adyacente no visitado es el vrtice 5.Vemos que la distancia actual del vrtice inicial al vrtice 5 es 7, verifiquemos el paso de relajacin:

    distancia[ 3 ] + 5 < distancia[ 5 ] -> 6 + 5 < 7 -> 11 < 7

  • Algoritmo de Dijkstra paso a pasoEn esta oportunidad se no cumple por lo que no relajamos el vrtice 5, por lo que la tabla en cuanto a distancias no sufre modificaciones y no agregamos vrtices a la cola:

  • Algoritmo de Dijkstra paso a pasoAhora tocara el vrtice 2 pero como ya fue visitado seguimos extrayendo elementos de la cola, el siguiente vrtice ser el 5.

  • Algoritmo de Dijkstra paso a pasoAl ser el ultimo vrtice 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 relajacin, las dems si fueron usadas. La tabla final quedara de la siguiente manera:De la tabla si deseo saber la distancia mas corta del vrtice 1 al vrtice 5, solo tengo que acceder al valor del arreglo en su ndice respectivo (distancia[ 5 ]).

  • Algoritmo de Dijkstra Impresin camino encontradoEn el proceso anterior usbamos el arreglo previo[ u ] para almacenar el ID del vrtice previo al vrtice con ID = u, ello me sirve para formar el rbol de la ruta mas corta y adems me sirve para imprimir caminos de la ruta mas corta.

  • Algoritmo de Dijkstra Impresin camino encontradoPara imprimir el camino mas corto deseado usamos el arreglo previo[ u ], donde u tendr el ID del vrtice destino, o sea si quiero imprimir el camino mas corto desde vrtice 1 -> vrtice 3 partir desde previo[ 3 ] hasta el previo[ 1 ]. Veamos grficamente el funcionamiento, desde el grafo comenzamos en 3

  • Algoritmo de Dijkstra Impresin camino encontradoEl previo de 3 es el vrtice 2, por lo tanto ahora evalu 2:

  • Algoritmo de Dijkstra Impresin camino encontradoAhora el previo de 2 es el vrtice 4:

  • Algoritmo de Dijkstra Impresin camino encontradoEl previo de 4 es el vrtice inicial 1Como el previo de 1 es -1 terminamos el recorrido, ahora en el retorno de las llamadas recursivas imprimo el camino: 1 4 2 3

  • Tpicos ISemana 4Algoritmos sobre grafos elementales, Conectividad y Grafos ponderadosrboles, montculos y grafos

Recommended

View more >