CAMINO MAS CORTO: ALGORITMO DE BELLMAN-FORD

En esta oportunidad se explicará el algoritmo de Bellman-Ford para hallar la ruta más corta, comenzaremos con una breve introducción al problema de hallar la ruta más corta sobre pesos negativos y luego continuaremos con el algoritmo de Bellman-ford.

Algoritmo de Dijkstra y Pesos Negativos

Si el grafo posee pesos negativos, el algoritmo de Dijkstra puede producir respuestas incorrectas. Por ejemplo tengamos el siguiente grafo:

grafo0

Si deseo la ruta más corta partiendo desde el vértice 1 según dijkstra la ruta más corte de vértice 1 al vértice 3 sería 2. Sin embargo la ruta más corta en realidad es de 1 (1 -> 2 -> 4 ->3).

Ciclos Negativos

Cuando consideremos pesos negativos en las aristas, al momento de hallar la ruta más corta, es posible que se generen ciclos. Veamos el siguiente ejemplo:

cicloNegativo1

Tratemos de hallar la ruta más corta aplicando Dijkstra desde el vértice 1:

cicloNegativoDijkstra1

Partimos de vértice 1 con peso igual a 0 y actualizamos peso de vértice 2:

cicloNegativoDijkstra2

Ahora actualizamos peso de vértice 3:

cicloNegativoDijkstra3

Según el algoritmo descrito en CAMINO MAS CORTO: ALGORITMO DE DIJKSTRA. El algoritmo terminaría, eso se da debido a que estábamos usando una arreglo de visitados de esta manera no caería en ciclos negativos; sin embargo la solución no sería correcta. Si omitimos el arreglo de visitados para hallar la ruta más corta, el algoritmo caería en un ciclo:

cicloNegativoDijkstra4

Como se puede ver en la figura, tenemos un ciclo negativo ya que siempre encontrará una mejor ruta entre los vértices 2 y 3.

Algoritmo de Bellman-Ford

Descripción

El algoritmo de Bellman-Ford 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. La diferencia de este algoritmo con los demás es que los pesos pueden tener valores negativos ya que Bellman-Ford me permite detectar la existencia de un ciclo negativo.

Como trabaja

El algoritmo parte de un vértice origen que será ingresado, a diferencia de Dijkstra que utiliza una técnica voraz para seleccionar vértices de menor peso y actualizar sus distancias mediante el paso de relajación, Bellman-Ford simplemente relaja todas las aristas y lo hace |V| – 1 veces, siendo |V| el número de vértices del grafo.

Para la detección de ciclos negativos realizamos el paso de relajación una vez más y si se obtuvieron mejores resultados es porque existe un ciclo negativo, para verificar porque tenemos un ciclo podemos seguir relajando las veces que queramos y seguiremos obteniendo mejores resultados.

Algoritmo en pseudocódigo

Considerar distancia[ i ] como la distancia más corta del vértice origen ingresado al vértice i y |V| el número de vértices del grafo.

método BellmanFord(Grafo,origen):
2      inicializamos las distancias con un valor grande
3      distancia[ origen ] = 0
4      para i = 1 hasta |V| - 1:
5          para cada arista E del Grafo:
6              sea ( u , v ) vértices que unen la arista E
7              sea w el peso entre vértices ( u , v )  
8              Relajacion( u , v , w )
9      para cada arista E del Grafo:
10         sea ( u , v ) vértices que unen la arista E
11         sea w el peso entre vértices ( u , v )  
12         si Relajacion( u , v , w )
13            Imprimir “Existe ciclo negativo”    
15            Terminar Algoritmo             

1  Relajacion( actual , adyacente , peso ):
2      si distancia[ actual ] + peso < distancia[ adyacente ]
3         distancia[ adyacente ] = distancia[ actual ] + peso

Ejemplo y Código 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

grafo

Algunas consideraciones para entender el código que se explicara junto con el funcionamiento del algoritmo.

#define MAX 105 //maximo numero de vértices
#define Node pair< int , int > //definimos el nodo como un par( first , second ) donde first es el vertice adyacente y second el peso de la arista
#define INF 1<<30 //definimos un valor grande que represente la distancia infinita inicial, basta conque sea superior al maximo valor del peso en alguna de las aristas

Inicializamos los valores de nuestros arreglos:

tablaBellman1

Dónde:

  • Vértices: ID de los vértices.
  • Distancia[ u ]: Distancia más corta desde vértice inicial a vértice con ID = u.
  • Previo[ u ]: Almacenara el ID del vértice anterior al vértice con ID = u, me servirá para impresión del camino más corto.

En cuanto al código los declaramos de la siguiente manera:

vector< Node > ady[ MAX ]; //lista de adyacencia
int distancia[ MAX ];      //distancia[ u ] distancia de vértice inicial a vértice con ID = u
int previo[ MAX ];         //para la impresion de caminos
int V;                     //numero de vertices

Y la función de inicialización será simplemente lo siguiente:

//función de inicialización
void init(){
    for( int i = 0 ; i <= V ; ++i ){
        distancia[ i ] = INF;  //inicializamos todas las distancias con valor infinito
        previo[ i ] = -1;      //inicializamos el previo del vértice i con -1
    }
}

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. grafoBellman1

Inicialmente la distancia de vértice 1 -> vértice 1 es 0 por estar en el mismo lugar.

    distancia[ inicial ] = 0;      //Este paso es importante, inicializamos la distancia del inicial como 0

Hasta este momento la tabla quedaría de la siguiente manera:

tablaBellman2

Ahora según Bellman-Ford debemos realizar el paso de relajación |V| – 1 = 5 – 1 = 4 veces para cada arista:

    for( int i = 1 ; i <= V - 1 ; ++i ){ //Iteramos |V| - 1 veces
        …
    }

 Primera Iteración

Empezamos con las aristas que parten del vértice 1:

grafoBellman2

Como podemos observar tenemos 2 aristas, la que une vértice 1 con vértice 2 y vértice 1 con vértice 4. Ello en código:

    for( int actual = 1 ; actual <= V ; ++actual ){  //Estos dos for = O(E)
       for( int j = 0 ; j < ady[ actual ].size() ; ++j ){ //reviso sus adyacentes del vertice actual
           int adyacente = ady[ actual ][ j ].v;    //id del vertice adyacente
           int peso = ady[ actual ][ j ].w;        //peso de la arista que une actual con adyacente ( actual , adyacente )
           …
       }
    }

Las aristas de acuerdo al código serian de la forma e = (actual , adyacente , peso) donde actual es el vértice de donde partimos (en este caso sería 1) adyacente son los vértices que unen la arista e  (en este caso serían los vértices 2 y 4) y peso son los pesos de cada arista (en este caso tendríamos 7 y 2).

Evaluamos primero para vértice 2:

grafoBellman3

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 < ∞

El paso de relajación es posible realizarlo entonces actualizamos la distancia en el vértice 2 quedando:

tablaBellman3grafoBellman4

El paso de relajación se daría en la siguiente parte:

    for( int actual = 1 ; actual <= V ; ++actual ){  //Estos dos for = O(E)
       for( int j = 0 ; j < ady[ actual ].size() ; ++j ){ //reviso sus adyacentes del vertice actual
           int adyacente = ady[ actual ][ j ].v;    //id del vertice adyacente
           int peso = ady[ actual ][ j ].w;        //peso de la arista que une actual con adyacente ( actual , adyacente )
           //Realizamos paso de relajacion para la arista actual
           relajacion( actual , adyacente , peso );
       }
    }

Donde la función de relajación seria

//Paso de relajacion
void relajacion( int actual , int adyacente , int peso ){
    //Si la distancia del origen al vertice actual + peso de su arista es menor a la distancia del origen al vertice adyacente
    if( distancia[ actual ] + peso < distancia[ adyacente ] ){
        distancia[ adyacente ] = distancia[ actual ] + peso;  //relajamos el vertice actualizando la distancia
        previo[ adyacente ] = actual;                         //a su vez actualizamos el vertice previo
        Q.push( Node( adyacente , distancia[ adyacente ] ) ); //agregamos adyacente a la cola de prioridad
    }
}

Ahora evaluamos al siguiente adyacente que es el vértice 4:

grafoBellman5

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 < ∞

El paso de relajación es posible realizarlo entonces actualizamos la distancia en el vértice 4 quedando:

tablaBellman4grafoBellman6

Hemos terminado las aristas que parten del vértice 1, continuamos con las aristas que parten del vértice 2:

grafoBellman7

Comenzamos por el vértice 3 y realizamos paso de relajación:

distancia[ 2 ] + 1 < distancia[ 3 ]    ->        7 + 1 < ∞         ->         8 < ∞

En esta oportunidad hemos encontrado una ruta más corta partiendo desde el vértice inicial al vértice 3, actualizamos la distancia en el vértice 3 y actualizamos el vértice previo al actual quedando:

grafoBellman8tablaBellman5

Ahora continuamos con la arista que une al vértice 2 con el vértice 4:

grafoBellman9

En este caso vemos que no se lleva acabo el paso de relajación:

distancia[ 2 ] + 2 < distancia[ 4 ]    ->        7 + 2 < 2         ->         9 < 2

Por lo tanto no actualizamos valores en la tabla. Ahora el siguiente vértice a evaluar es el vértice 3 que posee una sola arista:

grafoBellman10jpg

Como el peso de su vértice adyacente es infinito actualizamos la distancia:

grafoBellman11tablaBellman6

Ahora el siguiente vértice a evaluar es el vértice 4 que posee cuatro aristas:

grafoBellman12

