Implementa búsquedas sobre Grafos utilizando DFS (Depth First Search) con Java


DFS (Depth First Search) es un algoritmo recursivo para la búsqueda sobre grafos, en este post se explicará como implementarlo con Java, se tomará como base el post Implementa un grafo de ciudades en Java.

Creando clases base para la construcción del grafo

El grafo que se creará contendrá información de ciudades y la distancia entre ellas, para hacerlo necesitaremos 3 clases Node, Edge y Graph. A continuación se mostrará cada una de ellas con su explicación:

Node.java


import java.util.ArrayList;
import java.util.List;

/**
 * @author raidentrance
 *
 */
public class Node {
	private String city;
	private List adjacents = new ArrayList();

	public Node(String city) {
		this.city = city;
	}

	public void addEdge(Edge edge) {
		adjacents.add(edge);
	}

	public List getAdjacents() {
		return adjacents;
	}

	public String getCity() {
		return city;
	}

	@Override
	public String toString() {
		return "Node [city=" + city + ", adjacents=" + adjacents + "]";
	}
}

La clase Node representará una ciudad en nuestro grafo, como se puede ver la ciudad contiene una lista de Edges los cuáles representarán las uniones entre los nodos, más adelante se darán más detalles sobre la clase Edge.
Edge.java


/**
 * @author raidentrance
 *
 */
public class Edge {
	private Node origin;
	private Node destination;
	private double distance;

	public Edge(Node origin, Node destination, double distance) {
		this.origin = origin;
		this.destination = destination;
		this.distance = distance;
	}

	public Node getOrigin() {
		return origin;
	}

	public void setOrigin(Node origin) {
		this.origin = origin;
	}

	public Node getDestination() {
		return destination;
	}

	public void setDestination(Node destination) {
		this.destination = destination;
	}

	public double getDistance() {
		return distance;
	}

	public void setDistance(double distance) {
		this.distance = distance;
	}

	@Override
	public String toString() {
		return "Edge [origin=" + origin.getCity() + ", destination=" + destination.getCity() + ", distance=" + distance
				+ "]";
	}
}

La clase Edge representa la unión entre dos nodos, como se puede ver contiene un nodo origen, uno destino y la distancia entre ambos.
Graph.java


import java.util.ArrayList;
import java.util.List;

/**
 * @author raidentrance
 *
 */
public class Graph {

	private List nodes = new ArrayList();

	public void addNode(Node node) {
		nodes.add(node);
	}

	public List getNodes() {
		return nodes;
	}

	@Override
	public String toString() {
		return "Graph [nodes=" + nodes + "]";
	}
}

La clase Graph representará el conjunto de las ciudades junto con sus uniones y direcciones.

Creando el grafo

Una vez que contamos con las clases necesarias para crear nuestro grafo el siguiente paso será llenarlo con la información de las ciudades que utilizaremos:

cities-graph

Analicemos el grafo:

  • Es posible ir del df a Toluca y a cuernavaca
  • Es posible ir de Toluca a Tlaxcala, Puebla, DF y Cuernavaca
  • Es posible ir de Cuernavaca al DF y a Puebla
  • Es posible ir de Puebla a Toluca y Tlaxcala
  • En este ejemplo solo podemos llegar a Tlaxcala pero no podemos ir a ningún otro lugar
  • En este ejemplo existe la ciudad de Cancún pero no hay una ruta hacia ella.

Veamos el código para construirlo:

MapBuilder.java


import com.raidentrance.graphs.Edge;
import com.raidentrance.graphs.Graph;
import com.raidentrance.graphs.Node;

/**
 * @author raidentrance
 *
 */
public class MapBuilder {
	private static final Graph instance = new Graph();

	private MapBuilder() {
	}

	public static Graph getGraph() {
		Node df = new Node("DF");
		Node toluca = new Node("Toluca");
		Node cuernavaca = new Node("Cuernavaca");
		Node puebla = new Node("Puebla");
		Node tlaxcala = new Node("Tlaxcala");
		Node cancun = new Node("Cancún");

		df.addEdge(new Edge(df, toluca, 100));
		df.addEdge(new Edge(df, cuernavaca, 90));

		toluca.addEdge(new Edge(toluca, puebla, 350));
		toluca.addEdge(new Edge(toluca, cuernavaca, 150));
		toluca.addEdge(new Edge(toluca, tlaxcala, 340));
		toluca.addEdge(new Edge(toluca, df, 100));

		cuernavaca.addEdge(new Edge(cuernavaca, df, 90));
		cuernavaca.addEdge(new Edge(cuernavaca, puebla, 100));

		puebla.addEdge(new Edge(puebla, tlaxcala, 20));
		puebla.addEdge(new Edge(puebla, toluca, 350));

		instance.addNode(df);
		instance.addNode(toluca);
		instance.addNode(cuernavaca);
		instance.addNode(puebla);
		instance.addNode(cancun);
		instance.addNode(tlaxcala);
		return instance;
	}
}

