Algoritmo de la burbuja en Java (Bubble sort)


El algoritmo de la burbuja es un algoritmo de ordenamiento de arreglos popular, este dividirá el arreglo en 2 secciones o particiones, una ordenada y la otra desordenada, durante la ejecución la partición ordenada irá creciendo y la des ordenada irá disminuyendo.

A continuación se muestra un arreglo desordenado:

El algoritmo seguirá los siguientes pasos:

  • Se tomará el primer elemento y se comparará con el siguiente
  • En caso de que sea mayor se intercambiarán los elementos de posición
  • En caso de que sea menor se hará nada
  • del lado derecho se irá creando la partición ordenada

Veamos el código

Una vez que entendimos el algoritmo veamos como se ve el código:

public class BubbleSort {
	public void sortArray(int[] array) {
		for (int i = array.length - 1; i > 0; i--) {
			for (int j = 0; j < i; j++) {
				if (array[j] > array[j + 1]) {
					swap(array, j, j+1);
				}
				printArray(array);
			}
			System.out.println("Change of partition index");
		}
	}

	public void printArray(int[] array) {
		for (int i = 0; i < array.length; i++) {
			System.out.printf("%d \t", array[i]);
		}
		System.out.println();
	}

	public void swap(int[] array, int a, int b) {
		int value = array[b];
		array[b] = array[a];
		array[a] = value;
	}

	public static void main(String[] args) {
		BubbleSort bubbleSort = new BubbleSort();
		int[] array = { 10, 1, 5, 40, 12, 34, 44, 12, 11, 9 };
		bubbleSort.printArray(array);
		bubbleSort.sortArray(array);
		bubbleSort.printArray(array);
	}
}

Ejecutando el algoritmo y analizando los resultados:

Una vez que ejecutamos la aplicación veremos la siguiente salida:

10 	1 	5 	40 	12 	34 	44 	12 	11 	9 	
1 	10 	5 	40 	12 	34 	44 	12 	11 	9 	
1 	5 	10 	40 	12 	34 	44 	12 	11 	9 	
1 	5 	10 	40 	12 	34 	44 	12 	11 	9 	
1 	5 	10 	12 	40 	34 	44 	12 	11 	9 	
1 	5 	10 	12 	34 	40 	44 	12 	11 	9 	
1 	5 	10 	12 	34 	40 	44 	12 	11 	9 	
1 	5 	10 	12 	34 	40 	12 	44 	11 	9 	
1 	5 	10 	12 	34 	40 	12 	11 	44 	9 	
1 	5 	10 	12 	34 	40 	12 	11 	9 	44 	
Change of partition index
1 	5 	10 	12 	34 	40 	12 	11 	9 	44 	
1 	5 	10 	12 	34 	40 	12 	11 	9 	44 	
1 	5 	10 	12 	34 	40 	12 	11 	9 	44 	
1 	5 	10 	12 	34 	40 	12 	11 	9 	44 	
1 	5 	10 	12 	34 	40 	12 	11 	9 	44 	
1 	5 	10 	12 	34 	12 	40 	11 	9 	44 	
1 	5 	10 	12 	34 	12 	11 	40 	9 	44 	
1 	5 	10 	12 	34 	12 	11 	9 	40 	44 	
Change of partition index
1 	5 	10 	12 	34 	12 	11 	9 	40 	44 	
1 	5 	10 	12 	34 	12 	11 	9 	40 	44 	
1 	5 	10 	12 	34 	12 	11 	9 	40 	44 	
1 	5 	10 	12 	34 	12 	11 	9 	40 	44 	
1 	5 	10 	12 	12 	34 	11 	9 	40 	44 	
1 	5 	10 	12 	12 	11 	34 	9 	40 	44 	
1 	5 	10 	12 	12 	11 	9 	34 	40 	44 	
Change of partition index
1 	5 	10 	12 	12 	11 	9 	34 	40 	44 	
1 	5 	10 	12 	12 	11 	9 	34 	40 	44 	
1 	5 	10 	12 	12 	11 	9 	34 	40 	44 	
1 	5 	10 	12 	12 	11 	9 	34 	40 	44 	
1 	5 	10 	12 	11 	12 	9 	34 	40 	44 	
1 	5 	10 	12 	11 	9 	12 	34 	40 	44 	
Change of partition index
1 	5 	10 	12 	11 	9 	12 	34 	40 	44 	
1 	5 	10 	12 	11 	9 	12 	34 	40 	44 	
1 	5 	10 	12 	11 	9 	12 	34 	40 	44 	
1 	5 	10 	11 	12 	9 	12 	34 	40 	44 	
1 	5 	10 	11 	9 	12 	12 	34 	40 	44 	
Change of partition index
1 	5 	10 	11 	9 	12 	12 	34 	40 	44 	
1 	5 	10 	11 	9 	12 	12 	34 	40 	44 	
1 	5 	10 	11 	9 	12 	12 	34 	40 	44 	
1 	5 	10 	9 	11 	12 	12 	34 	40 	44 	
Change of partition index
1 	5 	10 	9 	11 	12 	12 	34 	40 	44 	
1 	5 	10 	9 	11 	12 	12 	34 	40 	44 	
1 	5 	9 	10 	11 	12 	12 	34 	40 	44 	
Change of partition index
1 	5 	9 	10 	11 	12 	12 	34 	40 	44 	
1 	5 	9 	10 	11 	12 	12 	34 	40 	44 	
Change of partition index
1 	5 	9 	10 	11 	12 	12 	34 	40 	44 	
Change of partition index
1 	5 	9 	10 	11 	12 	12 	34 	40 	44 	

