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

Borrar elementos de un Arbol binario


En el post Árboles binarios en Java se habló sobre como crear un árbol binario en Java y se analizaron las siguientes operaciones:

  • Agregar un nuevo nodo
  • Buscar un nodo
  • Imprimir in order
  • Imprimir in pos order
  • Imprimir in pre order

En este post se explicará como implementar el borrado de un nodo en el árbol.

Posibles escenarios

Cuando queremos borrar un elemento de un árbol binario, nos daremos cuenta que hay 3 posibles escenarios:

  • El nodo no tiene nodos hijos
  • El nodo tiene 1 hijo
  • El nodo tiene 2 hijos

A continuación se presentará como borrar el nodo con Java para cada uno de ellos.

El nodo no tiene nodos hijos

Si el nodo que se desea borrar no tiene ningún nodo hijo, el borrado será muy simple ya que lo único que se debe hacer es asignar el valor de null a la referencia padre que apunta a el.

El borrado para este escenario tendrá una complejidad de  O(Log N) por la búsqueda + O(Log 1) del borrado lo cual da una complejidad total de O(Log N).

El nodo tiene un hijo

Si el nodo que se desea borrar tiene un nodo hijo el procedimiento será el siguiente:

  • Buscar el elemento que deseamos borrar
  • Apuntar el puntero padre que apunta a el a su nodo hijo

El borrado para este escenario tendrá una complejidad de O(Log N) por la búsqueda + O(1) de la actualización de referencias = O(Log N).

El nodo tiene 2 hijos

Este es el escenario más complejo y debemos seguir lo siguiente:

  1. Buscar el elemento
  2. Para el siguiente paso tenemos dos opciones
    • Buscar el elemento más grande en el sub árbol de la izquierda (Que será conocido como predecesor).
    • Buscar el elemento más pequeño en el sub árbol de la derecha (Que será conocido como sucesor)
  3. Intercambiar el predecesor o sucesor con el nodo que se desea borrar, antes de hacerlo se deben validar los siguientes dos escenarios
    1. Si el predecesor o sucesor no tienen nodos hijos: El elemento se intercambiará con el predecesor o sucesor y será borrado
    2. Si el predecesor o sucesor tiene un nodo hijo: El elemento se intercambiará con el predecesor o sucesor, será borrado y su hijo ahora será hijo del predecesor o sucesor.

El borrado para este escenario tendrá una complejidad de O(Log N).

Analizando el código

Una vez que entendemos lo que se debe realizar, el siguiente paso será programarlo y analizar paso a paso el código:

  • Programando la búsqueda del predecessor:
public Node findPredecessor() {
	if (this.getRight() == null) {
		return this;
	} else {
		return this.getRight().findPredecessor();
	}
}
  • Programando la búsqueda del sucessor:
public Node findSuccessor() {
	if (this.getLeft() == null) {
		return this;
	} else {
		return this.getLeft().findSuccessor();
	}
}
  • Programando el borrado:
public Node delete(Integer value) {
	Node response = this;
	if (value < this.value) { 		this.left = this.left.delete(value); 	} else if (value > this.value) {
		this.right = this.right.delete(value);
	} else {
		if (this.left != null && this.right != null) {
			Node temp = this;
			Node maxOfTheLeft = this.left.findPredecessor();
			this.value = maxOfTheLeft.getValue();
			temp.left=temp.left.delete(maxOfTheLeft.getValue());
		} else if (this.left != null) {
			response = this.left;
		} else if (this.right != null) {
			response = this.right;
		} else {
			response = null;
		}
	}
	return response;
}

Analizando método por método:

  • findPredecessor : Busca el nodo más grande de la rama

  • findSuccessor : Busca el nodo más pequeño de la rama
  • delete: Busca en el árbol y cuando encuentra el elemento intercambia el predecesor de la izquierda por el elemento a borrar

Todo el código

A continuación se muestra como se ve la clase Node completa:


import java.util.Optional;

public class Node {
	private Integer value;
	private Node left;
	private Node right;

	public Node(Integer value) {
		this.value = value;
	}

	public Integer getValue() {
		return value;
	}

	public void setValue(Integer value) {
		this.value = value;
	}

	public Node getLeft() {
		return left;
	}

	public void setLeft(Node left) {
		this.left = left;
	}

	public Node getRight() {
		return right;
	}

	public void setRight(Node right) {
		this.right = right;
	}