La clase MapBuilder tiene un método que devuelve un objeto de tipo Graph que representa el grafo definido en la imagen anterior.

Implementando DFS sobre el grafo

El siguiente paso será implementar el algoritmo DFS para búsqueda de ciudades en el grafo que definimos, para esto crearemos la clase GraphExampleApplication.


import java.util.HashSet;
import java.util.List;
import java.util.Optional;

import com.raidentrance.graphs.Edge;
import com.raidentrance.graphs.Graph;
import com.raidentrance.graphs.Node;
import com.raidentrance.map.MapBuilder;

/**
 * @author raidentrance
 *
 */
public class GraphExampleApplication {
	private Graph graph;

	public GraphExampleApplication() {
		graph = MapBuilder.getGraph();
	}

	private Optional getNode(String city) {
		List nodes = graph.getNodes();
		for (Node node : nodes) {
			if (node.getCity().equals(city)) {
				return Optional.of(node);
			}
		}
		return Optional.empty();
	}

	public boolean hasPathDfs(String source, String destination) {
		Optional start = getNode(source);
		Optional end = getNode(destination);
		if (start.isPresent() && end.isPresent()) {
			return hasPathDfs(start.get(), end.get(), new HashSet());
		} else {
			return false;
		}
	}

	private boolean hasPathDfs(Node source, Node destination, HashSet visited) {
		if (visited.contains(source.getCity())) {
			return false;
		}
		visited.add(source.getCity());
		if (source == destination) {
			return true;
		}
		for (Edge edge : source.getAdjacents()) {
			if (hasPathDfs(edge.getDestination(), destination, visited)) {
				return true;
			}
		}
		return false;
	}
}

Analicemos cada uno de los componentes:

  • El atributo graph contiene el grafo a utilizar.
  • El constructor inicializa la variable graph con el grafo definido en la imágen anterior.
  • El método OptionalgetNode(String city): Recibe como parámetro una ciudad y devuelve el Nodo en el grafo en caso de existir que contenga el nombre de la ciudad.
  • El método boolean hasPathDfs(String source, String destination): Recibe dos ciudades, el origen y el destino, con esto ejecuta el método de búsqueda DFS para determinar si existe la ruta en el grafo.
  • El método boolean hasPathDfs(Node source, Node destination, HashSet visited): Recibe un nodo origen, un nodo destino y un set con nodos visitados y sigue la siguiente lógica:
    • Si el nodo origen ya fue visitado devuelve false.
    • Agrega el nodo origen a los nodos visitados
    • Toma todos los nodos adyacentes del nodo origen y se ejecuta de forma recursiva.

Caso de ejemplo

Analicemos el método boolean hasPathDfs(Node source, Node destination, HashSet visited) en el caso yendo de Puebla a Cuernavaca.

Ejecución 1: Source =Puebla, Destination=Cuernavaca, Visited={}

  • No se ha visitado la ciudad origen, en este caso Puebla, así que continua.
  • Se agrega Puebla a la lista de ciudades visitadas
  • En este caso el origen y el destino son diferentes así que continua
  • Se iteran los nodos adyacentes para obtener el siguiente nodo origen, en este caso son (Tlaxcala y Toluca) y se ejecuta el método hasPathDfs de forma recursiva tomando el primer nodo como nuevo source veamos la siguiente ejecución.

cities-graph

Ejecución 2: Source =Tlaxcala, Destination=Cuernavaca, Visited={Puebla}

  • No se ha visitado la ciudad origen, en este caso Tlaxcala, así que continua.
  • Se agrega Tlaxcala a la lista de ciudades visitadas
  • En este caso el origen y el destino son diferentes así que continua
  • Se iteran los nodos adyacentes para obtener el siguiente nodo origen, en este caso Tlaxcala no tiene ninguno así que se devuelve false y se continua con la siguiente iteración.

cities-graph