En la salida anterior podemos analizar el siguiente comportamiento:

  • Los elementos se van cambiando de izquierda a derecha
  • La partición ordenada se encontrará del lado derecho e irá creciendo cada que veamos el log “Change of partition index”
  • La partición desordenada se encontrará del lado izquierdo e irá decreciendo cada que veamos el log “Change of partition index”
  • Es posible que antes de que termine el algoritmo el arreglo ya se encuentre ordenado, pero tiene que terminar la ejecución para asegurarlo

Características del algoritmo

  • No requiere de arreglos adicionales para realizar el ordenamiento
  • La complejidad es de O(n²)
  • El performance se reduce cuando crece el número de elementos en el arreglo

Para estar al pendiente sobre nuestro contenido nuevo síguenos en nuestras redes sociales  https://www.facebook.com/devs4j/ y https://twitter.com/devs4j.

Si hay algún algoritmo que te gustaría que desarrollemos coméntenlo en nuestras redes sociales o en la sección de comentarios del post.

Autor: Alejandro Agapito Bautista

Twitter: @raidentrance

Contacto:raidentrance@gmail.com


Implementa búsquedas sobre Grafos utilizando BFS (Breadth First Search) con Java


BFS (Breadth first search) es un algoritmo para la búsqueda sobre grafos por amplitud, en este post se explicará como implementarlo con Java, se tomará como base el post Implementa un grafo de ciudades en Java y también te puede interesar el post Implementa búsquedas sobre Grafos utilizando DFS (Depth First Search) con Java.

Creando las 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, se utilizará el mismo grafo que en el ejemplo de DFS:

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 BFS sobre el grafo

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

GraphBfsSearch.java


import java.util.HashSet;