Realizamos paso de relajación para cada vértice adyacente:

Con vértice 2:  distancia[ 4 ] + 3 < distancia[ 2 ]    ->     2 + 3 < 7        ->       5 < 7

Con vértice 3:  distancia[ 4 ] + 8 < distancia[ 3 ]    ->     2 + 8 < 8       ->       10 < 8

Con vértice 5:  distancia[ 4 ] + 5 < distancia[ 5 ]    ->      2 + 5 < 13     ->       7 < 13

Actualizamos distancias para los vértices 2 y 5:

grafoBellman13tablaBellman7

Ahora continuamos con vértice 5:

grafoBellman14

En este caso no actualizamos las distancias. Hemos terminado la primera iteración, continuemos:

Segunda Iteración:

Luego de la segunda iteración obtendremos lo siguiente:

grafoBellman15tablaBellman8

En esta iteración solamente se realizó el paso de relajación en la arista que une vértices 2 y 3. Para el grafo dado en la segunda iteración ya habremos obtenido la ruta más corta partiendo del vértice 1 a todos los demás vértices. Sin embargo no siempre obtendremos el óptimo en la 2da iteración, todo dependerá del grafo ingresado.

Impresión del Camino Más Corto

La impresión del camino más corto dado un vértice destino es de la misma forma como se explicó en el tutorial del Algoritmo de Dijkstra.

Detección de Ciclo Negativo

Para la detección de ciclo negativo tomaremos como ejemplo el grafo siguiente:

cicloNegativo1

Asumimos que el vértice inicial es el vértice 1, tendremos que realizar 2 iteraciones.

Primera Iteración

Empezamos por el vértice 1:

cicloNegativo2

Continuamos con el vértice 2:

cicloNegativo3

Continuamos con el vértice 3:

cicloNegativo4

Segunda Iteración

En esta última iteración se relajan vértices 2 y 3:

cicloNegativo5

Hemos terminado el número de iteraciones que teníamos que realizar. Para verificar la existencia de un ciclo negativo, según el algoritmo de Bellman-Ford, realizamos el paso de relajación sobre todas las aristas una vez más:

cicloNegativo6

Como se pudo realizar el paso de relajación entonces existe un ciclo negativo:

//Comprobamos si hay ciclo negativo en el grafo ingresado
    for( int actual = 1 ; actual <= V ; ++actual ){  //Estos dos for = O(E)
        for( int j = 0 ; j < ady[ actual ].size() ; ++j ){ //reviso sus adyacentes del vertice actual
            int adyacente = ady[ actual ][ j ].v;    //id del vertice adyacente
            int peso = ady[ actual ][ j ].w;       //peso de la arista que une actual con adyacente ( origen , destino )
            //Si aun es posible relajar la arista actual entonces tenemos ciclo negativo
            if( relajacion( actual , adyacente , peso ) ){
                puts("Existe Ciclo Negativo");
                return;
            }
        }
    }

Problemas de diferentes Jueces

UVA

117The Postal Worker Rings Once

558 – Wormholes

10557 – XYZZY

11280 – Flying to Fredericton

11721 – Instant View of Big Bang

LightOJ

1074 – Extended Traffic

1108 – Instant View of Big Bang

1221 – Travel Company

Códigos:

Implementación del algoritmo en C++: Algoritmo de Bellman-Ford

Por Jhosimar George Arias Figueroa

ÁRBOL DE EXPANSIÓN MÍNIMA: ALGORITMO DE KRUSKAL

Antes de explicar directamente el algoritmo de Kruskal, comenzaré dando conceptos sobre que es un árbol de expansión mínima para entender mejor el problema.

Árbol de Expansión

Dado un grafo conexo, no dirigido G. Un árbol de expansión es un árbol compuesto por todos los vértices y algunas (posiblemente todas) de las aristas de G. Al ser creado un árbol no existirán ciclos, además debe existir una ruta entre cada par de vértices.

Un grafo puede tener muchos arboles de expansión, veamos un ejemplo con  el siguiente grafo:

En la imagen anterior se puede observar que el grafo dado posee 3 arboles de expansión, dichos arboles cumplen con las propiedades antes mencionadas como son unir todos los vértices usando algunas aristas.

Árbol de Expansión Mínima

Dado un grafo conexo, no dirigido y con pesos en las aristas, un árbol de expansión mínima es un árbol compuesto por todos los vértices y cuya suma de sus aristas es la de menor peso. Al ejemplo anterior le agregamos pesos a sus aristas y obtenemos los arboles de expansiones siguientes:

De la imagen anterior el árbol de expansión mínima seria el primer árbol de expansión cuyo peso total es 6.

El problema de hallar el Árbol de Expansión Mínima (MST) puede ser resuelto con varios algoritmos, los mas conocidos con Prim y Kruskal ambos usan técnicas voraces (greedy).

Algoritmo de Kruskal

Para poder comprender el algoritmo de kruskal será necesario revisar primer el tutorial de Union-Find.

Como trabaja:

Primeramente ordenaremos las aristas del grafo por su peso de menor a mayor. Mediante la técnica greedy Kruskal intentara unir cada arista siempre y cuando no se forme un ciclo, ello se realizará mediante Union-Find. Como hemos ordenado las aristas por peso comenzaremos con la arista de menor peso, si los vértices que contienen dicha arista no están en la misma componente conexa  entonces los unimos para formar una sola componente mediante Union(x , y), para revisar si están o no en la misma componente conexa usamos la función SameComponent(x , y) al hacer esto estamos evitando que se creen ciclos y que la arista que une dos vértices siempre sea la mínima posible.

Algoritmo en Pseudocódigo

método Kruskal(Grafo):
2      inicializamos MST como vacío
3      inicializamos estructura unión-find
4      ordenamos las aristas del grafo por peso de menor a mayor.
5      para cada arista e que une los vértices u y v
6          si u y v no están en la misma componente
7             agregamos la arista e al MST     
8             realizamos la unión de las componentes de u y v

Ejemplo y código paso a paso

Tengamos el siguiente grafo no dirigido:

Como podemos ver en la imagen anterior la definición de nuestro grafo en código sería:

struct Edge{
    int origen;     //Vértice origen
    int destino;    //Vértice destino
    int peso;       //Peso entre el vértice origen y destino
    Edge(){}
    …
}arista[ MAX ];      //Arreglo de aristas para el uso en kruskal

Primeramente usaremos el método MakeSet de unión-find para inicializar cada componente, obteniendo las siguientes componentes conexas iniciales:

Ahora el siguiente paso es ordenar las aristas del grafo en orden ascendente:

Para el ordenamiento podemos usar las librerías predefinidas de Java y C++ como estamos ordenando estructuras necesitamos un comparador, en este caso estamos ordenando por peso por lo tanto dentro de la estructura antes definida agregamos:

struct Edge{
    …
    //Comparador por peso, me servira al momento de ordenar lo realizara en orden ascendente
    //Cambiar signo a > para obtener el arbol de expansion maxima
    bool operator<( const Edge &e ) const {
        return peso < e.peso;
    }
}arista[ MAX ];      //Arreglo de aristas para el uso en kruskal

Ordenamos el arreglo de aristas mediante lo siguiente:

    std::sort( arista , arista + E );    //Ordenamos las aristas por su comparador

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):

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 MST así que unimos los vértices por el método de Union( 8 , 7 ).

Continuamos con la siguiente arista:

Observamos la tabla de Union-Find y vemos que Find(3) != Find(9). Entonces es posible realizar la unión de ambas componentes:

Continuamos con la siguiente arista:

En la imagen podemos observar que ambos vértices no están en la misma componente, por tanto realizamos la Union( 6 , 7 ):

Continuamos con la siguiente arista, los vértices 1 y 2 no están en la misma componente conexa:

Realizamos la Union(1,2):

Continuamos con la siguiente arista:

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.

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.

Continuamos con la siguiente arista:

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:

Continuamos con la siguiente arista:

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:

Los vértices 1 y 8 están diferentes componentes. Realizamos la Union(1,8) en el grafo:

Continuamos con la siguiente arista:

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:

Los vértices 4 y 7 no están en la misma componente conexa, realizamos Union(4,5) en el grafo:

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.

En código simplemente es iterar sobre el arreglo de aristas ingresado y ordenado obteniendo sus respectivos datos. Para verificar si están o no en la misma componente usamos el método sameComponent explicado en el tutorial de Union-Find:

    for( int i = 0 ; i < E ; ++i ){     //Recorremos las aristas ya ordenadas por peso
        origen = arista[ i ].origen;    //Vértice origen de la arista actual
        destino = arista[ i ].destino;  //Vértice destino de la arista actual
        peso = arista[ i ].peso;        //Peso de la arista actual
        //Verificamos si estan o no en la misma componente conexa
        if( !sameComponent( origen , destino ) ){  //Evito ciclos
            total += peso;              //Incremento el peso total del MST
            MST[ numAristas++ ] = arista[ i ];  //Agrego al MST la arista actual
            Union( origen , destino );  //Union de ambas componentes en una sola
        }
    }

Verificación de 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. Veamos otro ejemplo teniendo como grafo ingresado lo siguiente:

Como podemos observar el grafo ingresado posee 2 componentes conexas, al aplicar kruskal obtendremos los siguientes MST:

En la imagen podemos observar el MST luego de aplicar kruskal, sin embargo no es un MST válido porque no tiene 1 componente conexa que posea todos los vértices, comprobemos:

  • Número de Aristas = 7
  • Número de Vértices = 9

