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