Recorrido en anchura y en profundidad de un grafo representado por una matriz

RECORRIDO EN ANCHURA

 

"En Ciencias de la Computación, 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."

(Para más información: http://es.wikipedia.org/wiki/B%C3%BAsqueda_en_anchura)

Un recorrido en anchura se refiere a recorrer un grafo por niveles, es decir, partiendo de un nodo inicial recorro todos sus vecinos, posteriormente los vecinos de los vecinos hasta que todos los nodos hayan sido visitados.

RECORRIDO EN 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."

(Para más información:http://es.wikipedia.org/wiki/B%C3%BAsqueda_en_profundidad)

Un recorrido en profundidad es que partiendo de un nodo inicial, visite toda una rama, luego otra hasta que todos los nodos hayan sido visitados.

A continuación un ejemplo sencillo de ambos recorridos realizado en Java:

import java.util.ArrayList;

/**
 * Clase Grafo
 * @author Juan Sebastian
 */
public class Grafo {

    public int[][] g = {{2, 1, 0, 1, 0},
                        {1, 2, 1, 0, 0},
                        {0, 1, 2, 1, 0},
                        {1, 0, 1, 2, 1},
                        {0, 0, 0, 1, 2}};
    private boolean[] visitiadoAnchura = new boolean[5];
    private boolean[] visitiadoProfunidad = new boolean[5];

    public Grafo() {
    }

    public int[][] getG() {
        return g;
    }

public ArrayList<Integer> recorridoAnchura(int nodoI) {

//Lista donde guardo los nodos recorridos

        ArrayList<Integer> recorridos = new ArrayList<Integer>();

//El nodo inicial ya está visitado

        visitiadoAnchura[nodoI] = true;

//Cola de visitas de los nodos adyacentes

        ArrayList<Integer> cola = new ArrayList<Integer>();

//Se lista el nodo como ya recorrido

        recorridos.add(nodoI);

//Se agrega el nodo a la cola de visitas

        cola.add(nodoI);

//Hasta que visite todos los nodos

        while (!cola.isEmpty()) {
            int j = cola.remove(0); //Se saca el primero nodo de la cola

//Se busca en la matriz que representa el grafo los nodos adyacentes

            for (int i = 0; i < g.length; i++) {

//Si es un nodo adyacente y no está visitado entonces

                if (g[j][i] == 1 && !visitiadoAnchura[i]) {
                    cola.add(i);//Se agrega a la cola de visitas
                    recorridos.add(i);//Se marca como recorrido
                    visitiadoAnchura[i] = true;//Se marca como visitado
                }
            }
        }
        return recorridos;//Devuelvo el recorrido del grafo en anchura
    }

    public ArrayList<Integer> recorridoProfunidad(int nodoI) {

//Lista donde guardo los nodos recorridos

        ArrayList<Integer> recorridos = new ArrayList<Integer>();
        visitiadoProfunidad[nodoI] = true;//El nodo inicial ya está visitado

//Cola de visitas de los nodos adyacentes

        ArrayList<Integer> cola = new ArrayList<Integer>();
        recorridos.add(nodoI);//Listo el nodo como ya recorrido
        cola.add(nodoI);//Se agrega el nodo a la cola de visitas
        while (!cola.isEmpty()) {//Hasta que visite todos los nodos
            int j = cola.remove(0);//Se saca el primer nodo de la cola

    //Se busca en la matriz que representa el grafo los nodos adyacentes

            for (int i = 0; i < g.length; i++) {

//Si es un nodo adyacente y no está visitado entonces

                if (g[j][i] == 1 && !visitiadoProfunidad[i]) {
                    cola.add(i);//Se agrega a la cola de visita

//Se recorren los hijos del nodo actual de visita y se agrega el recorrido al la lista

                    recorridos.addAll(recorridoProfunidad(i));
                    visitiadoProfunidad[i] = true;//Se marca como visitado
                }
            }
        }
        return recorridos;//Se devuelve el recorrido del grafo en profundidad
    }
}

Para porbar los métodos se ejecuta el siguiente código:

public class Prueba {

/**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        Grafo g=new Grafo();
        ArrayList<Integer> enAnchura=g.recorridoAnchura(0);//Nodo inicial 0
        System.out.println("Recorrido en anchura de un grafo representado como matriz: ");
        for(int i=0;i<enAnchura.size();i++){
            System.out.print(""+enAnchura.get(i)+" ");
        }
        ArrayList<Integer> enProfundidad=g.recorridoProfunidad(0);//Nodo inicial 0
        System.out.println("");
        System.out.println("Recorrido en profundidad de un grafo representado como matriz: ");
        for(int i=0;i<enProfundidad.size();i++){
            System.out.print(""+enProfundidad.get(i)+" ");
        }
    }

}

ÉXITOS