	public void add(Integer value) {
		if (value < this.value) {
			if (left != null) {
				left.add(value);
			} else {
				left = new Node(value);
			}
		} else {
			if (right != null) {
				right.add(value);
			} else {
				right = new Node(value);
			}
		}
	}

	public Optional<Node> find(Integer value) {
		if (value == this.value) {
			return Optional.of(this);
		} else if (value < this.value) {
			if (this.left != null) {
				return this.left.find(value);
			} else {
				return Optional.empty();
			}
		} else {
			if (this.right != null) {
				return this.right.find(value);
			} else {
				return Optional.empty();
			}
		}
	}

	public void printInOrder() {
		if (left != null) {
			left.printInOrder();
		}
		System.out.println(value);
		if (right != null) {
			right.printInOrder();
		}
	}

	public void printPreOrder() {
		System.out.println(value);
		if (left != null) {
			left.printPreOrder();
		}
		if (right != null) {
			right.printPreOrder();
		}
	}

	public void printPosOrder() {
		if (left != null) {
			left.printPreOrder();
		}
		if (right != null) {
			right.printPreOrder();
		}
		System.out.println(value);
	}

	public Node findPredecessor() {
		if (this.getRight() == null) {
			return this;
		} else {
			return this.getRight().findPredecessor();
		}
	}

	public Node findSuccessor() {
		if (this.getLeft() == null) {
			return this;
		} else {
			return this.getLeft().findSuccessor();
		}
	}

	public Node delete(Integer value) {
		Node response = this;
		if (value < this.value) { 			this.left = this.left.delete(value); 		} else if (value > this.value) {
			this.right = this.right.delete(value);
		} else {
			if (this.left != null && this.right != null) {
				Node temp = this;
				Node maxOfTheLeft = this.left.findPredecessor();
				this.value = maxOfTheLeft.getValue();
				temp.left = temp.left.delete(maxOfTheLeft.getValue());
			} else if (this.left != null) {
				response = this.left;
			} else if (this.right != null) {
				response = this.right;
			} else {
				response = null;
			}
		}
		return response;
	}

	@Override
	public String toString() {
		return "Node [value=" + value + ", left=" + left + ", right=" + right + "]";
	}

}

 Probando el código

El último paso es probar todo el código y ver que el borrado funciona, para esto ejecutaremos el siguiente código:

public class TreeTest {
	public static void main(String[] args) {
		Node root = new Node(32);
		root.add(10);
		root.add(55);
		root.add(1);
		root.add(19);
		root.add(16);
		root.add(23);
		root.add(79);
		System.out.println("Tree before deletion");
		root.printPreOrder();
		root.delete(55);
		root.delete(16);
		root.delete(32);
		System.out.println("Tree after deletion");
		root.printPreOrder();

	}
}<span 				data-mce-type="bookmark" 				id="mce_SELREST_start" 				data-mce-style="overflow:hidden;line-height:0" 				style="overflow:hidden;line-height:0" 			></span>

Como se puede ver es posible borrar nodos en los 3 escenarios mencionados anteriormente.

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

Implementa un grafo de ciudades en Java


Una de las estructuras de datos más complejas y más útiles son los grafos (Graphs), en este post se explicará paso a paso como implementar uno en Java. Para este ejemplo se creará uno sobre algunas de las ciudades que se encuentran en México.

Conceptos básicos

Antes de crear el grafo debemos entender algunos conceptos básicos:

  • Vértice (Vertex) : Es un punto donde varias líneas se unen
  • Arista (Edge) : Es un término matemático que representa una línea que conecta 2 vértices
  • Grafo (Graph) : Es el término que representa un conjunto de vértices y aristas.

Ejemplo práctico

En el ejemplo que se presentará se creará un Grafo de ciudades, cada nodo será una ciudad (DF, Toluca, Cuernavaca, Puebla y Tlaxcala) que se unirán con un conjunto de aristas con su distancia, la siguiente imagen es una representación gráfica:

graphs

Creando el modelo

Como siempre el primer paso será crear el modelo con las clases a utilizar, para esto crearemos 3 clases Node, Edge y Grap que serán mostradas a continuación:

Node.java


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

/**
 * @author raidentrance
 *
 */
public class Node {
	private String city;
	private List<Edge> edges;

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

	public String getCity() {
		return city;
	}

	public void setCity(String city) {
		this.city = city;
	}

	public List<Edge> getEdges() {
		return edges;
	}

	public void addEdge(Edge edge) {
		if (edges == null) {
			edges = new ArrayList<>();
		}
		edges.add(edge);
	}