No cumple lo dicho inicialmente 9 – 1 != 7 por lo tanto tenemos un MST invalido. En código basta con un if:

    //Si el MST encontrado no posee todos los vértices mostramos mensaje de error
    //Para saber si contiene o no todos los vértices basta con que el numero
    //de aristas sea igual al numero de vertices - 1
    if( V - 1 != numAristas ){
        puts("No existe MST valido para el grafo ingresado, el grafo debe ser conexo.");
        return;
    }

Problemas de diferentes Jueces

UVA

908 – Re-connecting Computer Sites

1208 – Oreon

10034 – Freckles

10462 – Is There A Second Way Left?

10600 – ACM contest and Blackout

10842 – Traffic Flow

11228 – Transportation System

11631 – Dark roads

11710 – Expensive subway

11733 – Airports

11747 – Heavy Cycle Edges

11857 – Driving Range

COJ

1016 – Freckles

1690 – Bad Cowtractors

TOPCODER

SRM 356 DIV2-1000 – RoadReconstruction

SRM 492 DIV2 – 1000 – TimeTravellingSalesman

HDU

1102 – Constructing Roads

POJ

2377 – Bad Cowtractors

2421 – Constructing Roads

TJU

2531 – Oreon

Códigos:

Implementación del algoritmo en C++: Algoritmo de Kruskal

Implementación del algoritmo en JAVA: Algoritmo de Kruskal

Por Jhosimar George Arias Figueroa

DISJOINT-SET: 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 me servirán para la implementación del algoritmo de Kruskal o problemas que involucran particionamiento como encontrar las componentes conexas en un grafo.

Implementación

Explicaré dos formas de implementar Union-Find, la forma básica y sus mejoras. Al final encontrarán los códigos en C++ y JAVA:

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:

#define MAX 10005
int parent[ MAX ];   //Este arreglo contiene el padre del i-esimo nodo

Método MakeSet

Para este tipo de implementación agregaremos un método que me inicializará los conjuntos, el cual llamaremos MakeSet:

//Método de inicialización
void MakeSet( int n ){
    for( int i = 0 ; i < n ; ++i ){
        padre[ i ] = i;      //Inicialmente el padre de cada vértice es el mismo vértice
    }
}

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.

Método Find – Find( x )

Como se explicó al inicio 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 ala que pertenece el vértice 3:

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:

El vértice actual ahora es el vértice 1 y hacemos lo mismo que antes, padre[ 1 ] = 0.

Ahora estamos en vértice 0, como el padre[ 0 ] = 0 entonces estamos en la raíz y la retornamos.

Veamos otro ejemplo, en este caso deseo saber la raíz para el vértice 6:

El vértice actual es 6 vemos su padre[ 6 ] = 4 y continuamos:

El vértice actual es 4, padre[ 4 ] = 5, todavía posee un padre por lo tanto continuamos:

El vértice actual es 5 en este caso padre[ 5 ] = 5 hemos llegado a la raíz y la retornamos.

Por la parte de código la implementación se realizara de manera recursiva, teniendo como caso base:

    if( x == padre[ x ] ){          //Si estoy en la raiz
        return x;                   //Retorno la raiz
    }

Si no estoy en la raíz continúo subiendo hasta encontrar la raíz y retornarla:

    else return Find( padre[ x ] ); //De otro modo busco el padre del nodo actual, hasta llegar a la raiz.

El código completo:

//Método para encontrar la raiz del vértice actual X
int Find( int x ){
    if( x == padre[ x ] ){          //Si estoy en la raiz
        return x;                   //Retorno la raiz
    }
    else return Find( padre[ x ] ); //De otro modo busco el padre del vértice actual, hasta llegar a la raiz.
}

Del ejemplo anterior podemos agregar un método que me permita saber si dos vértices están o no en la misma componente conexa, veamos:

En este caso no están en la misma componente conexa. Para saber si están en la misma componente conexa pues es simplemente ver si poseen la misma raíz, por lo tanto en código tendríamos:

//Método que me determina si 2 vértices estan o no en la misma componente conexa
bool sameComponent( int x , int y ){
    if( Find( x ) == Find( y ) ) return true;   //si poseen la misma raíz
    return false;
}

Método Union – Union( x , y )

Como se explicó al inicio este método me permite unir 2 componentes conexas, ello se realiza por lo siguiente:

  1. Obtenemos la raíz del vértice x.
  2. Obtenemos la raíz del vértice y.
  3. Actualizamos el padre de alguna de las raíces, asignándole como nuevo padre la otra raíz.

Por ejemplo:

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:

Al igual que el caso anterior el nuevo padre del vértice 7 es el vértice 0.

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.

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.

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.

En código tendríamos:

//Método para unir 2 componentes conexas
void Union( int x , int y ){
    int xRoot = Find( x );    //Obtengo la raiz de la componente del vértice X
    int yRoot = Find( y );    //Obtengo la raiz de la componente del vértice Y
    padre[ xRoot ] = yRoot;   //Mezclo ambos arboles o conjuntos, actualizando su padre de alguno de ellos como la raiz de otro
}

Como pudimos observar cada vez que hagamos unión entre componentes con mayor numero de nodos el árbol tiende a ser un árbol desbalanceado.

Mejoras

Implementación de Find por Compresión de Caminos

La idea de esta mejora es que cada nodo que visitemos en el camino al nodo raíz puede ser conectado directamente hacia la raíz, es decir al terminar de usar el método Find todos los nodos que visite tendrán como padre la raíz directamente. Veamos la mejora en el primer ejemplo del método Find antes visto:

Al aplicar Find( 3 ) estamos en vértice 0, como el padre[ 0 ] = 0 entonces estamos en la raíz y la retornamos.

Compresión de Caminos: Al momento de retornar la raíz en la recursión actualizamos el padre de cada vértice visitado como la raíz encontrada.

Veamos el otro ejemplo, donde realizamos Find(6):

Realizamos la compresión de caminos, obteniendo:

Veamos ahora de la siguiente imagen realizo Find(3):

Aplicamos compresión de caminos obteniendo:

Como hemos podido observar esta mejora me servirá a futuro ya que si deseo saber ahora el Find( 3 ) no es necesario recorrer varias veces el padre del vértice 3 puesto que por la compresión de caminos el vértice 3 esta conectado directamente a la raíz.

Para la implementación basta con una pequeña modificación en el método Find y es la de modificar lo siguiente:

    //else return Find( padre[ x ] ); //De otro modo busco el padre del vértice actual, hasta llegar a la raiz.
    else return padre[ x ] = Find( padre[ x ] ); //Compresion de caminos

Lo que hacemos es cambiar el puntero actual al padre de un nodo en el recorrido, apuntando a la raíz directamente. Con ello mejoramos la eficiencia por el hecho de que en futuras llamadas de alguno de los nodos vistos ya no tendremos que realizar todo el recorrido hacia la raíz simplemente revisara el padre actual del nodo que es la raíz.

Todo el método:

//Método para encontrar la raiz del vértice actual X
int Find( int x ){
    if( x == padre[ x ] ){          //Si estoy en la raiz
        return x;                   //Retorno la raiz
    }
    //else return Find( padre[ x ] ); //De otro modo busco el padre del vértice actual, hasta llegar a la raiz.
    else return padre[ x ] = Find( padre[ x ] ); //Compresion de caminos
}

Implementación de Unión por Rango

La idea de esta mejora básicamente lo que hará será unir el árbol de menor rango a la raíz del árbol con el mayor rango, los rangos los almacenamos en un arreglo y sufrirán modificación al momento de la unión. Los pasos para la implementación son los siguientes:

  1. Obtenemos la raíz del vértice x.
  2. Obtenemos la raíz del vértice y.
  3. Si el rango de X es mayor que el rango de Y entonces.
  • Actualizamos el padre de la raíz de Y asignándole como nuevo padre la raíz de X.

     4. De otro modo:

  • Actualizamos el padre de la raíz de X asignándole como nuevo padre la raíz de Y.
  • Si los rangos de ambas raíces son iguales incremento el rango de la nueva raíz en este caso incremento el rango de la raíz del vértice Y.

En resumen cada vez que hagamos unión entre dos componentes, la componente de mayor altura( rango ) siempre predominara sobre la de menor altura( rango ). Veamos la inicialización:

Código:

//Método de inicialización
void MakeSet( int n ){
    for( int i = 0 ; i < n ; ++i ){
        padre[ i ] = i;      //Inicialmente el padre de cada vértice es el mismo vértice
        rango[ i ] = 0;      //Altura o rango de cada vértice es 0
    }
}

Veamoslo ahora con ejemplo antes visto en el método Union:

La imagen anterior muestra el caso de rangos iguales, por tanto aumentamos el rango.

En este caso tenemos rangos diferentes, además no cumple con el paso 3 porque el rango del vértice 7 es 0 y no es mayor que el rango del vértice 0 que es 1, al no tener rangos iguales los rangos quedan como estaban.

Este caso es similar al primero, por tanto el rango de la raíz de la componente a la que pertenece el vértice Y se incrementa.

Caso similar a los anteriores con rangos iguales por parte de las raíces.

En la imagen anterior se hizo Union( 6 , 4 ) -> Union( 8 , 4 ) -> en ese orden, las actualizaciones las vemos en la tabla de la imagen.

Hasta el momento no hemos notado diferencia alguna entre la Unión normal con la Unión por Rangos, haremos ahora Union(3, 6) por ambos métodos:

1. Unión Normal

La altura del nuevo árbol formado es de 3. Ahora veamos la diferencia con la unión por rangos.

2. Unión por Rango

