Búsqueda de profundidad y Anchura
1: Tener un nodo inicio.
2: Adjuntarlo a la pila.
3: Verificar si la pila esta vacia, mientras no este vacia...4: Tomo un nodo de la pila (en el caso de la pila el ultimo que se ingresó) y lo marco como visitado.
5: Proceso el nodo que tome del paso 4 (El proceso puede ser por ej: imprimirlo).
6: Adjunto a lapila los nodos adyacente del nodo tomado en el paso 4.
7: Regreso al paso 3, hasta que la pila este vacia.
Asi implemente el metodo.
Algorito de profundiad
public voidrecorrerProfundidadI(Nodo nodoInicio){
if(nodoInicio != null){
pila.addNodo(nodoInicio);
while(pila.size() > 0){
Nodo nodoVisitado = pila.getNodo();if(nodoVisitado.visitado == false){
nodoVisitado.visitado = true;
System.out.print(nodoVisitado.getDato()+",");llenarPilaNodosAdyacentes(nodoVisitado);
}
}
}
}
Para el caso del recorrido en anchura, es analogo, solo tienes que remplazar la pila por una cola (tener en cuenta queen la cola el primero en entrar es el primero en salir).
Tomemos el grafo del dibujo como ejemplo:
Lo contruimos de la siguiente forma:
----------------------------------------------
publicstatic void llenandoGrafo(){
grafo = new Grafo();
// creamos los nodos del grafo.
grafo.adjuntarNodo(new Nodo("A"));
grafo.adjuntarNodo(newNodo("B"));
grafo.adjuntarNodo(new Nodo("C"));
grafo.adjuntarNodo(new Nodo("D"));
grafo.adjuntarNodo(new Nodo("F"));
grafo.crearEnlaces("A","B");// de Ahacia B
grafo.crearEnlaces("B","A");// de B hacia A
/*
* Lo anterior lo hacemos por ser un grafo no dirigido...
* En caso de ser un grafo con peso esto no...
Regístrate para leer el documento completo.