	@Override
	public String toString() {
		return "\n \tNode [city=" + city + ", edges=" + edges + "]";
	}
}

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 "\n Edge [origin=" + origin.getCity() + ", destination=" + destination.getCity() + ", distance="
				+ distance + "]";
	}

}

Graph


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

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

	private List<Node> nodes;

	public void addNode(Node node) {
		if (nodes == null) {
			nodes = new ArrayList<>();
		}
		nodes.add(node);
	}

	public List<Node> getNodes() {
		return nodes;
	}

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

}

A continuación se presenta la explicación:

  • Un Graph contiene una lista de nodos
  • Cada nodo contiene el nombre de una ciudad y una lista de aristas
  • Cada arista contiene la unión de las ciudades así como la distancia entre ellas

Creando el grafo de ciudades

Una vez que se creó el modelo el siguiente paso será llenarlo con la información de las ciudades.


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

	public static Graph getCities() {
		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");

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

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

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

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

		Graph graph = new Graph();
		graph.addNode(df);
		graph.addNode(toluca);
		graph.addNode(cuernavaca);
		graph.addNode(puebla);
		return graph;
	}

	public static void main(String[] args) {
		Graph graph = getCities();
		System.out.println(graph);
	}
}

Salida:

Graph [nodes=[
 	Node [city=DF, edges=[
 Edge [origin=DF, destination=Toluca, distance=100.0],
 Edge [origin=DF, destination=Cuernavaca, distance=90.0]]],
 	Node [city=Toluca, edges=[
 Edge [origin=Toluca, destination=Cuernavaca, distance=150.0],
 Edge [origin=Toluca, destination=Puebla, distance=350.0],
 Edge [origin=Toluca, destination=Tlaxcala, distance=340.0]]],
 	Node [city=Cuernavaca, edges=[
 Edge [origin=Cuernavaca, destination=Puebla, distance=100.0]]],
 	Node [city=Puebla, edges=[
 Edge [origin=Puebla, destination=Tlaxcala, distance=20.0]]]]]

Si observamos la salida del programa podemos ver que cada ciudad cuenta con sus aristas que representan la unión de ambos puntos y cuenta con la distancia entre ellas como se mostró en la imagen.

Siguientes pasos

En próximos posts se explicará ejecutar algoritmos sobre este grafo, agregar dirección a las aristas y muchas más operaciones, 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

Listas doblemente ligadas en Java


En el post anterior Listas ligadas en Java paso a paso y en Español aprendimos como utilizar listas simplemente ligadas, en este explicaremos como crear listas doblemente ligadas en Java.

A diferencia de las listas simplemente ligadas las listas doblemente ligadas contienen una referencia al nodo siguiente y una al anterior, esto debe ser considerado al momento de agregar los valores al principio y al final de ella.

Creando la clase Nodo


public class Node {
	private Integer value;
	private Node nextElement;
	private Node previousElement;

	public Node(Integer value) {
		this.value = value;
	}

	public Integer getValue() {
		return value;
	}

	public void setValue(Integer value) {
		this.value = value;
	}

	public Node getNextElement() {
		return nextElement;
	}

	public void setNextElement(Node nextElement) {
		this.nextElement = nextElement;
	}

	public Node getPreviousElement() {
		return previousElement;
	}

	public void setPreviousElement(Node previousElement) {
		this.previousElement = previousElement;
	}

	@Override
	public String toString() {
		return "Node [value=" + value + ", nextElement=" + ((nextElement != null) ? nextElement.getValue()
				: null) + ", previousElement=" +( (previousElement != null) ? previousElement.getValue() : null) + "]";
	}

}

Como se puede observar la clase nodo contiene 3 atributos:

  • Integer value : Contiene el valor a almacenar en la lista

  • Node nextElement: Contiene una referencia al nodo siguiente
  • Node previousElement: Contiene una referencia al nodo anterior

Con estos atributos la lista doblemente ligada se verá como la siguiente imagen:

doublylinkedlist

Creando la lista doblemente ligada

Una vez que se ha creado el nodo, el siguiente paso es crear la lista doblemente ligada.


public class DoublyLinkedList {
	private Node tail;
	private Node head;

	public void addLast(Integer value) {
		Node node = new Node(value);
		if (tail == null && head == null) {
			tail = node;
			head = node;
		} else {
			tail.setNextElement(node);
			node.setPreviousElement(tail);
			tail = node;
		}
	}