La altura del nuevo árbol es 2, este método mantiene el árbol tan balanceado como sea posible, para mayor número de vértices se verá la diferencia en cuanto a la eficiencia. Asimismo podemos decir que el rango del vértice raíz de una componente conexa es la altura de dicha componente.

El código es el siguiente:

//Método para unir 2 componentes conexas usando sus alturas (rangos)
void UnionbyRank( int x , int y ){
    int xRoot = Find( x );    //Obtengo la raiz de la componente del vértice X
    int yRoot = Find( y );    //Obtengo la raiz de la componente del vértice Y
    if( rango[ xRoot ] > rango[ yRoot ] ){ //en este caso la altura de la componente del vértice X es
                                           //mayor que la altura de la componente del vértice Y.
        padre[ yRoot ] = xRoot;            //el padre de ambas componentes será el de mayor altura
    }
    else{                    //en este caso la altura de la componente del vértice Y es mayor o igual que la de X
        padre[ xRoot ] = yRoot;            //el padre de ambas componentes será el de mayor altura
        if( rango[ xRoot ] == rango[ yRoot ] ){ //si poseen la misma altura
            rango[ yRoot ]++;              //incremento el rango de la nueva raíz
        }
    }
}

Número de Componentes Conexas

Para saber el número de componentes conexas mediante unión-find, basta con contar los vértices que sean raíces de su componente conexa, por ejemplo:

De la imagen podemos hallar la cantidad de componentes conexas de dos formas:

  • Verificamos simplemente si padre[ x ] = x.

  • Verificamos si Find( x ) = x, al llamar a Find realizará la compresión de caminos.

En ambos casos será necesario recorrer el número de vértices y realizar la verificación, en este ejemplo la respuesta será 4 componentes conexas. Adicionalmente podemos almacenar la raíz de cada componente para usos futuros.

Código:

int root[ MAX ]; //tendra las raices de las componentes conexas luego de aplicar el método
int numComponentes; //variable para el numero total de componentes conexas
//Método para obtener el numero de componentes conexas luego de realizar las conexiones respectivas
int getNumberConnectedComponents( int n ){
    numComponentes = 0;
    for( int i = 0 ; i < n ; ++i ){
        if( padre[ i ] == i ){    //Si el padre del vértice i es el mismo vértice entonces es raíz
        //if( Find( i ) == i ){   //podemos usamos find para el mismo proposito y
                                  //para que se realice compresion de caminos
            root[ numComponentes++ ] = i;  //almaceno la raiz de cada nueva componente
           // numComponentes++;
        }
    }
    return numComponentes;
}

Cantidad de Vértices por Componente Conexa

Para saber la cantidad de Vértices que posee cada componente conexa basta con tener un contador en la raíz de su componente conexa, de tal manera que al recorrer cada vértice incrementamos el contador de la raíz de su componente conexa. Veamos el siguiente ejemplo:

Comencemos haciendo Find( x ) desde vértice 0 hasta vértice 8:

Incrementamos en un arreglo el número de vértices, ello lo realizamos solo sobre los vértices que son raíces:

    for( int i = 0 ; i < n ; ++i ){
        numVertices[ Find( i ) ]++;                    //incremento la raíz del vértice i
    }

Código:

int numVertices[ MAX ];   //almacenara la cantidad de vértices para la i-esima raiz.
//Método para obtener la raiz y el numero de vértices de cada componente conexa
//será necesario primero tener la cantidad de componentes conexas
//podemos llamar 1ero al metodo getNumberConnectedComponents o incluir porcion de su codigo en este
void getNumberNodes( int n ){
    memset( numVertices , 0 , sizeof( numVertices ) );    //inicializo mi contador de vértices
    for( int i = 0 ; i < n ; ++i ){
        numVertices[ Find( i ) ]++;                    //incremento la raíz del vértice i
    }
    for( int i = 0 ; i < numComponentes ; ++i ){
        printf("Componente %d: Raiz = %d , Nro nodos = %d.\n" , i + 1 , root[ i ] , numVertices[ root[ i ] ] );
    }
}

Problemas de diferentes Jueces

UVA

459 – Graph Connectivity

599 – The Forrest for the Trees

793 – Network Connections

10158 – War

10178 – Counting Faces

10685 – Nature

11503 – Virtual Friends

11987 – Almost Union-Find

TIMUS

1671 – Anansi’s Cobweb

TJU

3499 – Network

POJ

1703 – Find them, Catch them

2236 – Wireless Network

Códigos:

Implementación de la estructura en C++: Union-Find

Implementación de la estructura en JAVA: Union-Find

 Por Jhosimar George Arias Figueroa

SPOJ 3273 – Order statistic set (ORDERSET)

El enlace del problema es el siguiente: SPOJ3272 – ORDERSET

Enunciado:

El problema me da un numero determinado de operaciones que se deben realizar, cada linea consta inicialmente de los caracteres: I, D, K, C seguidos de un entero x. Donde:

  • I x = INSERT( S , X ) = Insertar el elemento X a S siempre y cuanto X no exista en S.
  • D x = DELETE( S , X ) = Eliminar el elemento X de S siempre y cuando X exista en S.
  • K x = KTH( S ) = Imprimir el K-esimo menor elemento de S, si no existe imprimir “invalid”.
  • C x = COUNT( S , X ) = Imprimir el numero de elementos de S menores a X.

Ejemplo Input dado en el problema

Input
8
I -1   Inserto en S elemento -1 -> S = { -1 }
I -1   Elemento -1 ya existe en S asi que no inserto nada
I 2    Inserto en S elemento  2 -> S = { -1 , 2 }
C 0    Imprimo Nro elementos menores a 0 -> { -1 } = 1
K 2    Imprimo 2do menor elemento de S -> S = { -1 , 2 } = 2
D -1   Elimino elemento -1 de S -> S = { 2 }
K 1    Imprimo 1er menor elemento de S -> S = { 2 } = 2
K 2    S posee 1 elemento, asi que imprimo invalid

Solución

Como podemos ver se necesita de una estructura dinamica que me permita hacer la inserción y borrado de elementos, el hecho de pedirme el k-esimo menor y el numero de elementos menores a X, me indica que al insertar o eliminar debo mantener mi estructura ordenada. Por lo tanto para resolver el problema podemos usar un TREAP u otra estructura como Splay Tree, AVL Tree, etc. Escogi treap por ser la codificacion mas sencilla, la implementación y tutorial de treap lo encuentran aqui. Simplemente es usar el codigo dado en el tutorial y agregarle los metodos de k-esimo menor elemento y contar el menor numero de elementos.

K-esimo menor elemento

Para el k-esimo menor elemento sera necesario agregarle un campo a la estructura ya que necesitare el tamaño de los subarboles en cada nodo para saber la posicion.

struct Node{
    int key , priority , size;
    Node* left , *right;
    Node( int k ): key( k ) , left( NULL ) , right( NULL ) , priority( rand() ) , size( 0 ){}
};

De esta manera cada vez que inserte o elimine un elemento actualizo el tamaño en cada nodo. Ello lo hallamos de la siguiente manera:

int sz( Node* root ){
    if( root == NULL ) return 0; return root -> size;
}

Node* upd( Node* root ){
    if( root != NULL ){
        root -> size = 1 + sz( root -> left ) + sz( root -> right );
    }
    return root;
}

En la siguiente imagen podemos ver un treap con el campo adicional de tamaño de subarboles:

De la imagen la raiz tendria que ser el 4to menor elemento, ello lo podemos obtener sumando 1 al tamaño del subarbol izquierdo.

int ans = 1 + sz( root -> left );  //para cada nodo su posicion sera 1 + el tamaño del subarbol izquierdo
if( ans == k ) return root;        //si es el nodo actual lo retorno

Si deseo el 5to menor elemento, parto de la raiz como se que la raiz es el cuarto elemento tengo que buscar en el subarbol derecho, ahora como se que los 1eros 4 elementos son menores que la raiz le resto al que estoy buscando esa cantidad obteniendo 5 – 4 = 1, entonces en el subarbol derecho tengo que buscar el 1er menor elemento.

if( ans < k ) return find_kth( root -> right , k - ans ); //si esta en el subarbol derecho, busco el (k-ans)menor elemento
return find_kth( root -> left , k );                      //si esta en el subarbol izquierdo, simplemente sigo buscando

El codigo completo de la funcion es el siguiente:

Node* find_kth( Node *root , int k ){
    if( sz( root ) < k ) return NULL; //si no poseo elementos en esa posicion retorno NULL
    int ans = 1 + sz( root -> left ); //para cada nodo su posicion sera 1 + el tamaño del subarbol izquierdo
    if( ans == k ) return root;       //si es el nodo actual lo retorno
    if( ans < k ) return find_kth( root -> right , k - ans ); //si esta en el subarbol derecho, busco el (k-ans)menor elemento
    return find_kth( root -> left , k ); //si esta en el subarbol izquierdo, simplemente sigo buscando
}

Una vez entendido como hallar el k-esimo menor elemento, la funcion de contar el menor numero de elementos será facil de programar, ello se dejara para que lo programen.

El main seria lo siguiente:

int main(){
    char c;
    int q , d;
    scanf("%d" , &q );
    Node* tree = NULL;
    while( q-- ){
        scanf(" %c %d" , &c , &d );
        if( c == 'I' ) tree = insert( tree , new Node( d ) );
        else if( c == 'D' ) tree= erase( tree , d );
        else if( c == 'K' ){
            Node* aux = find_kth( tree , d );
            if( aux != NULL )printf("%d\n" , aux -> key );
            else puts("invalid");
        }
        else printf("%d\n" , count( tree, d ) );
    }
    clear( tree );
    return 0;
}