Ejecución 3: Source =Toluca, Destination=Cuernavaca, Visited={Puebla,Tlaxcala}

  • No se ha visitado la ciudad origen, en este caso Toluca, así que continua.
  • Se agrega Toluca a la lista de ciudades visitadas
  • En este caso el origen y el destino son diferentes así que continua
  • Se iteran los nodos adyacentes para obtener el siguiente nodo origen, en este caso son (Puebla, Cuernavaca,Tlaxcala y DF) y se ejecuta el método hasPathDfs de forma recursiva tomando el primer nodo como nuevo source veamos la siguiente ejecución.

cities-graph

Ejecución 3: Source =Puebla, Destination=Cuernavaca, Visited={Puebla,Tlaxcala,Toluca}

  • La ciudad origen, en este caso Puebla, ya ha sido visitada, en este caso devuelve false y continua con la siguiente ciudad adyacente(Puebla, Cuernavaca,Tlaxcala y DF)

cities-graph

Ejecución 4: Source =Cuernavaca, Destination=Cuernavaca, Visited={Puebla,Tlaxcala,Toluca}

  • No se ha visitado la ciudad origen, en este caso Cuernavaca, así que continua.
  • Se agregaCuernavaca a la lista de ciudades visitadas
  • En este caso el origen y el destino son iguales así que devuelve verdadero, esto significa que si existe una ruta válida para ir desde Puebla hacia Toluca.

Probando los distintos escenarios

Para terminar agregaremos un main a nuestra aplicación, para probar todos los posibles escenarios.

	public static void main(String[] args) {

		System.out.println("\n\t Paths from DF \n");
		System.out.println(String.format("From DF to DF %s", new GraphExampleApplication().hasPathDfs("DF", "DF")));
		System.out.println(
				String.format("From DF to Toluca %s", new GraphExampleApplication().hasPathDfs("DF", "Toluca")));
		System.out.println(String.format("From DF to Cuernavaca %s",
				new GraphExampleApplication().hasPathDfs("DF", "Cuernavaca")));
		System.out.println(
				String.format("From DF to Puebla %s", new GraphExampleApplication().hasPathDfs("DF", "Puebla")));
		System.out.println(
				String.format("From DF to Tlaxcala %s", new GraphExampleApplication().hasPathDfs("DF", "Tlaxcala")));
		System.out.println(
				String.format("From DF to Cancún %s", new GraphExampleApplication().hasPathDfs("DF", "Cancún")));
		// Paths from Toluca

		System.out.println("\n\t Paths from Toluca \n");
		System.out.println(String.format("From Toluca to Toluca %s",
				new GraphExampleApplication().hasPathDfs("Toluca", "Toluca")));
		System.out.println(
				String.format("From Toluca to DF %s", new GraphExampleApplication().hasPathDfs("Toluca", "DF")));
		System.out.println(String.format("From Toluca to Cuernavaca %s",
				new GraphExampleApplication().hasPathDfs("Toluca", "Cuernavaca")));
		System.out.println(String.format("From Toluca to Puebla %s",
				new GraphExampleApplication().hasPathDfs("Toluca", "Puebla")));
		System.out.println(String.format("From Toluca to Tlaxcala %s",
				new GraphExampleApplication().hasPathDfs("Toluca", "Tlaxcala")));
		System.out.println(String.format("From Toluca to Cancún %s",
				new GraphExampleApplication().hasPathDfs("Toluca", "Cancún")));

		System.out.println("\n\t Paths from Cuernavaca \n");
		System.out.println(String.format("From Cuernavaca to Cuernavaca %s",
				new GraphExampleApplication().hasPathDfs("Cuernavaca", "Cuernavaca")));
		System.out.println(String.format("From Cuernavaca to DF %s",
				new GraphExampleApplication().hasPathDfs("Cuernavaca", "DF")));
		System.out.println(String.format("From Cuernavaca to Toluca %s",
				new GraphExampleApplication().hasPathDfs("Cuernavaca", "Toluca")));
		System.out.println(String.format("From Cuernavaca to Puebla %s",
				new GraphExampleApplication().hasPathDfs("Cuernavaca", "Puebla")));
		System.out.println(String.format("From Cuernavaca to Tlaxcala %s",
				new GraphExampleApplication().hasPathDfs("Cuernavaca", "Tlaxcala")));
		System.out.println(String.format("From Cuernavaca to Cancún %s",
				new GraphExampleApplication().hasPathDfs("Cuernavaca", "Cancún")));

		System.out.println("\n\t Paths from Puebla \n");
		System.out.println(String.format("From Puebla to Puebla %s",
				new GraphExampleApplication().hasPathDfs("Puebla", "Puebla")));
		System.out.println(String.format("From Puebla to Cuernavaca %s",
				new GraphExampleApplication().hasPathDfs("Puebla", "Cuernavaca")));
		System.out.println(
				String.format("From Puebla to DF %s", new GraphExampleApplication().hasPathDfs("Puebla", "DF")));
		System.out.println(String.format("From Puebla to Toluca %s",
				new GraphExampleApplication().hasPathDfs("Puebla", "Toluca")));
		System.out.println(String.format("From Puebla to Tlaxcala %s",
				new GraphExampleApplication().hasPathDfs("Puebla", "Tlaxcala")));
		System.out.println(String.format("From Puebla to Cancún %s",
				new GraphExampleApplication().hasPathDfs("Puebla", "Cancún")));

		System.out.println("\n\t Paths from Tlaxcala \n");
		System.out.println(String.format("From Tlaxcala to Tlaxcala %s",
				new GraphExampleApplication().hasPathDfs("Tlaxcala", "Tlaxcala")));
		System.out.println(String.format("From Tlaxcala to Puebla %s",
				new GraphExampleApplication().hasPathDfs("Tlaxcala", "Puebla")));
		System.out.println(String.format("From Tlaxcala to Cuernavaca %s",
				new GraphExampleApplication().hasPathDfs("Tlaxcala", "Cuernavaca")));
		System.out.println(
				String.format("From Tlaxcala to DF %s", new GraphExampleApplication().hasPathDfs("Tlaxcala", "DF")));
		System.out.println(String.format("From Tlaxcala to Toluca %s",
				new GraphExampleApplication().hasPathDfs("Tlaxcala", "Toluca")));
		System.out.println(String.format("From Tlaxcala to Cancún %s",
				new GraphExampleApplication().hasPathDfs("Tlaxcala", "Cancún")));

		System.out.println("\n\t Paths from Cancún \n");
		System.out.println(String.format("From Cancún to Cancún %s",
				new GraphExampleApplication().hasPathDfs("Cancún", "Cancún")));
		System.out.println(String.format("From Cancún to Tlaxcala %s",
				new GraphExampleApplication().hasPathDfs("Cancún", "Tlaxcala")));
		System.out.println(String.format("From Cancún to Puebla %s",
				new GraphExampleApplication().hasPathDfs("Cancún", "Puebla")));
		System.out.println(String.format("From Cancún to Cuernavaca %s",
				new GraphExampleApplication().hasPathDfs("Cancún", "Cuernavaca")));
		System.out.println(
				String.format("From Cancún to DF %s", new GraphExampleApplication().hasPathDfs("Cancún", "DF")));
		System.out.println(String.format("From Cancún to Toluca %s",
				new GraphExampleApplication().hasPathDfs("Cancún", "Toluca")));

	}