	public void addFirst(Integer value) {
		Node node = new Node(value);
		if (tail == null && head == null) {
			tail = node;
			head = node;
		} else {
			node.setNextElement(head);
			head.setPreviousElement(node);
			head = node;
		}
	}

	public void print() {
		for (Node i = head; i != null; i = i.getNextElement()) {
			System.out.printf("\t %s ", i.toString());
		}
		System.out.println();
	}
}

El código anterior muestra como realizar las siguientes operaciones en una lista doblemente ligada:

  • void addLast(Integer value) : Agrega un nodo al final de la lista

  • void addFirst(Integer value) : Agrega un nodo al principio de la lista

  • void print() : Imprime los elementos en la lista

Es importante mencionar que cada elemento de la lista debe mantener una referencia tanto al nodo siguiente como al nodo anterior.

Probando la lista

El último paso será probar la lista doblemente ligada, veamos el código:

public class TestDoublyLinkedList {
	public static void main(String[] args) {
		DoublyLinkedList list = new DoublyLinkedList();
		list.addLast(10);
		list.addLast(11);
		list.addLast(12);
		list.addLast(13);
		list.addLast(14);
		list.addFirst(9);
		list.addFirst(8);
		list.print();
	}
}

Salida:

Node [value=8, nextElement=9, previousElement=null] 	 Node [value=9, nextElement=10, previousElement=8] 	 Node [value=10, nextElement=11, previousElement=9] 	 Node [value=11, nextElement=12, previousElement=10] 	 Node [value=12, nextElement=13, previousElement=11] 	 Node [value=13, nextElement=14, previousElement=12] 	 Node [value=14, nextElement=null, previousElement=13]

La salida muestra por cada nodo su valor, su nodo anterior y su nodo siguiente.

Si te gusta el contenido compártelo y no olvides seguirnos 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

Listas ligadas en Java


En este post explicaremos paso a paso como crear una lista ligada en Java, como sabemos existe un api llamado Collections api que se encuentra en el paquete java.util, nosotros no lo utilizaremos y crearemos una desde cero para entender como funciona.

Una lista ligada es un conjunto dinámico de elementos de cualquier tipo almacenados en memoria, estos pueden ser:

  • Des ordenadas
  • Ordenadas
  • Con elementos únicos
  • Con elementos duplicados
  • Simplemente ligadas
  • Doblemente ligadas

En este post explicaremos como crear una lista simplemente ligada.

Creando la clase Nodo

La clase nodo será la clase base y será utilizada para representar cada elemento en la lista.


/**

 * @author raidentrance

 *

 */

public class Node {

	private Integer value;

	private Node next;

	public Node(Integer value) {

		this.value = value;

	}

	public Integer getValue() {

		return value;

	}

	public void setValue(Integer value) {

		this.value = value;

	}

	public Node getNext() {

		return next;

	}

	public void setNext(Node next) {

		this.next = next;

	}

}

Como se puede observar cada elemento de la lista contendrá dos atributos:

  • Integer value : Almacena el valor contenido en el elemento
  • Node next : Almacena una referencia al nodo siguiente de la lista

Las listas se llaman ligadas porque cada elemento contiene una referencia al nodo siguiente como se muestra en la siguiente imagen :

linkedlist

Creando la lista ligada

Una vez que definimos la estructura que tendrá el nodo el siguiente paso será crear una clase que represente las acciones disponibles sobre esa lista, en este caso crearemos una clase llamada LinkedList.


import java.util.Optional;

/**

 * @author raidentrance

 *

 */

public class LinkedList {

	private Node head;

	public void append(Integer value) {

		if (head == null) {

			head = new Node(value);

			return;

		}

		Optional<Node> lastNode = getLastNode();

		Node node = lastNode.get();

		node.setNext(new Node(value));

	}

	public void print() {

		for (Node i = head; i != null; i = i.getNext()) {

			System.out.print(i.getValue() + "\t");

		}

		System.out.println();

	}

	public Optional<Node> getLastNode() {

		if (head != null) {

			Node current = head;

			while (current.getNext() != null) {

				current = current.getNext();

			}

			return Optional.of(current);

		} else {

			return Optional.empty();

		}

	}

	public void delete(Integer value) {

		System.out.printf("Deleting %d \n", value);

		if (head == null) {

			return;

		}

		if (head.getValue() == value) {

			head = head.getNext();

			return;

		}

		Node current = head;

		while (current != null && current.getNext() != null) {

			if (current.getNext().getValue() == value) {

				current.setNext(current.getNext().getNext());

			}

			current = current.getNext();

		}

	}

}