CAMINO MAS CORTO: ALGORITMO DE DIJKSTRA

Para el problema de la ruta corta tenemos varios algoritmos, en esta oportunidad se explicará el algoritmo de dijkstra el cual usa una técnica voraz (greedy). Al final del articulo se encuentran adjuntas las implementaciones en C++ y JAVA.

Descripción

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 mis aristas son de valor 1, entonces bastará con usar el algoritmo de BFS.
  • Si los pesos de mis aristas son negativos no puedo usar el algoritmo de dijsktra, para pesos negativos tenemos otro algoritmo llamado Algoritmo de Bellmand-Ford.

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).

Dijkstra es muy similar a BFS, si recordamos BFS usaba una Cola para el recorrido para el caso de Dijkstra usaremos una Cola de Prioridad o Heap, este Heap debe tener la propiedad de Min-Heap es decir cada vez que extraiga un elemento del Heap me debe devolver el de menor valor, en nuestro caso dicho valor será el peso acumulado en los nodos.

Tanto java como C++ cuentan con una cola de prioridad ambos implementan un Binary Heap aunque con un Fibonacci Heap la complejidad de dijkstra se reduce haciéndolo mas eficiente, pero en un concurso mas vale usar la librería que intentar programar una nueva estructura como un Fibonacci Heap, claro que particularmente uno puede investigar y programarlo para saber como funciona internamente.

Algoritmo en pseudocódigo

Considerar distancia[ i ] como la distancia mas corta del vértice origen ingresado al vértice i.

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

Ejemplo y Código 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

Algunas consideraciones para entender el código que se explicara junto con el funcionamiento del algoritmo.

#define MAX 10005 //maximo numero de vértices
#define Node pair< int , int > //definimos el nodo como un par( first , second ) donde first es el vertice adyacente y second el peso de la arista
#define INF 1<<30 //definimos un valor grande que represente la distancia infinita inicial, basta conque sea superior al maximo valor del peso en alguna de las aristas

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.

En cuanto al código los declaramos de la siguiente manera:

vector< Node > ady[ MAX ]; //lista de adyacencia
int distancia[ MAX ];      //distancia[ u ] distancia de vértice inicial a vértice con ID = u
bool visitado[ MAX ];      //para vértices visitados
int previo[ MAX ];         //para la impresion de caminos
priority_queue< Node , vector<Node> , cmp > Q; //priority queue propia del c++, usamos el comparador definido para que el de menor valor este en el tope
int V;                     //numero de vertices

Y la función de inicialización será simplemente lo siguiente

//función de inicialización
void init(){
    for( int i = 0 ; i <= V ; ++i ){
        distancia[ i ] = INF;  //inicializamos todas las distancias con valor infinito
        visitado[ i ] = false; //inicializamos todos los vértices como no visitado
        previo[ i ] = -1;      //inicializamos el previo del vértice i con -1
    }
}

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.

    Q.push( Node( inicial , 0 ) ); //Insertamos el vértice inicial en la Cola de Prioridad
    distancia[ inicial ] = 0;      //Este paso es importante, inicializamos la distancia del inicial como 0

Extraemos el tope de la cola de prioridad

while( !Q.empty() ){                   //Mientras cola no este vacia
        actual = Q.top().first;            //Obtengo de la cola el nodo con menor peso, en un comienzo será el inicial
        Q.pop();                           //Sacamos el elemento de la cola

Si el tope ya fue visitado entonces no  tengo necesidad de evaluarlo, por ello continuaría extrayendo elementos dela cola:

        if( visitado[ actual ] ) continue; //Si el vértice actual ya fue visitado entonces sigo sacando elementos de la cola

En este caso al ser el tope el inicial no esta visitado por lo tanto marcamos como visitado.

        visitado[ actual ] = true;         //Marco como visitado el vértice actual

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.

        for( int i = 0 ; i < ady[ actual ].size() ; ++i ){ //reviso sus adyacentes del vertice actual
            adyacente = ady[ actual ][ i ].first;   //id del vertice adyacente
            peso = ady[ actual ][ i ].second;        //peso de la arista que une actual con adyacente ( actual , adyacente )
            if( !visitado[ adyacente ] ){        //si el vertice adyacente no fue visitado

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 < ∞

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:

El paso de relajación se daría en la siguiente parte:

        for( int i = 0 ; i < ady[ actual ].size() ; ++i ){ //reviso sus adyacentes del vertice actual
            adyacente = ady[ actual ][ i ].first;   //id del vertice adyacente
            peso = ady[ actual ][ i ].second;        //peso de la arista que une actual con adyacente ( actual , adyacente )
            if( !visitado[ adyacente ] ){        //si el vertice adyacente no fue visitado
                relajacion( actual , adyacente , peso ); //realizamos el paso de relajacion
            }
        }

Donde la función de relajación seria

//Paso de relajacion
void relajacion( int actual , int adyacente , int peso ){
    //Si la distancia del origen al vertice actual + peso de su arista es menor a la distancia del origen al vertice adyacente
    if( distancia[ actual ] + peso < distancia[ adyacente ] ){
        distancia[ adyacente ] = distancia[ actual ] + peso;  //relajamos el vertice actualizando la distancia
        previo[ adyacente ] = actual;                         //a su vez actualizamos el vertice previo
        Q.push( Node( adyacente , distancia[ adyacente ] ) ); //agregamos adyacente a la cola de prioridad
    }
}

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 < ∞

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:

Revisamos sus adyacentes no visitados que serian vértices 2, 3 y 5.

Empecemos por el 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

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:

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:

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.

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

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:

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

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:

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.

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 ]).

Shortest Path Tree

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.

 

Impresión del 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 ]. De manera similar a lo que se explico en el algoritmo BFS, en este caso se realizara de manera recursiva:

//Impresion del camino mas corto desde el vertice inicial y final ingresados
void print( int destino ){
    if( previo[ destino ] != -1 )    //si aun poseo un vertice previo
        print( previo[ destino ] );  //recursivamente sigo explorando
    printf("%d " , destino );        //terminada la recursion imprimo los vertices recorridos
}

Veamos gráficamente el funcionamiento, desde el grafo comenzamos en 3

El previo de 3 es el vértice 2, por lo tanto ahora evaluó 2:

Ahora el previo de 2 es el vértice 4:

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

Problemas de diferentes Jueces

UVA

341 – Non-Stop Travel

423 – MPI Maelstrom

10278 – Fire Station

10801 – Lift Hopping

12144 – Almost Shortest Path

TJU

1325 – Fire Station

SPOJ

15 – The Shortest Path (SHPATH)

50 – Invitation Cards (INCARDS)

440 – The Turtle´s Shortest Path (TSHPATH)

3405 – Almost Shortest Path (SAMER08A)

POJ

1511 – Invitation Cards

HDU

1535 – Invitation Cards

ICPC

4210 – Almost Shortest Path

COJ

1659 – Checking an Alibi

Códigos:

Implementación del algoritmo en C++: Algoritmo de Dijkstra

Implementación del algoritmo en JAVA: Algoritmo de Dijkstra

Por Jhosimar George Arias Figueroa

ALGORITMO DE BÚSQUEDA: DEPTH FIRST SEARCH (PARTE 1)

El algoritmo de búsqueda que se explicará a continuación es Depth First Search ( DFS ) se explicará el algoritmo de manera similar a como se hizo BFS, proponiendo problemas y otorgando códigos del algoritmo en si.

Descripción

El algoritmo DFS posee varias aplicaciones la mas importante es para problemas de conectividad,  si un grafo es conexo, detectar ciclos en un grafo,  numero de componentes conexas,  etc y es bastante útil en otro algoritmos como para hallar las componentes fuertemente conexas en un grafo ( Algoritmo de Kosaraju, Algoritmo de Tarjan), para hallar puntos de articulación o componentes biconexas ( puentes ),  para recorrido en un circuito o camino euleriano, topological sort, flood fill y otras aplicaciones.

Como trabaja

DFS va formando un árbol al igual que BFS pero lo hace a profundidad. Existen dos formas de hacer el recorrido una es usando una Pila y otra de manera recursiva:

Usando Stack

El concepto es el mismo que BFS solo que se cambia la Cola por una Pila, el proceso es como sigue: visitar el nodo inicial y ponerlo en la pila, ahora para ver los siguientes nodos a visitar sacamos el nodo tope de la pila y vemos sus adyacentes, los que no han sido visitados los insertamos en la pila. El proceso se repite hasta que la pila se encuentre vacía ( se han visitado todos los nodos ).

Algoritmo en pseudocodigo:

1  método DFS( origen):
2      creamos una pila S
3      agregamos origen a la pila S
4      marcamos origen como visitado
5      mientras S no este vacío:
6          sacamos un elemento de la pila S llamado v
7          para cada vertice w adyacente a v en el Grafo: 
8              si w no ah sido visitado:
9                 marcamos como visitado w
10                 insertamos w dentro de la pila S

Código en C++:  Algoritmo DFS usando Stack

Usando Recursión

Usar la recursión es mucho mas fácil y ademas muy útil, es la forma mas usada en la solución de problemas con este algoritmo.

Algoritmo en pseudocódigo:

1  método DFS( origen):
2      marcamos origen como visitado 
3          para cada vertice v adyacente a origen en el Grafo: 
4              si v no ah sido visitado:
5                 marcamos como visitado v
6                 llamamos recursivamente DFS( v )  

Tomemos como ejemplo el siguiente grafo no dirigido:

Al igual que con la pila requerimos un nodo inicial, de manera recursiva llamamos a los adyacentes del nodo inicial, de esta forma se puede ver si llamamos inicialmente a “1”:

Inicial “1”: marcamos “1” como visitado, sus adyacentes son “2”,  “3” y “5”.

  • Visitados : 1.
  • Adyacentes de 1: 2 , 3 , 5

En la llamada recursiva ira el primero insertado en la lista de adyacencia, en este caso “2”, marcamos como visitado. Ahora el inicial es “2”, sus adyacentes son “1” , “4” y “5”.

  • Visitados: 1 , 2
  • Adyacentes de 2: 1, 4 , 5

Evaluamos el 1ero de la lista que es “1” pero ya fue visitado por lo tanto sigo con el siguiente, en este caso “4” , marcamos como visitado. Ahora inicial es “4”, sus adyacentes son “2”.

  • Visitados: 1 , 2 , 4
  • Adyacentes de 4: 2

Tocaria el nodo 2 pero ya fue visitado termina la recursion por ese lado. El siguiente adyacente de “2” es “5”. Ahora inicial es “5”, marcamos como visitado, sus adyacentes son “1” y “2”.

  • Visitados: 1 , 2 , 4 , 5
  • Adyacentes de 5: 1 , 2

Igual que con nodo “4” sus adyacentes han sido visitados por lo tanto terminamos la recursion por el nodo “2”.

El nodo actual es “1”, sus adyacentes eran “2”, “5” y “3”, estabamos evaluando por “2” pero ya terminamos el siguiente es “5” el cual ya fue visitado, continuamos con “3” este no fue visitado, marcamos como visitado, vemos sus adyacentes “1”.

  • Visitados: 1 , 2 , 4 , 5 , 3
  • Adyacentes de 3: 1

Como nodo “1” ya fue visitado entonces termina la recursión y termina el recorrido DFS. Como se puede observar el orden en que fueron visitados los nodos es el recorrido DFS del grafo.

Posibles Paths en un grafo

Otra ayuda importantisima del algoritmo recursivo es que nos permite hallar todos los posibles paths( rutas) de un nodo inicial a otro final, ello lo conseguiremos usando backtracking dentro del algoritmo:

Algoritmo en pseudocódigo:

1  método DFS( origen,final):
2      marcamos origen como visitado 
3      recuperar el path si se llego a final
4          para cada vertice v adyacente a origen en el Grafo: 
5              si v no ah sido visitado:
6                 marcamos como visitado v
7                 llamamos recursivamente DFS( v )
8      marcamos origen como no visitado

Codigo C++:  Algoritmo DFS usando Recursion

Componentes Conexas

Algun problema puede ser que nos pida hallar la cantidad de componentes conexas, supongamos el siguiente grafo no dirigido:

La cantidad de componentes conexas es 2. El problema puede ser resuelto de la siguiente manera:

Evaluamos todos los vertices posibles y los tomamos como origen aquellos no visitados:

...
for( int i = 1 ; i <= V ; ++i ){    //recorremos todos los posibles vertices
    if( !visitado[ i ] ){          //si alguno no fue visitado tenemos una componente a partir de ese nodo
       dfs( i );                  //recorremos a partir de nodo i todo el grafo que se forma
       total++;                   //incrementamos cantidad de componentes
    }
}
...

Usamos el algoritmo estandar DFS para cada recorrido:

void dfs( int u ){
    visitado[ u ] = true;
    visitado_componente[ u ] = true;
    for( int v = 0 ; v < ady[ u ].size(); ++v ){
        if( !visitado[ ady[ u ][ v ] ] ){
            dfs( ady[ u ][ v ] );
        }
    }
}

Veamos gráficamente, el código anterior parte evaluando el vértice 1:

  • i = 1
  • Visitados: Ninguno

Como no fue visitado entonces hacemos recorrido DFS partiendo de ese vértice ( dfs( i = 1 ) ). Entonces veamos el recorrido:

  • Vértice Actual: 1
  • Vértices Adyacentes: 2
  • Vértices Visitados: 1

El siguiente paso es evaluar los adyacentes:

  • Vértice Actual: 2
  • Vértices Adyacentes: 3
  • Vértices Visitados: 1, 2

  • Vértice Actual: 3
  • Vértices Adyacentes: 2
  • Vértices Visitados: 1, 2, 3

Terminamos la función de DFS partiendo del vértice 1. Ahora volvemos al for inicial e incrementamos las componentes.

...
if( !visitado[ i ] ){
    dfs( i );
    total++; //incrementamos numero de componentes
}
...

Ahora tenemos i = 2 pero 2 ya fue visitado por lo que no entraría al if, igual para i=3 que ya fue visitado; sin embargo para i=4 este no fue visitado por lo tanto hacemos recorrido dfs partiendo del vértice 4:

  • i = 4
  • Visitados: 1, 2, 3

  • Vértice Actual: 4
  • Vértices Adyacentes: 5
  • Vértices Visitados: 1, 2, 3, 4

Como 5 no fue visitado es el siguiente a evaluar:

  • Vértice Actual: 5
  • Vértices Adyacentes: 4
  • Vértices Visitados: 1, 2, 3, 4, 5

Terminamos DFS partiendo del vértice 4, entonces volvemos al if e incrementamos el numero de componentes, de esta manera el resultado será de 2 componentes.

Codigo C++: DFS Ejemplo – Conectividad

Ejemplo Aplicativo:

Tengamos un juego de dominos donde si hago caer uno domino, todos los demas dominos que siguen a este caerán. Dado el numero de dominos “n”, el estado del juego en la forma “x y” ( si domino “x” cae entonces domino “y” tambien caerá) , la cantidad de consultas a realizar, cada consulta sera el numero del domino el cual yo impulsaré. El problema me pide hallar cuantos dominos caeran a partir del domino que yo impulsé.

Supongamos la entrada:

8 6 3  ( 8 dominos, 6 enlaces de dominos y 3 consultas  )

1 2

2 5

5 3

4 3

6 7

7 8

1

4

6

Solución

Declaremos nuestras variables globales:

vector<int> ady[ MAX ];                     //lista de adyacencia
int total;                                  //la cantidad total de dominos que caerán
bool visitado[ MAX ];                       //arreglo de domino caido

Modelemos el problema como un grado dirigido:

Ahora vemos cada consulta, la primera nos indica que impulsaré el domino numero 1, entonces al hacer ello los dominos que caerán serán 1 -> 2 -> 5 ->3, debo retornar 4 la cantidad de dominos caidos. Para la segunda consulta caéran solamente 4->3, y finalmente para 6 caerán 6->7->8

La solución lo relizaremos con un DFS como sigue:

void dfs( int u ){                          //domino origen
    total++;                                //aumento en mi respuesta la caida de un domino
    visitado[ u ] = true;                   //domino "u" cayo
    for( int v = 0 ; v < ady[ u ].size(); ++v ){ //verifico los demas posibles domino que caeran si impulso "u"
         if( !visitado[ ady[ u ][ v ] ] ){         //si el domino adyacente no cayó entonces es el siguiente a evaluar
             dfs( ady[ u ][ v ] );               //recursivamente veo que dominos caeran a partir del adyacente de "u"
         }
    }
}

Codigo C++: DFS Ejemplo – Domino

A continuación algunos problemas que pueden ser resueltos con este algoritmo:

JUEZ UVA:

459 – Graph Connectivity

Varios Problemas se encuentran en el UvaToolkit colocando en el buscador DFS

JUEZ PKU:

2245 – Lotto

TOPCODER:

SRM 371: DIV 2 – 1000  FloodRelief

SRM 407: DIV 2 – 500 CorporationSalary

SRM 435 : DIV 1 – 250 CellRemoval

Se irán agregando mas adelante mas problemas de otros jueces asi como más aplicaciones de DFS.

Resumen de códigos:

Código en C++:  Algoritmo DFS usando Stack

Código en C++:  Algoritmo DFS usando Recursion

Código en C++: DFS Ejemplo – Domino

Código en C++: DFS Ejemplo – Conectividad

Por: Jhosimar George Arias Figueroa

ÁRBOL DE BÚSQUEDA ALEATORIZADO – TREAP

Treap es una estructura muy usada por su eficiencia y facilidad de codificación. Un treap consiste en introducir un número aleatorio en cada nodo. El número aleatorio será la prioridad del nodo. Las claves y las prioridades deben ser diferentes y pertenecer a un universo totalmente ordenado. En el árbol, las claves están almacenadas según un árbol binario de búsqueda, y las prioridades según una cola de prioridad. Por esta razón a la estructura se la denomina treaps que es un acrónimo de trees y heaps.

Como se dijo anteriormente un treap es la unión de arboles binarios con heaps, por tanto tienen que cumplir con las propiedades de ambos es decir:

Propiedad de Árbol Binario

Dada un nodo raíz X:

  • Los nodos ubicados a la izquierda del nodo X deben tener una clave menor que X
  • Los nodos ubicados a la derecha del nodo X deben tener una clave mayor que X.

Clave( hijo izquierda) < Clave(actual) > Clave(hijo derecha)

Propiedad de Heap:

Si tengo un Min-Heap: El nodo con prioridad mínima debe estar en la raíz, con ello queremos decir:

Prioridad (hijo) >= Prioridad (padre)

Si tengo un Max-Heap: El nodo con prioridad máxima debe estar en la raíz, con ello queremos decir:

Prioridad (padre) >= Prioridad (hijo)

Por tanto para definir nuestra estructura quedaría con los siguientes campos:

