Cómo implementar el recorrido DFS y BFS en Java

Por ray padgett
Implementar los recorridos DFS y BFS es relativamente simple.
Stockbyte/Stockbyte/Getty Images

La primera búsqueda en profundidad (DFS) y la mejor primera búsqueda (BFS) son dos recorridos que se pueden ejecutar en estructuras de árbol de Java. Comienzan en un nodo especifico y se ramifican hasta que encuentran el objeto de la búsqueda. La única diferencia es la direccionalidad: DFS busca hacia abajo desde el nodo y BFS busca horizontalmente hacia los nodos vecinos. Implementar los recorridos DFS y BFS es relativamente simple ya que aunque el código es largo, sólo hay un par de lugares donde necesitas personalizarlo para tus datos.

Paso 1

Abre tu código Java.

Paso 2

Copia y pega el siguiente código donde desees ejecutar el recorrido: public void TRAV() { Stack s=new Stack(); s.push(this.rootNode); rootNode.PROP; printNode(rootNode); while(!s.isEmpty()) { Node n=(Node)s.peek(); Node child=getUnvisitedChildNode(n); if(child!=null) { child.visited=true; printNode(child); s.push(child); } else { s.pop(); } } clearNodes(); }

Paso 3

Reemplaza "TRAV", ya sea con "dfs" o "bfs".

Paso 4

Reemplaza "PROP" con tu búsqueda de propiedades. Esto puede ser cualquier condición de Java que use el código Java regular.

Paso 5

Ejecuta el código. Este llevará a cabo el recorrido DFS/BFS y mostrará los resultados en una nueva ventana cuando termine.