import java.util.LinkedList;

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 GraphBfsSearch {

	private Graph graph;

	public GraphBfsSearch() {

		graph = MapBuilder.getGraph();

	}

	private Optional&lt;Node&gt; getNode(String city) {

		List&lt;Node&gt; nodes = graph.getNodes();

		for (Node node : nodes) {

			if (node.getCity().equals(city)) {

				return Optional.of(node);

			}

		}

		return Optional.empty();

	}

	public boolean hasPathBfs(String source, String destination) {

		Optional&lt;Node&gt; start = getNode(source);

		Optional&lt;Node&gt; end = getNode(destination);

		if (start.isPresent() &amp;&amp; end.isPresent()) {

			return hasPathBfs(start.get(), end.get());

		} else {

			return false;

		}

	}

	public boolean hasPathBfs(Node source, Node destination) {

		LinkedList&lt;Node&gt; nextToVisit = new LinkedList&lt;&gt;();

		HashSet&lt;String&gt; visited = new HashSet&lt;&gt;();

		nextToVisit.add(source);

		while (!nextToVisit.isEmpty()) {

			Node node = nextToVisit.remove();

			if (node.getCity().equals(destination.getCity())) {

				return true;

			}

			if (visited.contains(node.getCity())) {

				continue;

			}

			visited.add(node.getCity());

			for (Edge edge : node.getAdjacents()) {

				nextToVisit.add(edge.getDestination());

			}

		}

		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 hasPathBfs(String source, String destination): Recibe dos ciudades, el origen y el destino, con esto ejecuta el método de búsqueda BFS para determinar si existe la ruta en el grafo.
  • El método booleanhasPathBfs(Node source, Node destination): Recibe un nodo origen y uno nodo destino siguiendo la siguiente lógica:
    • Se agrega el nodo origen a los nodos por visitar
    • Se ejecuta la siguiente lógica mientras existan ciudades por visitar
      • Remueve y devuelve el primer nodo por visitar
      • Si ese nodo es igual al destino devolvemos que si existe una ruta por visitar y termina el proceso
      • Valida si la ciudad que se está buscando ya fue visitada, en ese caso continua con la siguiente iteración
      • Agrega la ciudad que se validó a la lista de nodos visitados
      • itera todos los nodos adjacentes para agregarlos a las ciudades por visitar
    • En caso de no encontrar una ruta devuelve false.

Caso de ejemplo

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

Inicio :Source =Puebla, Destination=Cuernavaca,

  • Se Agrega a nextToVisit la ciudad de puebla
  • la variable nextToVisit contiene a la ciudad de puebla, mientras no esté vacía se ejecutarán las siguientes iteraciones:

Iteración 1:  Visited={},NextToVisit={Puebla}

  • Se remueve de nextToVisit la ciudad de puebla y se asigna en la variable node
  • Se valida si la ciudad de la variable node (Puebla) es igual a la ciudad de destino (Cuernavaca), devuelve falso así que continua.
  • Se valida si la lista visited contiene la ciudad de Puebla, devuelve falso así que continua.
  • Agrega a visited la ciudad de Puebla
  • Obtiene todos los nodos adyacentes de puebla (Tlaxcala y Toluca) y los agrega a la lista nextToVisit

cities-graph

Iteración 1: Visited={Puebla},NextToVisit={Tlaxcala, Toluca}

  • Se remueve el primer elemento de nextToVisit (Tlaxcala) y se asigna en la variable node
  • Se valida si la ciudad de la variable node (Tlaxcala) es igual a la ciudad de destino (Cuernavaca), devuelve falso así que continua.
  • Se valida si la lista visited contiene la ciudad de Tlaxcala, devuelve falso así que continua.
  • Agrega a visited la ciudad de Tlaxcala
  • Agrega todos los nodos adyacentes de Tlaxcala a la lista nextToVisit, en este caso no hay ninguno así que continua.

graph - Page 1

Iteración 1: Visited={Tlaxcala,Puebla},NextToVisit={Toluca}

  • Se remueve el primer elemento de nextToVisit (Toluca) y se asigna en la variable node
  • Se valida si la ciudad de la variable node (Toluca) es igual a la ciudad de destino (Cuernavaca), devuelve falso así que continua.
  • Se valida si la lista visited contiene la ciudad de Toluca, devuelve falso así que continua.
  • Agrega a visited la ciudad de Toluca
  • Agrega todos los nodos adyacentes de Toluca (Puebla, Cuernavaca,Tlaxcala, DF) a la lista nextToVisit.

graph - Page 1

Iteración 1: Visited={Tlaxcala,Puebla,Toluca},NextToVisit={Puebla, Cuernavaca,Tlaxcala, DF}

  • Se remueve el primer elemento de nextToVisit (Puebla) y se asigna en la variable node
  • Se valida si la ciudad de la variable node (Puebla) es igual a la ciudad de destino (Cuernavaca), devuelve falso así que continua.
  • Se valida si la lista visited contiene la ciudad dePuebla, devuelve verdadero así que se salta las siguientes líneas del loop y se va a la siguiente iteración.

graph - Page 1

Iteración 1: Visited={Tlaxcala,Puebla,Toluca},NextToVisit={ Cuernavaca,Tlaxcala, DF}

  • Se remueve el primer elemento de nextToVisit (Cuernavaca) y se asigna en la variable node
  • Se valida si la ciudad de la variable node (Cuernavaca) es igual a la ciudad de destino (Cuernavaca), devuelve verdadero así que termina el programa indicando que si existe una ruta entre puebla y Cuernavaca.

graph - Page 1

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) {

		GraphBfsSearch graph = new GraphBfsSearch();

		System.out.println("\n\t Paths from DF \n");

		System.out.println(String.format("From DF to DF %s", graph.hasPathBfs("DF", "DF")));

		System.out.println(String.format("From DF to Toluca %s", graph.hasPathBfs("DF", "Toluca")));

		System.out.println(String.format("From DF to Cuernavaca %s", graph.hasPathBfs("DF", "Cuernavaca")));

		System.out.println(String.format("From DF to Puebla %s", graph.hasPathBfs("DF", "Puebla")));

		System.out.println(String.format("From DF to Tlaxcala %s", graph.hasPathBfs("DF", "Tlaxcala")));

		System.out.println(String.format("From DF to Cancún %s", graph.hasPathBfs("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", graph.hasPathBfs("Toluca", "Toluca")));

		System.out.println(String.format("From Toluca to DF %s", graph.hasPathBfs("Toluca", "DF")));

		System.out.println(String.format("From Toluca to Cuernavaca %s", graph.hasPathBfs("Toluca", "Cuernavaca")));

		System.out.println(String.format("From Toluca to Puebla %s", graph.hasPathBfs("Toluca", "Puebla")));

		System.out.println(String.format("From Toluca to Tlaxcala %s", graph.hasPathBfs("Toluca", "Tlaxcala")));

		System.out.println(String.format("From Toluca to Cancún %s", graph.hasPathBfs("Toluca", "Cancún")));

		System.out.println("\n\t Paths from Cuernavaca \n");

		System.out.println(

				String.format("From Cuernavaca to Cuernavaca %s", graph.hasPathBfs("Cuernavaca", "Cuernavaca")));

		System.out.println(String.format("From Cuernavaca to DF %s", graph.hasPathBfs("Cuernavaca", "DF")));

		System.out.println(String.format("From Cuernavaca to Toluca %s", graph.hasPathBfs("Cuernavaca", "Toluca")));

		System.out.println(String.format("From Cuernavaca to Puebla %s", graph.hasPathBfs("Cuernavaca", "Puebla")));

		System.out.println(String.format("From Cuernavaca to Tlaxcala %s", graph.hasPathBfs("Cuernavaca", "Tlaxcala")));

		System.out.println(String.format("From Cuernavaca to Cancún %s", graph.hasPathBfs("Cuernavaca", "Cancún")));

		System.out.println("\n\t Paths from Puebla \n");

		System.out.println(String.format("From Puebla to Puebla %s", graph.hasPathBfs("Puebla", "Puebla")));

		System.out.println(String.format("From Puebla to Cuernavaca %s", graph.hasPathBfs("Puebla", "Cuernavaca")));

		System.out.println(String.format("From Puebla to DF %s", graph.hasPathBfs("Puebla", "DF")));

		System.out.println(String.format("From Puebla to Toluca %s", graph.hasPathBfs("Puebla", "Toluca")));

		System.out.println(String.format("From Puebla to Tlaxcala %s", graph.hasPathBfs("Puebla", "Tlaxcala")));

		System.out.println(String.format("From Puebla to Cancún %s", graph.hasPathBfs("Puebla", "Cancún")));

		System.out.println("\n\t Paths from Tlaxcala \n");

		System.out.println(String.format("From Tlaxcala to Tlaxcala %s", graph.hasPathBfs("Tlaxcala", "Tlaxcala")));

		System.out.println(String.format("From Tlaxcala to Puebla %s", graph.hasPathBfs("Tlaxcala", "Puebla")));

		System.out.println(String.format("From Tlaxcala to Cuernavaca %s", graph.hasPathBfs("Tlaxcala", "Cuernavaca")));

		System.out.println(String.format("From Tlaxcala to DF %s", graph.hasPathBfs("Tlaxcala", "DF")));

		System.out.println(String.format("From Tlaxcala to Toluca %s", graph.hasPathBfs("Tlaxcala", "Toluca")));

		System.out.println(String.format("From Tlaxcala to Cancún %s", graph.hasPathBfs("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", graph.hasPathBfs("Cancún", "Cancún")));

		System.out.println(String.format("From Cancún to Tlaxcala %s", graph.hasPathBfs("Cancún", "Tlaxcala")));

		System.out.println(String.format("From Cancún to Puebla %s", graph.hasPathBfs("Cancún", "Puebla")));

		System.out.println(String.format("From Cancún to Cuernavaca %s", graph.hasPathBfs("Cancún", "Cuernavaca")));

		System.out.println(String.format("From Cancún to DF %s", graph.hasPathBfs("Cancún", "DF")));

		System.out.println(String.format("From Cancún to Toluca %s", graph.hasPathBfs("Cancún", "Toluca")));

	}

Al ejecutar el programa mostrará la siguiente 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 BFS.

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 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

Búsqueda binaria en Java paso a paso


El algoritmo de búsqueda binaria funciona sobre arreglos ordenados y es utilizado para buscar un elemento en los mismos.

Funcionamiento

El funcionamiento del algoritmo es simple y cuenta con las siguientes partes:

  • Datos de entrada :
    • Un arreglo ordenado
    • Un valor a buscar en el arreglo
  • Datos de salida:
    • La posición del elemento en el arreglo o -1 en caso de no encontrarlo

El algoritmo de búsqueda binaria sigue los siguientes pasos:

  • Verifica si el elemento a buscar es menor al máximo elemento en el arreglo y mayor al mínimo elemento del arreglo, en caso de no ser así  se devolverá -1 ya que sabemos que no se encuentra el elemento.
  • Obtiene el elemento que se encuentra en la mitad del arreglo y lo compara con el valor que se busca.
  • En caso de que el elemento sea mayor al valor que se busca se descartará la parte derecha y se volverá a ejecutar la misma validación pero solo sobre el lado izquierdo del arreglo.
  • El paso anterior se repetirá hasta encontrar el elemento
  • En caso de no encontrar el elemento se devolverá -1 para indicar que no se encontró.

Ejemplo práctico

A continuación presentaremos un ejemplo paso a paso de la búsqueda binaria, imaginemos el siguiente arreglo donde se desea buscar el número 400:

paso1

  • Evaluar que el número 400 es mayor al menor elemento del arreglo y menor al máximo elemento del arreglo, en este caso 10 es menor y 2222 es mayor a 400, entonces podemos pasar al siguiente paso.
  • Obtendremos el elemento de la mitad del arreglo utilizando la siguiente ecuación (límite inferior + límite superior)/2
  • En este caso la mitad del arreglo es 120, una vez hecho esto evaluaremos si 120 es mayor o menor al número que buscamos, que en este caso es 400, 400 es mayor a 120, esto significa que se encuentra del lado derecho del arreglo, así que el lado izquierdo será descartado como se muestra en la siguiente imagen:

paso2

  • Una vez hecho esto volveremos a dividir el arreglo, pero en este caso nuestro límite inferior no será 10 sino ahora será 200, y el nuevo valor de en medio será 500 como se muestra en la siguiente imagen:

paso3

  • Una vez más evaluaremos si el número 500 es mayor o menor al número que buscamos que es 400, en este caso 400 es menor a 500, entonces la parte de la derecha será descartada como se muestra en la siguiente imagen:

paso4

  • Con lo anterior el nuevo límite inferior es el 200 y el nuevo límite superior es 400 así que ejecutaremos nuestra ecuación para obtener el elemento de la mitad, en este caso es la posición 7 del arreglo que es 200 así que volveremos a reducir en uno el límite superior, con esto tanto el límite superior como el límite inferior se encuentran en la posición 8 como se muestra en la siguiente imagen:

paso 5

  • Listo ! encontramos el elemento que buscábamos en el arreglo, esto nos tomó 4 iteraciones en lugar de 9 si hubiéramos iterado el arreglo indice por indice, con esto se demuestra que es mucho más eficiente que iterar el arreglo posición por posición. La complejidad de una búsqueda lineal es de O(n) mientras que la complejidad de una búsqueda binaria es O(Log n) lo cuál indica que es mucho más eficiente, solo consideremos que para poder ejecutarla el arreglo debe estar ordenado.

Implementación de la búsqueda binaria en Java

A continuación se presenta el código para ejecutar la búsqueda binaria en Java:

public class ChallengeClass {
	public static int binarySearch(int[] array, int minLimit, int maxLimit, int value) {
		if (maxLimit >= 0 && array[minLimit] <= value && array[maxLimit] >= value) {
			int mid = getMidValue(minLimit, maxLimit);
			System.out.println(String.format("Límite inferior %d límite superior %d valor en el arreglo %d valor a buscar %d", minLimit,maxLimit,array[mid],value));
			if (array[mid] == value) {
				return mid;
			} else if (array[mid] <span 				data-mce-type="bookmark" 				id="mce_SELREST_start" 				data-mce-style="overflow:hidden;line-height:0" 				style="overflow:hidden;line-height:0" 			></span>< value) {
				return binarySearch(array, mid + 1, maxLimit, value);
			}
			return binarySearch(array, minLimit, mid - 1, value);
		}
		return -1;
	}

	public static int getMidValue(int minLimit, int maxLimit) {
		return (maxLimit + minLimit) / 2;
	}

	public static void main(String[] args) {
		int value = 400;
		int[] array = { 10, 15, 20, 40, 50, 100, 120, 200, 400, 500, 600, 800 ,2222};
		int result = binarySearch(array, 0, array.length - 1, value);
		System.out.println(String.format("Result %d", result));
	}
}

La implementación presentada fue hecha sin utilizar ningún api de Java para el manejo de búsquedas u ordenamientos.

Implementación de búsqueda binaria utilizando clases existentes en Java

Como sabemos Java provee de un framework para el manejo de colecciones y arreglos, a continuación se presenta el código para ejecutar la búsqueda binaria utilizando dichas clases:

import java.util.Arrays;

public class ChallengeClass {

	public static void main(String[] args) {
		int[] array = { 10, 15, 20, 40, 50, 100, 120, 200, 400, 500, 600, 800, 2222 };
		int result = Arrays.binarySearch(array, 400);
		System.out.println(String.format("Result %d", result));
	}
}

Es importante mencionar que el método binarySearch de la clase Arrays también requiere que el arreglo que se pase como parámetro se encuentre ordenado, en caso contrario los resultados pueden ser erróneos.

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

¿Cómo trabajar en Google? Analizando preguntas de entrevista


Uno de los lugares donde la mayor parte de los desarrolladores desea trabajar es Google, en este post analizaremos algunos problemas que exponen en su canal de youtube y daremos las soluciones en código Java, el problema que analizaremos el día de hoy es el siguiente:

Dado un arreglo de números determinar si dentro de este se encuentra el par de números que de la suma proporcionada

Datos de entrada:

  • Arreglo de números que podemos asumir que se encuentran ordenados
  • Valor entero que representa una suma

Datos de salida:

  • Expresión boolean de acuerdo a lo siguiente:
    • Verdadero: Si dentro del arreglo se encuentran dos números que al sumarlos dan el valor entero recibido
    • Falso : Si dentro del arreglo no se encuentran dos números que al sumarlos den el valor entero recibido

Ejemplos:

array = [1 , 2 , 3 , 9]   sum=8    salida=false

array = [1 , 2 , 4 , 4]   sum=8    salida=true

Antes de continuar te recomendamos que intentes resolverlo por ti mismo.

Solución 1

La primera solución y más sencilla es realizar todas las sumas posibles y validar si alguna de ellas genera el resultado esperado.

public class SearchSums {
	public static boolean searchSumInArray(int arr[], int sum) {
		for (int i = 0; i < arr.length; i++) {
			for (int j = i + 1; j <arr.length; j++) {
				if (i != j && arr[i] + arr[j] == sum) {
					return true;
				}
			}
		}
		return false;
	}

	public static void main(String[] args) {
		int arr[] = { 1, 2, 4, 4 };
		int sum = 8;
		boolean response = searchSumInArray(arr, sum);
		System.out.println(response);
	}
}

Como se puede observar el programa anterior cumple con los requerimientos en el enunciado, pero si vas a una entrevista a Google esta no es la respuesta que debes dar por lo siguiente:

Aunque el código es simple y fácil de leer esta no es una solución óptima debido a que su complejidad (Hablando de notación Big O) es muy grande así que aunque tu pienses que lo resolviste de forma correcta esta respuesta será marcada como incorrecta.

Solución 2

La solución dos tiene un poco más de ciencia pero es mucho más óptima, para la explicación utilizaremos los siguientes datos de entrada:

array = [1 , 2 , 4 , 4]   sum=8

Analicemos el problema:

  • Recordemos que el arreglo esta ordenado de menor a mayor
  • La suma  posible más grande será con los dos últimos valores debido a que son los más grandes
  • La suma posible más pequeña será con los primeros dos valores debido a que son los más pequeños

Una vez mencionado lo anterior comencemos a diseñar la solución del problema siguiendo los siguientes pasos:

  • Colocaremos dos indices en nuestro arreglo uno en el último valor (j) y el otro en el primero (i).
  • Sumaremos el valor que se encuentra en esos dos indices, en este ejemplo serían 1 y 4.
    • Si el valor es igual a la suma que es 8 devolveremos verdadero y terminaremos el problema.
    • Si el valor es mayor a la suma que es 8 decrementaremos el indice j
    • Si el valor es menor a la suma que es 8 incrementaremos el indice i
  • Repetiremos este proceso hasta que siempre y cuando i sea menor que j

Veamos el código resolviendo lo anterior:

public class SearchSums {
	public static boolean searchSumInArray(int arr[], int sum) {
		for (int i = 0, j = (arr.length - 1); i < j;) {
			int localSum = arr[j] + arr[i];
			if (localSum == sum) {
				return true;
			} else if (localSum > sum) {
				j--;
			} else if (localSum < sum) {
				i++;
			}
		}
		return false;
	}

	public static void main(String[] args) {
		int arr[] = { 1, 2, 3, 5, 9 };
		int sum = 8;
		boolean response = searchSumInArray(arr, sum);
		System.out.println(response);
	}
}

Con esta solución se puede conseguir el mismo objetivo que con la anterior pero de una manera mucho más óptima.

Recordemos que este algoritmo esta basado en que los datos están ordenados del mayor al menor, si este no fuera el caso la forma en la que se resolvería sería diferente.

Este problema se tomó de la cuenta de Youtube Life at Google y es el siguiente:

En este post solo se explicó la solución del problema asumiendo que el arreglo está ordenado en un próximo post se explicará la solución cuando el arreglo no está ordenado y más problemas de Google. Si tienes más soluciones coméntanoslas en la sección de comentarios.

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