Salida:


	 Paths from DF 

From DF to DF true
From DF to Toluca true
From DF to Cuernavaca true
From DF to Puebla true
From DF to Tlaxcala true
From DF to Cancún false

	 Paths from Toluca 

From Toluca to Toluca true
From Toluca to DF true
From Toluca to Cuernavaca true
From Toluca to Puebla true
From Toluca to Tlaxcala true
From Toluca to Cancún false

	 Paths from Cuernavaca 

From Cuernavaca to Cuernavaca true
From Cuernavaca to DF true
From Cuernavaca to Toluca true
From Cuernavaca to Puebla true
From Cuernavaca to Tlaxcala true
From Cuernavaca to Cancún false

	 Paths from Puebla 

From Puebla to Puebla true
From Puebla to Cuernavaca true
From Puebla to DF true
From Puebla to Toluca true
From Puebla to Tlaxcala true
From Puebla to Cancún false

	 Paths from Tlaxcala 

From Tlaxcala to Tlaxcala true
From Tlaxcala to Puebla false
From Tlaxcala to Cuernavaca false
From Tlaxcala to DF false
From Tlaxcala to Toluca false
From Tlaxcala to Cancún false

	 Paths from Cancún 

From Cancún to Cancún true
From Cancún to Tlaxcala false
From Cancún to Puebla false
From Cancún to Cuernavaca false
From Cancún to DF false
From Cancún to Toluca false

De este modo se pueden realizar búsquedas sobre un grafo utilizando el algoritmo DFS.

Si te gusta el contenido y quieres enterarte cuando realicemos un post nuevo síguenos en nuestras redes sociales https://twitter.com/geeks_mx y https://www.facebook.com/geeksJavaMexico/.

Autor: Alejandro Agapito Bautista

Twitter: @raidentrance

Contacto:raidentrance@gmail.com

Anuncios

1 comentario »

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s