RECORRIDO EN ANCHURA
RECORRIDO 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.
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) {
int j = cola.remove(0); //Se saca el primero nodo de la cola
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) {
visitiadoProfunidad[nodoI] = true;//El nodo inicial ya está visitado
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
cola.add(i);//Se agrega a la cola de visita
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)+" ");
}
}
}