Como se puede observar, las acciones soportadas en esta clase son las siguientes:

  • void append(Integer value) : Agrega un valor al final de la lista

  • void print() : Imprime el contenido de la lista

  • Optional getLastNode() : Devuelve una referencia al nodo final de la lista en caso de existir

  • void delete(Integer value) : Borra el o los elementos que contengan el valor pasado como parámetro de la lista

Probando la lista

Una vez que determinamos los nodos y las disponibles en la lista el siguiente paso será probarla para esto crearemos la siguiente clase:


/**

 * @author raidentrance

 *

 */

public class TestLinkedList {

	public static void main(String[] args) {

		LinkedList list = new LinkedList();

		list.append(10);

		list.append(11);

		list.append(12);

		list.append(13);

		list.append(14);

		list.append(12);

		list.print();

		list.delete(14);

		list.print();

		list.delete(10);

		list.print();

		list.delete(12);

		list.print();

	}

}

Salida:


10	11	12	13	14	12

Deleting 14

10	11	12	13	12

Deleting 10

11	12	13	12

Deleting 12

11	13

En siguientes posts se explicará como utilizar una lista doblemente ligada así como otras estructuras de datos, Si te gusta el contenido compártelo y no olvides seguirnos 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

Árboles binarios en Java


Uno de los temas sobre desarrollo de software que todos los desarrolladores de software deberían conocer y que por lo mismo es cuestionado en una gran parte de las entrevistas es el manejo de arboles binarios, en este post entraremos en detalle en este tema y lo analizaremos paso a paso.

Introducción

En este ejemplo se mostrará como desarrollar un árbol binario balanceado en Java, esto significa que los datos serán ordenados en tiempo de inserción de acuerdo a lo siguiente:

  • Si el valor a insertar es menor al valor del nodo se insertará a la izquierda
  • Si el valor a insertar es mayor al valor del nodo se insertará a la derecha

La clase a desarrollar será de acuerdo al siguiente diagrama:

Tree node

Analizando la clase

El siguiente paso será analizar la clase a desarrollar, para esto expliquemos a detalle cada uno de los componentes:

  • Atributos
    • value: Cada nodo contendrá un valor almacenado
    • left : Cada nodo tendrá una rama izquierda
    • right : Cada nodo tendrá una rama derecha
  • Métodos
    • add : Permite agregar un nuevo valor al árbol binario
    • find : Permite buscar un valor en el árbol binario
    • printInOrder : Permite imprimir el árbol en modo In order
    • printPreOrder : Permite imprimir el árbol en modo Pre Order
    • printPosOrder : Permite imprimir el árbol en modo Pos Order

Creando el árbol

Para crear el árbol solo debemos crear una clase llamada Node (Nodo), veamos el código necesario para definir los atributos a utilizar:

public class Node {
	private Integer value;
	private Node left;
	private Node right;

	public Node(Integer value) {
		this.value = value;
	}
//... Getters y setters
}

Agregar un valor nuevo

Para agregar un valor nuevo al árbol la lógica será la siguiente:

  1. Si el valor a agregar es menor al del nodo actual se insertará del lado izquierdo
  2. Si el valor a agregar es mayor al del nodo actual se insertará del lado derecho

Recordemos que cada nodo puede tener solo 2 nodos hijos, por lo tanto si el nodo actual contiene un 10 y el valor a insertar es un 7 este se insertará del lado izquierdo, si ya hay un valor insertado del lado izquierdo se ejecutará la misma lógica con el valor insertado hasta llegar a un nodo izquierdo o derecho nulo, veamos el código:

public class Node {
...// El código anterior
public void add(Integer value) {
	if (value < this.value) {
		if (left != null) {
			left.add(value);
		} else {
			left = new Node(value);
		}
	} else {
		if (right != null) {
			right.add(value);
		} else {
			right = new Node(value);
		}
	}
}
}

Como se puede observar en el código se utiliza recursividad para agregar los nodos en caso de que ya existan en el árbol.

Buscar un valor

La lógica para buscar un valor en el árbol es muy similar que para insertarlo, en el código que se mostrará se utilizará la clase Optional agregada en Java 8, veamos el código:

import java.util.Optional;
public class Node {
...// El código anterior
public Optional<Node> find(Integer value) {
	if (value == this.value) {
		return Optional.of(this);
	} else if (value < this.value) {
		if (this.left != null) {
			return this.left.find(value);
		} else {
			return Optional.empty();
		}
	} else {
		if (this.right != null) {
			return this.right.find(value);
		} else {
			return Optional.empty();
		}
	}
}
}

Como se puede ver es necesario importar la clase Optional del paquete java.util.

Imprimir los valores del árbol binario

Para imprimir los valores es necesario iterar el árbol utilizando recursividad y existen 3 formas de hacerlo:

  1. In order: Imprime el valor del nodo izquierdo, después el del nodo contenedor y al final el del nodo derecho
  2. Pre order: Imprime el valor del nodo contenedor, después el del nodo izquierdo y al final el del nodo derecho
  3. Pos order: Imprime el valor del nodo izquierdo, después el del nodo derecho y al final el del nodo contenedor

Veámoslo en código:

public class Node{
...// El código anterior
        public void printInOrder(){
		if(left!=null){
			left.printInOrder();
		}
		System.out.println(value);
		if(right!=null){
			right.printInOrder();
		}
	}

	public void printPreOrder(){
		System.out.println(value);
		if(left!=null){
			left.printPreOrder();
		}
		if(right!=null){
			right.printPreOrder();
		}
	}

	public void printPosOrder(){
		if(left!=null){
			left.printPreOrder();
		}
		if(right!=null){
			right.printPreOrder();
		}
		System.out.println(value);
	}
}

Todo el código junto

Si unimos el código anterior queda del siguiente modo:


import java.util.Optional;

/**
 * @author raidentrance
 *
 */
public class Node {
	private Integer value;
	private Node left;
	private Node right;

	public Node(Integer value) {
		this.value = value;
	}

	public Integer getValue() {
		return value;
	}

	public void setValue(Integer value) {
		this.value = value;
	}

	public Node getLeft() {
		return left;
	}

	public void setLeft(Node left) {
		this.left = left;
	}

	public Node getRight() {
		return right;
	}

	public void setRight(Node right) {
		this.right = right;
	}

	public void add(Integer value) {
		if (value < this.value) {
			if (left != null) {
				left.add(value);
			} else {
				left = new Node(value);
			}
		} else {
			if (right != null) {
				right.add(value);
			} else {
				right = new Node(value);
			}
		}
	}

	public Optional<Node> find(Integer value) {
		if (value == this.value) {
			return Optional.of(this);
		} else if (value < this.value) {
			if (this.left != null) {
				return this.left.find(value);
			} else {
				return Optional.empty();
			}
		} else {
			if (this.right != null) {
				return this.right.find(value);
			} else {
				return Optional.empty();
			}
		}
	}

	public void printInOrder() {
		if (left != null) {
			left.printInOrder();
		}
		System.out.println(value);
		if (right != null) {
			right.printInOrder();
		}
	}

	public void printPreOrder() {
		System.out.println(value);
		if (left != null) {
			left.printPreOrder();
		}
		if (right != null) {
			right.printPreOrder();
		}
	}

	public void printPosOrder() {
		if (left != null) {
			left.printPreOrder();
		}
		if (right != null) {
			right.printPreOrder();
		}
		System.out.println(value);
	}

	@Override
	public String toString() {
		return "Node [value=" + value + ", left=" + left + ", right=" + right + "]";
	}

}

Probando el árbol

Para probar el árbol que creamos, utilizaremos una clase nueva llamada TreeTest, veamos el código:

import java.util.Optional;

/**
 * @author raidentrance
 *
 */
public class TreeTest {
	public static void main(String[] args) {
		Node root = new Node(10);
		root.add(5);
		root.add(15);
		root.add(8);

		Optional<Node> result = root.find(11);
		if (result.isPresent()) {
			System.out.println(result.get());
		} else {
			System.out.println("Value not found");
		}

		result = root.find(8);
		if (result.isPresent()) {
			System.out.println(result.get());
		} else {
			System.out.println("Value not found");
		}
		System.out.println("Print in order");
		root.printInOrder();
		System.out.println("Print pos order");
		root.printPosOrder();
		System.out.println("Print pre order");
		root.printPreOrder();
	}
}

Producirá la siguiente salida:

Value not found
Node [value=8, left=null, right=null]
Print in order
5
8
10
15
Print pos order
5
8
15
10
Print pre order
10
5
8
15

Si te gusta el contenido compártelo y no olvides seguirnos 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