struct Node{
    int key , priority;            //clave y prioridad de un nodo
    Node* left , *right;           //subarbol izquierdo y derecho
    Node( int k ): key( k ) , priority( rand() ), left( NULL ) , right( NULL ){}
};

La prioridad no se ingresa pues posee un valor aleatorio.

1. Operaciones:

1.1 Búsqueda

La búsqueda se realiza igual que en un árbol binario, partiendo de la raíz pregunto si esta a la izquierda o derecha.

Node* search( Node *root , int key ){
    if( root == NULL ) return NULL;
    if( key < root -> key ) return search( root -> left , key );
    if( key > root -> key ) return search( root -> right , key );
    return root;
}

Para mayor información sobre la búsqueda revisar BST( Arbol de Busqueda Binario)

1.2 Inserción

La inserción puede ser por medio de rotaciones al igual que un AVL o RojiNegro, pero con rotaciones simples no muy complejas. Adicionalmente el Treap posee la operación de separación de un árbol en 2 arboles izquierdo y derecho dado un elemento a insertar. Mostraré ambas implementaciones

1.2.1 Inserción por medio de Rotaciones

Antes de empezar a explicar este tipo de inserción es necesario entender las rotaciones que se realizaran, una vez entendidas se procederá a explicar la inserción con un ejemplo y código fuente.

1.2.1.1 Rotaciones: Las rotaciones que se realizaran serán, rotación al a derecha y rotación a la izquierda se explicara paso a paso como se realizan las rotaciones.

a. Rotación a la derecha

Tengamos la siguiente imagen, la izquierda será el árbol inicial y la derecha será el árbol luego de rotarlo:

Root es la raíz que se pasara como argumento y Pivot será la nueva raíz luego de rotar, este caso se puede dar si por ejemplo tenemos un max-Heap donde el Nodo Root posee una prioridad menor que el Nodo Pivot. Como es max-Heap el nodo raíz debe tener el mayor valor.

Node* rotRight( Node *root ){   //Raiz es el argumento, se retornara pivot como raiz luego de rotar
    Node* pivot = root -> left;     //Asigno a pivot el subarbol izquierdo de root
    …
}

Los pasos a seguir con los punteros serán los siguientes:

Esto en código es:

...
root -> left = pivot -> right; //Puntero izquierdo de root apunta a derecho de pivot.
...

Esto en código es:

...
pivot -> right = root; //Puntero derecho de pivot apunta a root.
...

Retorno pivot como nueva raíz, el código adjunto es el siguiente:

//Rotación a la Derecha
Node* rotRight( Node *root ){       //Raiz es el argumento, se retornara pivot como raiz luego de rotar
    Node* pivot = root -> left;     //Asigno a pivot el subarbol izquierdo de root
    root -> left = pivot -> right;  //Puntero izquierdo de root apunta a derecho de pivot.
    pivot -> right = root;          //Puntero derecho de pivot apunta a root.
    return pivot;
}

b. Rotación a la Izquierda

Tengamos la siguiente imagen, la izquierda será el árbol inicial y la derecha será el árbol, luego de rotarlo

La rotación a la izquierda es similar a la rotación a la derecha, los pasos serian los siguientes:

...
root -> right = pivot -> left; //Puntero derecho de root apunta a derecho de pivot.
...

...
pivot -> left = root; //Puntero izquierdo de pivot apunta a root.
...

//Rotación a la Izquierda
Node* rotLeft( Node *root ){        //Raiz es el argumento, se retornara pivot como raiz luego de rotar
    Node* pivot = root -> right;    //Asigno a pivot el subarbol derecho de root
    root -> right = pivot -> left;  //Puntero derecho de root apunta a derecho de pivot.
    pivot -> left = root;           //Puntero izquierdo de pivot apunta a root.
    return pivot;
}

Estas son las rotaciones necesarias para el Treap, ahora si se procederá a explicar la inserción en el Treap.

1.2.1.2 Inserción

Tengamos el siguiente árbol:

La parte superior me indica la clave y la que esta entre paréntesis me indica la prioridad generada, en este caso trabajaremos con propiedades de Max-Heap.

Ahora queremos ingresar el nodo con clave = 9 y prioridad = 51. Entonces seguimos los siguientes pasos:

  1. Buscamos el nodo como en un BST por su clave.
  2. Una vez encontrado la ubicación del nodo.
  3. Si cumple con las propiedades de Heap entonces termina.
  4. Sino por medio de rotaciones voy ubicando el nodo a ingresar hasta que cumpla con las propiedades de heap.

La declaración de la función y el paso 1 para inserción sería:

Node* insert( Node *root , Node *novo ){ //Ingreso árbol actual y el nuevo nodo a insertar
    if( root == NULL ) return novo;            //Encontré posición para nodo
    if( root -> key < novo -> key ){              //Buscamos por la derecha
        root -> right = insert( root -> right , novo );
        …
    }
    else{				        //Buscamos por la izquierda
        root -> left = insert( root -> left , novo );
        …
    }
    …
}

La 1era imagen me muestra el paso 1. Ubicamos el nodo por la clave siguiendo una búsqueda binaria sobre la clave.

Como tenemos Prioridad (hijo = 59) >= Prioridad (padre = 9) no cumple con propiedades de max-Heap, por tanto realizamos una rotación a la izquierda. Ello se muestra en la 2da  imagen.

Como aun no se cumple propiedades del heap se sigue realizando rotaciones, en la 2da imagen se realiza una rotación a la derecha dando como resultado la 3ra imagen.

De esa manera seguimos rotando como se muestra en las siguientes imágenes:

Como podemos observar en estas últimas imágenes se realizan las últimas rotaciones, en la 2da imagen se realiza una rotación a la izquierda y el nodo ingresado quedaría ubicado en la raíz:

Ahora si cumple con las propiedades del heap y de un árbol binario. De esa forma se realiza una inserción mediante rotaciones.

El código de inserción final con las rotaciones sería de la siguiente manera:

//Inserción: Recibo un arbol y el nodo a insertar
Node* insert( Node *root , Node *novo ){       //Ingreso árbol actual y el nuevo nodo a insertar
    if( root == NULL ) return novo;            //Encontre posición para nodo
    if( root -> key < novo -> key ){           //Buscamos por la derecha
        root -> right = insert( root -> right , novo );
        if( root -> right -> priority > root -> priority ) root = rotLeft( root ); //rotacion izquierda
    }
    else{				                       //Buscamos por la izquierda
        root -> left = insert( root -> left , novo );
        if( root -> left -> priority > root -> priority ) root = rotRight( root ); //rotacion derecha
    }
    return root;
}

1.2.2 Inserción por medio de Separación de un árbol

Tengamos con el mismo ejemplo

La parte superior me indica la clave y la que esta entre paréntesis me indica la prioridad generada, en este caso trabajaremos con propiedades de Max-Heap.

Ahora queremos ingresar el nodo con clave = 9 y prioridad = 51. Entonces seguimos los siguientes pasos:

  1. Buscamos al igual que el anterior como un BST por clave.
  2. En cada paso de búsqueda si prioridad (nuevo) <= prioridad (actual) sigo buscando.
  3. Sino en la posición actual separo en 2 arboles.
  4. Inserto el elemento asignando los punteros respectivos.

Del nuevo nodo tengo una prioridad de 51 la cual es mayor al de la raíz que es 39, como estamos con un max-heap este valor tendría que ser la nueva raiz, entonces no puedo seguir realizando búsqueda por clave, por ello hago partición del árbol para insertar el nuevo nodo. Esta parte de partición la realizaremos como en un BST normal sin considerar la prioridad.

La porción de código de inserción sería de la siguiente manera:

//Inserción: Recibo un arbol y el nodo a insertar
Node* insert( Node *root , Node *novo ){
    if( root == NULL ) return novo;
    if( root -> priority < novo -> priority ){ //si no cumple propiedad de heap en la ubicacion actual
          split( root , novo -> key , novo -> left , novo -> right );  //insertamos nodo mediante split
          return novo; //retorno nuevo nodo con sus respectivos subárboles izquierdo y derecho
    }
   //Búsqueda del elemento por la clave.
    if( root -> key < novo -> key ) root -> right = insert( root -> right , novo );
    else root -> left = insert( root -> left , novo );
    return root;
}

1.2.2.1 Split( Separación en 2 arboles)

La función de separación de un árbol lo llamaremos Split, y funciona de la siguiente manera. Supongamos que tenemos el siguiente árbol binario:

Entonces insertamos el nodo con clave 26. Al insertar 26 todos los nodos mayores a 26 tienen que estar a la derecha y los menores a la izquierda.

Veamos los pasos con la imagen siguiente:

A medida que vamos avanzando en la búsqueda de la posición del nodo, vamos partiendo el árbol. Al llegar a la ubicación como se ve en la última imagen, a la izquierda de 28, L y R se forman con los retornos de las llamadas recursivas, teniendo lo siguiente:

El Árbol R se forma por los subárboles R’.

De la misma forma el árbol L se forma con los subárboles L’.

Al final el árbol R y L serán hijo derecho e izquierdo del nuevo nodo insertado respectivamente, quedando lo siguiente:

De esta forma se da la inserción por medio de la separación de arboles. La implementación requiere conocimiento de manejo de punteros.

//Split: Ingresa la raíz del árbol, la clave del nodo a insertar y los subárboles izquierdo y derecho
void split( Node* root , int key , Node *&L , Node*&R ){
    if( root == NULL ){ L = R = NULL; return; }
    else if( root -> key < key ){ split( root ->right , key , root -> right , R ); L = root;}
    else{ split( root -> left , key , L , root -> left ); R = root; }
}

