Búsquedas en Amplitud y Profundidad

Presentado a Julio Cesar Sierra

Por:

- Lorena Ramirez cod: 1010179099
- Carlos Caicedo: 1015412218
- Jorge Barrera: 1018413066

Universidad Central 2013

Runnable Jar

BÚSQUEDA PROFUNDIDAD

Una Búsqueda en profundidad (en inglés DFS o Depth First Search) es un algoritmo que permite recorrer todos los nodos de un grafo o árbol (teoría de grafos) de manera ordenada, pero no uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan más nodos que visitar en dicho camino, regresa (Backtracking), de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado.

    @Override
    public boolean Buscar() {

        NodoArbol nodo = new NodoArbol(' ');
        abierto.add(inicial);                                           //1.    Poner nodo inicial en una lista llamada ABIERTO

        while (!abierto.isEmpty() && nodo.getElemento() != caracter) {  //2.    Mientras ABIERTO tenga elementos y no se se haya llegado al estado meta

            nodo = abierto.remove(0);                                   //2.1   Quitar el primer elemento de ABIERTO

            if (!cerrado.contains(nodo)) {                              //2.2   Si el nodo no se encuentra en CERRADO

                ruta = ruta + " -> " + nodo.getElemento();
                cerrado.add(nodo);                                      //2.2.1 Ponerlo en una lista llamado CERRADO

                NodoArbol n = nodo;                                     //2.2.2 Llamar a este nodo N

                if (n.getHijos().size() > 0) {                          //2.2.4 Si hay sucesores y no son el estado meta

                    abierto.addAll(abierto.size(), n.getHijos());       //2.2.3 Expander el nodo n obteniendo todos sus sucesores                  
                    //      Almacenarlos al final de la lista ABIERTO
                }                                                       //2.2.5 Fin del condicional 2.2.4

            }                                                           //2.3   Fin del condicional 2.2

        }                                                               //3.    Fin del mientras

        return true;                                                    //4.    Si alguno de los sucesores es el estado meta, entonces el algoritmo concluye con EXITO; de otra forma con FRACASO
    }

BÚSQUEDA EN ANCHURA

Búsqueda en anchura (en inglés BFS - Breadth First Search) es un algoritmo para recorrer o buscar elementos en un grafo (usado frecuentemente sobre árboles). Intuitivamente, se comienza en la raíz (eligiendo algún nodo como elemento raíz en el caso de un grafo) y se exploran todos los vecinos de este nodo. A continuación para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el árbol.

    @Override
    public boolean Buscar() {

        NodoArbol nodo = new NodoArbol(' ');
        abierto.add(inicial);                                           //1.    Poner nodo inicial en una lista llamada ABIERTO

        while (!abierto.isEmpty() && nodo.getElemento() != caracter) {  //2.    Mientras ABIERTO tenga elementos y no se se haya llegado al estado meta

            nodo = abierto.remove(0);                                   //2.1   Quitar el primer elemento de ABIERTO

            if (!cerrado.contains(nodo)) {                              //2.2   Si el nodo no se encuentra en CERRADO

                ruta = ruta + " -> " + nodo.getElemento();
                cerrado.add(nodo);                                      //2.2.1 Ponerlo en una lista llamado CERRADO

                NodoArbol n = nodo;                                     //2.2.2 Llamar a este nodo N

                if (n.getHijos().size() > 0) {                          //2.2.4 Si hay sucesores y no son el estado meta

                    abierto.addAll(0, n.getHijos());                    //2.2.3 Expander el nodo n obteniendo todos sus sucesores                  
                    //      Almacenarlos al inicio de la lista ABIERTO
                }                                                       //2.2.5 Fin del condicional 2.2.4

            }                                                           //2.3   Fin del condicional 2.2

        }                                                               //3.    Fin del mientras

        return true;                                                    //4.    Si alguno de los sucesores es el estado meta, entonces el algoritmo concluye con EXITO; de otra forma con FRACASO
    }