1.3 Eliminación

La eliminación es similar a la inserción también se puede dar de 2 formas, la primera con rotaciones y la segunda por medio de la unión de arboles.

1.3.1 Eliminación mediante rotaciones

La eliminación mediante rotaciones es lo inverso a la inserción. Tengamos el árbol:

Ahora queremos eliminar el nodo con clave = 9 y prioridad = 51. Entonces seguimos los siguientes pasos:

  1. Buscamos el nodo como en un BST por su clave.
  2. Una vez encontrado el nodo.
  3. Mediante rotaciones lo hago descender hasta que se convierta en una hoja, en las rotaciones se considera la prioridad mas no la clave.
  4. Una vez que el nodo a eliminar sea una hoja lo elimino.
//Declaracion del método, recibo un arbol y la clave del nodo a eliminar
Node* erase( Node* root , int key ){
    if( root == NULL ){ return root; }
    //Realizo la busqueda por clave
    if( root -> key < key ) root -> right = erase( root -> right , key );
    else if( root -> key > key ) root -> left = erase( root -> left , key );
    else{
           …
    }
    return root;
}

Del ejemplo el paso 1 me indica que el nodo a eliminar es la raíz, ahora para saber que rotación debo hacer tengo que tener en cuenta el tipo de heap que estoy usando, como en nuestro caso es un max-Heap, tengo que ver la prioridad  máxima entre el hijo izquierdo y el hijo derecho.

Node* erase( Node* root , int key ){
    if( root == NULL ){ return root; }
    if( root -> key < key ) root -> right = erase( root -> right , key );
    else if( root -> key > key ) root -> left = erase( root -> left , key );
    else{
        //Si tengo ambos hijos puedo comparar prioridades
        if( root -> left != NULL ){
            if( root -> right != NULL ){
                //Elijo el de mayor prioridad
                if( root -> left -> priority < root -> right -> priority ){
                   …
                }else{
                    …
                }
            }
            else…
        }
        else …
    }
    return root;
}

Si el de máxima prioridad es el nodo derecho, este tendrá que ser la nueva raíz, por tanto se tendrá que realizar una rotación a la izquierda.

Si el de máxima prioridad es el nodo izquierdo, este tendrá que ser la nueva raíz, por tanto se tendrá que realizar una rotación a la derecha.

Veamos las imágenes para el mayor entendimiento:

Como muestra la imagen tengo que hacer descender el nodo con clave 9 a la izquierda y colocar el nodo 15 como nueva raíz, luego de la rotación izquierda tendríamos.

En código tendríamos lo siguiente:

...
if( root -> left -> priority < root -> right -> priority ){
    root = rotLeft( root );
    root -> left = erase( root -> left , key );
}else
...

Ahora el de mayor prioridad es el hijo izquierdo por tanto este tiene que ser la raíz, realizamos rotación a la derecha.

En código tendríamos lo siguiente:

...
else{
   root = rotRight( root ); //rotacion derecha
   root -> right = erase( root -> right , key );
}
...

Y así hasta que lleguemos a la hoja.

Como se pudo observar es el mismo procedimiento que inserción solo que de manera inversa, ahora que tenemos el nodo en la hoja basta con colocarlo como NULL para su eliminación.

Código de eliminación:

//Eliminacion: Recibo un arbol y la clave del nodo a eliminar
Node* erase( Node* root , int key ){
    if( root == NULL ){ return root; }
    //Realizo la busqueda por clave
    if( root -> key < key ) root -> right = erase( root -> right , key );
    else if( root -> key > key ) root -> left = erase( root -> left , key );
    else{
        //Si tengo ambos hijos puedo comparar prioridades
        if( root -> left != NULL ){
            if( root -> right != NULL ){
                //Elijo el de mayor prioridad
                if( root -> left -> priority < root -> right -> priority ){
                    root = rotLeft( root );  //rotacion izquierda
                    root -> left = erase( root -> left , key );
                }else{
                    root = rotRight( root ); //rotacion derecha
                    root -> right = erase( root -> right , key );
                }
            }
            else{ //Si tengo solo hijo izquierdo basta con cambiar con dicho nodo y eliminar el actual
                Node* aux = root -> left;  delete root; return aux;
            }
        }
        else{
            //Si tengo solo hijo derecho basta con cambiar con dicho nodo y eliminar el actual
            if( root -> right != NULL ){
                Node* aux = root -> right;  delete root; return aux;
            }
            else{ //Si mi nodo actual es hoja lo elimino
                delete root;  return NULL;
            }
        }
    }
    return root;
}

1.3.2 Eliminación mediante unión de arboles

Teniendo el árbol anterior como ejemplo:

Ahora queremos eliminar el nodo con clave = 9 y prioridad = 51. Entonces seguimos los siguientes pasos:

  1. Buscamos el nodo como en un BST por su clave.
  2. Una vez encontrado el nodo.
  3. Mezclo sus hijos izquierdo y derecho en un solo árbol T.
  4. Eliminamos el nodo encontrado y retornamos el nuevo árbol T
//Eliminacion: Recibo un arbol y la clave del nodo a eliminar
Node* erase( Node* root , int key ){
    if( root == NULL ) return NULL;
    if( root -> key == key ){ //si lo encontre, mezclo sus subarboles
        Node *aux = merge( root -> left , root -> right );
        delete root; //elimino nodo actual
        return aux; //retorno nuevo arbol
    }
   //Busqueda de nodo por clave
    if( root -> key < key ) root -> right = erase( root -> right , key );
    else root -> left = erase( root -> left , key );
    return root;
}

Entonces en el caso ejemplo el nodo es la raíz, tendremos 2 subárboles el izquierdo y derecho.

1.3.2.1 Merge( Mezcla de 2 Arboles)

Por medio de este método realizaremos la eliminación, explicare como mezclar 2 subárboles. Debemos tener en cuenta que todas las claves del árbol izquierdo deben ser menores que las claves del árbol derecho.

La declaración del método es:

Node* merge( Node* L , Node* R ){ //Recibo 2 arboles
    Node *root;			       //Este sera nuestro nuevo arbol
    …
    return root;
}

Si tengo alguno de los arboles como Nulo entonces el nuevo árbol será el no nulo, o nulo si ambos son nulos.

Node* merge( Node* L , Node* R ){
    Node *root;
    if( L == NULL || R == NULL ) root = ( L != NULL ?L : R );
    …
    return root;
}

Ahora si no son nulos debemos tener en cuenta que estamos trabajando con un max-heap por tanto al mezclar ambos arboles, la raíz debe tener el máximo valor, entonces tenemos que comparar la prioridad de ambos arboles y elegir el máximo.

La nueva raíz será ese nodo, como las claves del subárbol derecho de la nueva raíz tiene claves mayores entonces todo ese subárbol ya formara parte del nuevo árbol, teniendo:

Ahora tendremos que comparar el subárbol izquierdo de la nueva raíz con el árbol izquierdo inicial.

Eso seria en código como sigue:

Node* merge( Node* L , Node* R ){
    ...
    else if( L -> priority < R -> priority ){ R -> left = merge( L , R -> left ); root = R; }
    else
    ...
}

De la misma manera comparamos las claves y elegimos raíz con su subárbol respectivo. En este caso seria el árbol izquierdo con su subárbol izquierdo.

La porción de código de esta parte seria:

Node* merge( Node* L , Node* R ){
    ...
    if( L -> priority < R -> priority ){ ... }
    else{ L -> right = merge( L -> right , R ); root = L; }
    ...
}

Ahora comparamos los dos siguientes arboles:

En este caso tendríamos como el inicial la raíz seria el árbol derecho.

Al final solo nos quedara 2 nodos que tendremos que unir finalizada la recursión. Ahora debemos unir los arboles de las llamadas recursivas.

De esta manera se realiza la unión de 2 arboles, el código de todo lo visto para el método merge es como sigue:

//Merge: Recibo un Arbol Izquierdo y un Arbol Derecho
//Todas las claves de L deben ser menores que R
Node* merge( Node* L , Node* R ){
    Node *root;			          //Este sera nuestro nuevo arbol
    if( L == NULL || R == NULL ) root = ( L != NULL ? L : R );
    else if( L -> priority < R -> priority ){ R -> left = merge( L , R -> left ); root = R; }
    else{ L -> right = merge( L -> right , R ); root = L; }
    return root;
}

Códigos en C++:

Implementación de la Estructura con Rotaciones: Treap-Rotaciones
Implementación de la Estructura con Merge y Split: Treap-Merge-Split

Problemas en Jueces

La mayor parte de problemas en los cuales se usa esta estructura pediran obtener el valor del k-esimo menor elemento, el k-esimo menor elemento es el elemento en la posicion k luego de ingresar valores, teniendo estos valores ordenados. Por ejemplo si inserto -1 , 2 ,3. Y deseo saber el valor para k = 2 (comenzando los indices de k desde 1) me devolveria el valor de 2. La implementacion de la funcion que halle el k-esimo menor elemento se encuentra en el siguiente problema resuelto – ORDERSET.

Ahora si les dejo algunos problemas que se resuelven con Treap, cabe mencionar que dichos problemas tambien pueden ser resueltos por medio de otras estructuras como Splay Tree.

SPOJ: 3273 – Order Statistic Set (ORDERSET)Solucion

CodeforcesString Manipulation 1.0

LightOJ: 1087 – Diablo

TJU: 2159 – Black Box

POJ:

1442 – Black Box

2201 – Cartesian Tree

Por Jhosimar George Arias Figueroa